4
$\begingroup$

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.

$\endgroup$
4
  • 3
    $\begingroup$ Obviously adding an atom to a fully-loaded board will result in an infinite chain reaction, since there is not enough room for stable molecules. So you probably need some limits on board state to identify when infinite chains can't occur. $\endgroup$
    – Joffan
    Sep 4 '17 at 5:36
  • $\begingroup$ Indeed. However, upon adding an atom to a fully loaded board one player would be wiped out and hence the game would immediately end. Any infinite chain reaction would necessarily have to keep at least one enemy atom untouched. $\endgroup$ Sep 4 '17 at 6:24
  • 1
    $\begingroup$ In that case, I think it could be shown that any infinite chain reaction would affect every cell on the board, ending the game. $\endgroup$
    – Joffan
    Sep 4 '17 at 6:39
  • $\begingroup$ Makes sense. Thanks for the insight. I'll try to formalize it now. $\endgroup$ Sep 4 '17 at 6:47
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.