Infection spread on a torus chessboard

Question

In one of his books, Peter Winkler includes the following problem:

A disease is spreading on a $n\times n$ chessboard as follows: if a healthy cell is neighboring at least 2 infected cells, it becomes infected. Using the property that the perimeter of the infected area never increases, it’s easy to prove that it’s impossible to infect the entire chessboard with fewer than $n$ infected cells.

If the chessboard is a torus, the result no longer holds (verified on some instances of $n$). It seems that $n-1$ is the smallest number of infected cells required to infect the chessboard. The perimeter argument can’t be used here. Does anyone know any other ‘invariant’ that can be used?

Note: two cells are neighbors if they share one side.

Answer 1

EDIT: This answer is actually totally wrong! I'm leaving it up so that others do not make the same mistake as I, but here is an example (thanks to Anton Petrunin) which shows that my supposed non-increasing quantity actually can increase. Initially, three cells are infected, and the restricted perimeter is $10$, but after 3 moves, the restricted perimeter increases to $12$.

---

Suppose there are only $n-2$ infected cells. Without loss of generality, these infected cells occur in the lower left $(n-1)\times (n-1)$ subgrid of the torus. If not, rotate the torus until one of the columns with no infections is on the right (such a column must exist, since there are at most $n-2$ infections), then rotate until a row with no infections is on top.

The desired invariant quantity is the perimeter of the figure comprising the infected cells only in the lower left $(n-1)\times (n-1)$ subgrid, ignoring wrap-around. Let us call this the "restricted perimeter."

To prove invariance, note that a cell which becomes infected in the top row or right column does not affect the restricted perimeter at all. On the other hand, a cell in the lower left $(n-1)\times (n-1)$ subgrid becoming infected does not increase the restricted perimeter for the same reason as in the non-torus case.

With this definition, the same argument goes through. If there are initially $n-2$ infected cells, then the restricted perimeter is at most $4(n-2)$. But when if the entire torus is infected, the restricted perimeter would be $4(n-1)$.

Here is an example when $n=4$. The left grid is the initial infection, with two infected cells. The restricted perimeter is initially $8$. The right grid is the infection one step later, and the restricted perimeter is still $8$. The edges contributing to the restricted perimeter are highlighted in orange. The topmost orange edge in the second picture might appear strange, since it is between two black squares. But remember, you have to mentally delete the top row and right edge, then consider the perimeter of what remains.

Answer 2

Consider separately two ways the infection can grow. When infection spreads to an empty cell, it can be that two of the adjacent infected cells share a corner (which is always the case when there are three or four adjacent infected cells) or not, in which case the two infected cells are both in the same row or column.

Within a row or column, we will say a component is a group of consecutive infected cells in that row or column. (We don't care whether the infected cells are connected via a path that lies outside the row or column.) Our proposed invariant is based on the total number of components among both rows and columns (with an exception noted below).

We will consider growth not in generations, but in individual steps where the infection grows to only a single cell at each step. (The order will not matter unless noted.)

Under the first kind of growth, new components cannot be created. The step can only decrease the number of components in a row or column or both.

Under the second kind of growth, usually the number of components of a single row or column will go down by one (as the components are joined by the infection of the cell between them) and the number of components in the corresponding column or row will either increase by one or stay the same. In this case, then, the total number of components will not increase.

The other case is when the last cell in the row or column is being infected. The first time this happens for rows and the first time for columns, it can indeed increase the number of components by one. However, we not need to concern ourselves with subsequent times. Without loss of generality, consider rows. If one row is already completely infected and a second row is one cell from being completely infected, then either there is a column component that connects these row components or not. If there is a connecting column component, then (by infecting in a different order) the first kind of growth can be used to infect the entire stripe bounded by the rows and the connecting component. (This includes the last cell in this new row which will have been infected without increasing the number of components.) If there is no such connection, then in $n - 1$ columns, there are at least $2$ components each plus at least $1$ component in the last column plus $2$ rows with at least one component. This is at least $2n + 1$ total components. We will not be concerned with cases that have so many components.

If we start with $n - 2$ infected cells, then there are at most $n - 2$ column components and $n - 2$ row components for a total of $2n - 4$ components. At most two new components can be introduced; one by the first full row infection and one by the first full column infection. This gives at most $2n - 2$ components. As this is less than $2n + 1$, any subsequent full row or column infection can be completed by growth of the first kind without increasing the number of components. Thus, the final number of components will be at most $2n - 2$. This is less than the $2n$ of the completely infected board.