Infection: The Solution

And here it is: the solution to last week's problem:

Consider any configuration of infected cells. Calculate the length of the boundary of these cells (a single side being 1 unit long) and call it L.

L remains constant as more cells are infected



In the picture above, the blue lines mark the boundary of the infected region. Observe that when a new cell is infected, it destroys two boundary pieces (from the cells that infected it) and adds two (for its other two sides). Hence L remains constant. Since the boundary of the entire grid is of length 4n, and each infected cell can contribute at most 4 units to L, there must be at least n infected squares to start with.

---

Credit to Shankar Krishnan, and Rudolf Fleischer, who supplied a variant of this proof.