How to prove the nonexistence of cycles in the game of Chain Reaction?

125 Views Asked by At

Chain Reaction is a two player combinatorial game played on a $9 \times 6$ game board in which players Red and Green take turns to place a single atom of their color in an empty square or in a square that they control. Placing more than one atom in the same square creates a molecule.

The more atoms in a molecule, the more unstable it becomes. When a molecule becomes too unstable it splits and its atoms move to orthogonally adjacent squares, changing the color of the atoms in those squares to match their color. This can cause a chain reaction of splitting molecules.

Molecules in the four corner squares require two atoms to split. Molecules on the edge of the board require three atoms to split. Molecules in the center of the board require four atoms to split. Atoms of a splitting molecule each move in a different direction.

The game ends immediately after one player captures all of the atoms belonging to the other player. What I'm interested in is proving the nonexistence of cycles in any chain reaction because otherwise the next turn would never begin. How would I go about proving this? I don't know where to begin.

1

There are 1 best solutions below

0
On BEST ANSWER

The key insight is to draw a tight boundary around the cells which split in the infinite cycle, such that each time round the cycle atoms must exit the boundary wherever it doesn't coincide with the edge of the board, but never enter the boundary. Then either the boundary coincides exactly with the edge of the board, and every cell is involved in the cycle; or there is an exodus of an infinite number of atoms from the boundary, which is impossible because we start with a finite number and don't create more.