Please turn on javascript in your browser to play chess.
Posers and Puzzles

Posers and Puzzles

  1. 15 Jun '08 12:58
    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.
  2. 15 Jun '08 13:22 / 2 edits
    SOLV'D
  3. Subscriber sonhouse
    Fast and Curious
    15 Jun '08 14:28
    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.
  4. 15 Jun '08 14:40
    My chesss board is infected. But I rather call it jinxed...
  5. 15 Jun '08 15:24
    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?
  6. 15 Jun '08 16:37
    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.
  7. Standard member ChronicLeaky
    Don't Fear Me
    15 Jun '08 18:52 / 3 edits
    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?