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.
Hint
Solution
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