Grid Infection


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

Previous Puzzle: Twelve Coins

One of twelve coins is counterfeit: it is either heavier or lighter than the rest. Is it possible to identify the counterfeit coin in three weighings on a beam balance?

Next Puzzle: Duplicate Integer

An array of length n+1 is populated with integers in the range [1, n]. Find a duplicate integer (just one, not all) in linear time with O(1) space. The array is read-only and may not be modified. Variation: what if the array may be written into but must be left unmodified by the algorithm?

26 Oct 2008
© Copyright 2008—2017, Gurmeet Manku.