Problem 1: Infection.

People have suggested starting a problem of the day/week/month/ series. The problem of course is that once you start, you have to continue !
My compromise is that I will occasionally post interesting problems that come my way (and will take suggestions), with solutions a week later. No regularity in the supply of problems is guaranteed though.

So, to start, a problem that comes from the puzzle master, Peter Winkler (via Shankar Krishnan):

This is a Game of Life variant. Consider an n X n grid in the plane. Let a grid cell become infected if two of its neighbours are infected (diagonals are not included). The figure below illustrates how a cell can get infected.



Prove that in order for all the cells to become infected, at least n of the cells must have been infected to start with.

As with many of Peter's problems, there exists a Book proof. Your mission, should you choose to accept it, is to find it. Email me or post your solution in the comments. The first k people to get the right answer, (where k is a random number between 1 and 10), will be rewarded with their 10 bytes of blogosphere fame.