Gateways To Joy
/
Puzzles
/
Set 6
/
Grid Infection
Grid Infection
26 Oct 2008
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 n2 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.
Send me email