Conway's Soldiers
From Wikipedia, the free encyclopedia
Conway's Soldiers is a one-person mathematical game or puzzle devised and analyzed by mathematician John Horton Conway in 1961. A variant of peg solitaire, it takes place on an infinite checkerboard. The board is divided by a horizontal line that extends indefinitely. Above the line are empty cells and below the line are an arbitrary number of game pieces, or "soldiers". As in peg solitaire, a move consists of one soldier jumping over an adjacent soldier into an empty cell, vertically or horizontally (but not diagonally), and removing the soldier which was jumped over. The goal of the puzzle is to place a soldier as far above the horizontal line as possible.
Conway proved that, regardless of the strategy used, there is no finite series of moves that will allow a soldier to advance more than four rows above the horizontal line. His elegant argument uses a carefully chosen weighting of cells (involving the golden ratio), and he proved that the total weight can only decrease or remain constant. This beautiful argument has been reproduced in a number of popular math books.
Simon Tatham has shown that the fifth row can be reached via an infinite series of moves [1]; this result is also in a paper by Pieter Blue and Stephen Hartke [2]. If diagonal jumps are allowed, the 8th row can be reached but not the 9th row. It has also been shown that, in the n-dimensional version of the game, the highest row that can be reached is 3n-2. Conway's weighting argument demonstrates that the row 3n-1 cannot be reached. It is considerably harder to show that row 3n-2 can be reached (see the paper by Eriksson and Lindstrom).
In the novel The Curious Incident of the Dog in the Night-time, the protagonist remarks that Conway's soldiers is "a good mathematics problem to do in your head when you don't want to think about something else because you can make it as complicated as you need to fill your brain by making the board as big as you want and the moves as complicated as you want" (Mark Haddon 2003, pp. 148-149).
[edit] References
- E. Berlekamp, J. Conway and R. Guy, Winning Ways for Your Mathematical Plays, 2nd ed., Vol. 4, Chap. 23: 803--841, A K Peters, Wellesley, MA, 2004.
- R. Honsberger, A problem in checker jumping, in Mathematical Gems II, Chap. 3: 23--28, MAA, 1976.
- H. Eriksson and B. Lindstrom, Twin jumping checkers in Z_d, Europ. J. Combinatorics, 16 (1995), 153–157.
