## The Infection Puzzle

by Jesse Farmer on Tuesday, April 15, 2008

I first heard this puzzle from the affable Hungarian mathematician and computer scientist LÃ¡szlÃ³ Babai in his Combinatorics and Probability class. It gave headaches to a lot of people much smarter than I am, but there is what Babai would call an "Ah-haaaa!" solution. Read on if you're brave enough.

#### The Rules

The rules of the puzzle are simple.

1. You are given an n-by-n board, e.g., an 8x8 chessboard.
2. Some initial number of the squares are "infected."
3. If an uninfected square shares an edge with two or more infected squares then it too becomes infected.
4. The infection spreads until there are no more squares which can be infected.

We view the infection as spreading in discrete time steps, which makes this puzzle an example of a cellular automaton. Here is an example of an initial infection which stops spreading well before it infects the whole board.

#### The Puzzle

There are many initial configurations which will infect the whole board. The most obvious and least interesting configuration is one with every square infected. It's also not hard to see that we can infect the whole board with fewer than this many initially infected squares. So, the question is, what is the smallest number of initially infected squares required to infect an n-by-n board? Does it depend on n? If so, how?

To help you get a grips on the puzzle I've included a Javascript implementation below using the canvas tag. This means that IE users are out of luck, but if you're on Windows you should be using Firefox or Opera, anyhow. Edit: I just learned about Google's Explorer Canvas, so hopefully this now works in IE. Since I don't have the means to test it on my laptop "hopefully" is the best I can offer.

To infect or disinfect a square just click on it. Once you're ready to test your initial configuration click "Run it!".

Run it! | Clear

You're free to use the code pursuant to the Creative Commons Attribution-ShareAlike 3.0 license. The code requires a browser that supports the canvas tag, as mentioned above, and also the Prototype JavaScript framework.