Bootstrap Percolation

grid infection puzzle

On a 12 × 12 grid, some squares are infected and some are healthy. On each turn, a healthy square becomes infected if it has two or more infected orthogonal neighbors. (In the example above, the black squares are infected, the white squares are healthy, and the gray squares will be infected next turn.) What’s the smallest number of initially infected squares that can spread an infection over the whole board?

	Select Click for Answer
Twelve (or, on an n × n grid, n). The key is to notice that the total perimeter of the infected area never increases. Since the fully infected board has a perimeter of 48, we need an initial arrangement of infected squares with a perimeter of at least 48, or 48/4 = 12 squares. The simplest example is a long diagonal. From Béla Bollobás, The Art of Mathematics, 2006.

November 19, 2013November 29, 2013 | Puzzles