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.
- You are given an n-by-n board, e.g., an 8×8 chessboard.
- Some initial number of the squares are "infected."
- If an uninfected square shares an edge with two or more infected squares then it too becomes infected.
- 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!".
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?
Though i don’t know much about combinatorics and probability, mine minimum of infected squares was exactly n.
Can you prove it? And have you seen this puzzle before?
*Spoilers warning*
I’ve never seen this before, and I agree with Eimantas. Obviously we have an upper bound of n by marking everything on a diagonal. But it’s not particularly hard to prove that it’s the lower bound. In order for a square to turn black, it must already be in a row or column that another black one is in. And it takes n squares to put a mark in every row and column. So the lower bound is n.
-E
Actually, on second thought, that’s a flawed proof, because a BWB leads to BBB, which might put a mark in a new column. Oh well, I’m not interested enough to give it more thought =/
I just read your article on dynamic programming so my mind is very much recursively focused atm. (I haven’t seen this problem before).
To illustrate the line of thinking I want to use:
Assume we can fill an m-by-m grid with k cells initially coloured in. Then we can fill an (m+1)-by-(m+1) grid with k+1 cells by adding a row to the bottom and column to the right side of our m-by-m grid and colouring the bottom right cell. (We colour the first k cells as in our m-by-m set up). Clearly the first k cells will still do their thing and fill the m-by-m square in the top left corner. Then, or before then, the bottom right cell will cause the bottom row and right-most column to fill.
Since we can fill a 1-by-1 square with 1 cell initially it follows inductively that we can fill an n-by-n with n cells filled initially.
~~
To prove a lower bound along this line of reasoning we need to show that if you can’t fill an m-by-m with k cells then you can’t fill an (m+1)-by-(m+1) with k+1 cells. If we can’t fill it with k+1 cells then clearly we can’t fill it with less then k+1 either.
If we can show this then the result follows fairly simply via induction: we can’t fill a 1-by-1 grid with 0 cells coloured initially.
We know that the infection can’t spread further right/left/up/down then the right/left/up/down-most square initially coloured in. To see this for the down-most case:
Assume we have some down-most cell A (and no ties for this title) which isn’t in the bottom row. Since we can’t generate coloured squares diagonally, if a coloured square gets generated further down then A it must be generated directly below A. But the way generation works means there needs to be another square touching the square directly below A. Necessarily this other square must be further down then A - our downmost square - contradiction. Hence we can’t generate a square lower then A.
It follows then that in any completely filled grid there were initially coloured cells in the bottom and top rows and in the left and right edge columns. Note this can be achieved with two cells by placing them in diagonally opposite corners.
Out of time unfortunately, perhaps I’ll get back to this later.
Isn’t growth from the initial configuration limited by the perimeter of the initially infected “shape” since you need two sides of a square to infect another square? In fact, isn’t the final infection at most a rectangle with the perimeter of the original shape since each infection spends two sides to create a newly infected square which has at most two unobstructed sides to contribute to new infections? So, since the entire board has a perimeter of 32, the initial infection must also and the only way to get this is with 8 “un-adjacent” squares.
On a personal note: I found this puzzle because one of my co-founders saw http://appaholic.com/ and your interest in my previous company, iLike, and said “we’ve got to bring this guy in for an interview”. Check out http://vadver.com/jobs.php and let me know when you can come in to learn more about our plans.
Patrick,
I finally approved your comment. And yep, that’s what the Hungarian mathematician who first told me this puzzle would call the “Ah-haa!” solution. The perimeter never decreases as the infection spreads so to infect an NxN board you need at least N initially infected squares.