Puzzle

In an n by n grid of squares, two squares are neighbors if they share an edge. Initially, some squares are "infected". At successive clock ticks, an uninfected square gets infected if at least two of its neighbors are infected. How many squares must initially be infected so that all squares eventually get infected?

Source

From Peter Winkler's Mathematical Puzzles: A Connoisseur's Collection (163 pages, 2003).

Solution

At least n squares must be infected initially. The perimeter of figure(s) formed by infected squares decreases by 0, 2 or 4, depending upon whether the square just infected had 2, 3 or 4 neighbors. When all n^{2} squares are infected, the perimeter is 4n. So the initial configuration must have at least n infected squares. For example, infecting all diagonals suffices. There are other configurations too (see figure on right).

© Copyright 2008—2017, Gurmeet Manku.