- 15 Jun '08 12:58Since we are chessplayers and love board puzzles, here is another one.

An infection spreads among the squares of an n x n checkerboard in the following way:

If a square has TWO or MORE infected NEIGHBORS, then it becomes infected itself. Neighbors are ORTHOGONAL only, so each square has AT MOST FOUR neighbors.

Prove that you cannot infect the whole board if you begin with fewer than n infected squares. - 15 Jun '08 14:28

That is a variation on the game 'life' from the '70s.*Originally posted by smaia***Since we are chessplayers and love board puzzles, here is another one.**

An infection spreads among the squares of an n x n checkerboard in the following way:

If a square has TWO or MORE infected NEIGHBORS, then it becomes infected itself. Neighbors are ORTHOGONAL only, so each square has AT MOST FOUR neighbors.

Prove that you cannot infect the whole board if you begin with fewer than n infected squares. - 15 Jun '08 15:24

More questions:*Originally posted by smaia***Since we are chessplayers and love board puzzles, here is another one.**

An infection spreads among the squares of an n x n checkerboard in the following way:

If a square has TWO or MORE infected NEIGHBORS, then it becomes infected itself. Neighbors are ORTHOGONAL only, so each square has AT MOST FOUR neighbors.

Prove that you cannot infect the whole board if you begin with fewer than n infected squares.

What if the board is cylindrical?

What if it is toroidal?

In both cases, what is the minimal number of infected squares needed to infect the entire board? - 15 Jun '08 18:52 / 3 edits

Here's a discussion of flat and some non-flat boards.*Originally posted by smaia*

An infection spreads among the squares of an n x n checkerboard in the following way:

If a square has TWO or MORE infected NEIGHBORS, then it becomes infected itself. Neighbors are ORTHOGONAL only, so each square has AT MOST FOUR neighbors.

Prove that you cannot infect the whole board if you begin with fewer than n infected squares.

There's good reason to restrict our consideration to the following four boards:

B1. A square

B2. A closed cylinder

B3. A Mobius strip with boundary

B4. A torus

(Consider tessellations of regular polygons by n^2 squares and then apply different possible quotient maps to them, eliminating cases that don't embed in R^3).

For a board B, let M(B) be the maximal integer such that no initial configuration of M(B) infected squares leads to an infection of all of B. On B1, (n-2)^2 squares have 4 neighbours and 4n - 2 have two neighbours. On B2 and B3, one edge is identified with its opposite edge, so n(n-2) squares have 4 neighbours 2n - 4 have two neighbours and 4 squares have three neighbours. On B4, every square has four neighbours. Thus a square is hardest to infect and the torus easiest, so we'd expect.

Thus (where < means "at most" ), M(B4) < M(B3) = M(B2) < M(B1) = n-1 (by Dejection's argument, I guess). Also, it's not hard to modify the proof for squares to show that M(B4) = n-2 (ie if we replace "Square" by "torus" in the original question, we should replace "n" by "n-1" in the answer). Thus:

1. Into what category do B2 and B3 fall?

2. When is it worth considering boards made out of connected sums of B1 - B4?