The Infection Puzzle

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.

Update

If you've read the comments when you know you can infect the whole n-by-n board by infecting one of the diagonals. This leads people to believe that you cannot infect the whole board with fewer than n initially-infected squares. The first "proof" of this rests in the claim that for the whole board to be infected every row and column must contain at least one infected square. If we start with fewer than n squares infected than at least one row or column would be empty, so that the whole board could not be infected.

This would be a fine proof were it the case that every row or column must have an initially infected square. Here's a configuration which infects the whole board but which nevertheless has fewer than n (here n=8) infected rows and columns:

So, we know we can infect the whole board by infected n squares initially (one of the diagonals). But can we do it in fewer? If not, why not?