Sunday, 16 September 2012

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?

1 comment:

  1. Atleast n squares - the sum of perimeters can only decrease. the final perimeter is 4n so need to start with atleast n squares.