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?

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

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² 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).