The cells of a square are susceptible to infection. In a unit of time, the cells with 2 or more infected neighbours (having a common side) become infected. Is it possible to start the infection in
a. nine cells,
b. ten cells,
in such a way that the infection spreads to the whole square?
It is easy to observe that the infection can never spread outside of a rectangle that bounds it. A less obvious but more useful observation is that the total perimeter of the infected area will never increase.
Let infected squares be black and non-infected squares be white. It is clear that the spread can be considered on a square-by-square basis, as additional infected squares will not hamper the infection of others.
We need then to consider the cases in which a square may get infected.
There are four ways in which it can have two or more black neighbours:
If it has exactly two infected neighbours, the black perimeter does not change, if it has three infected neighbours, the black perimeter will decrease by , and if all the neighbours are infected, the perimeter will decrease by .
To solve the problem, nine cells have a maximal perimeter of , whereas the total square has a perimeter of , so it is not possible to infect the entire square. If there are ten cells, which all lie along the main diagonal of the square, the infection will spread everywhere.