Infecting a chessboard

Question

Some squares of an n by n board are infected. Every minute, any healthy square that has at least two infected neighbours (sharing an edge, not just a corner) becomes infected. Infected squares stay infected. 1. Show that n squares, suitably placed, can eventually infect the entire board. 2. Prove that fewer than n initially infected squares can never infect the whole board, however cleverly they are placed.

Accepted Answer

Part 1: the diagonal works. Infect the n squares on the main diagonal. Each square just off the diagonal touches two diagonal squares, so it becomes infected in the first minute; the next diagonal band follows, and the infection sweeps out to the corners. Every square eventually catches it. Part 2: the perimeter never grows. Define the perimeter of the infected region as the number of unit edges that separate an infected square from either a healthy square or the outside of the board. A single infected square has perimeter 4, so k initially infected squares have perimeter at most 4k. Now watc…

Infecting a chessboard

Your answer

Discussion

Learn the concepts

Related questions