I learned about the following result from one of Peter Winkler's books:
It is impossible to infect the entire $n\times n$ chessboard (usual chessboard) starting from fewer than $n$ infected cells.
The infection is a deterministic process: a healthy cell that is neighboring at least $2$ infected cells becomes infected. Two cells are neighbors if they share one side. The technique that was proposed to prove the lower bound relies on the property that the perimeter of the infected area does not increase.
If we set the same problem (same infection rule and neighborhood definition) on a torus (by joining opposite sides of the chessboard), I noticed that $n-1$ infected cells are sufficient to infect the entire torus. However, I was not able to prove that it's impossible to infect the entire torus using fewer than $n-1$ infected cells, which seems to stand for some instances of $n$ at least. I tried to find similar 'invariant arguments' as the perimeter argument mentioned above, but settled with nothing. Does anyone know a similar technique to solve this problem?
