15 Jun 08
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
Originally posted by smaiaThat is a variation on the game 'life' from the '70s.
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
Originally posted by smaiaMore questions:
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
3 edits
Originally posted by smaiaHere's a discussion of flat and some non-flat boards.
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.
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?