Infected board

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.

SOLV'D

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.

That is a variation on the game 'life' from the '70s.

My chesss board is infected. But I rather call it jinxed...

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.

More questions:
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?

Originally posted by David113
More questions:
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?

it is a flat board of course.

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.

Here's a discussion of flat and some non-flat boards.

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?