Medium Discrete Maths

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.

Source: P. Winkler
Enable Like and Comment