medium | discrete |

An infection spreads among the squares of an nXn checkerboard in the following manner. If a square has two or more infected neighbors, it becomes infected itself. (Each square has 4 neighbors only!). Prove that you cannot infect the whole board if you begin with fewer than n infected squares.

Invariance

Perimeter of infected area can't increase. It stays constant or decreases. Initially maximum perimeter is 4 * k if k blocks are infected. But to infect all blocks, the perimeter must increase to 4 * n, $k<n$. This is not possible