Conway's Soldiers Explained

Conway's Soldiers or the checker-jumping problem 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 sequence of moves that will allow a soldier to advance more than four rows above the horizontal line. His 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 argument has been reproduced in a number of popular math books.

Simon Tatham and Gareth Taylor have shown that the fifth row can be reached via an infinite series of moves. If diagonal jumps are allowed, the 8th row can be reached, but not the 9th row. In the n-dimensional version of the game, the highest row that can be reached is

3 n -2 ; Conway's weighting argument demonstrates that row 3 n -1 cannot be reached.

Conway's proof that the fifth row is inaccessible

Notation and definitions

Define

\varphi = (\sqrt{ 5)/(-1 }{ 2 }) ≈ 0 . 6180339887 \ldots . (In other words, \varphi here denotes the reciprocal of the golden ratio.) Observe that \varphi ^{2} = 1 - \varphi .

Let the target square be labeled with the value

\varphi ^{0} = 1 , and all other squares be labeled with the value \varphi ^{n} , where n is the Manhattan distance to the target square. Then we can compute the "score" of a configuration of soldiers by summing the values of the soldiers' squares. For example, a configuration of only two soldiers placed so as to reach the target square on the next jump would have score \varphi ^{1} + \varphi ^{2} .

When a soldier jumps over another soldier, there are three cases to consider:

1. When a soldier jumps towards the target square: Let the value of the soldier's square be

\varphi ^{n} for some n , and the value of the square he jumps over be \varphi ^{n-1} ; then the total change in score after the jump is \varphi ^{n-2} - \varphi ^{n-1} - \varphi ^{n} = \varphi ^{n-2} ( 1 - \varphi - \varphi ^{2)} = 0 .

1. When a soldier remains the same distance from the target square after his jump: In this case the change in score is

\varphi ^{n} - \varphi ^{n-1} - \varphi ^{n} = - \varphi ^{n-1} .

1. When a soldier jumps away from the target square: Here the change in score is

\varphi ^{n+2} - \varphi ^{n+1} - \varphi ^{n} = \varphi ^{n(\varphi} ^{2} - \varphi - 1 ) = -2 \varphi ^{n+1} .

So, no jump will ever increase the configuration's total score.

Computing the score of the initial configuration

Consider now a starting configuration where only one infinite horizontal line is completely filled with soldiers.

If this horizontal line of soldiers is immediately below the target square, then the score of the configuration is

\varphi + 2 \varphi ^{2} + 2 \varphi ^{3} + \ldots . The score of a line two spaces below the target square is \varphi ^{2} + 2 \varphi ^{3} + 2 \varphi ^{4} + \ldots = \varphi(\varphi + 2 \varphi ^{2} + 2 \varphi ^{3} + \ldots) . The score of a line three spaces below is \varphi ^{2(\varphi} + 2 \varphi ^{2} + 2 \varphi ^{3} + \ldots) , and so on.

Consider the full starting configuration, where soldiers fill the whole half-plane below the red line. This configuration's score is the sum of the scores of the individual lines. Therefore, if the target square is immediately above the red line, the score is

S _{1} = (\varphi + 2 (\varphi ^{2} + \varphi ^{3} + \varphi ^{4} \ldots))( 1 + \varphi + \varphi ^{2} + \varphi ^{3} + \ldots) .

At this point, observe another interesting property of

\varphi , namely that \sum ^{inf ty} _{n =2} \varphi ^{n} = 1 . Applying this identity producesS _{1} = (\varphi + 2 )( 1 + \varphi + 1 ) = (\varphi + 2 ) ^{2} = 5 + 3 \varphi ≈ 6 . 85410 \ldots .

If the target square is in the second row above the red line, every soldier is one space further from the target square, and so the score is

S _{2} = \varphi S _{1} = 3 + 2 \varphi .

Similarly:

S _{3} = \varphi S _{2} = 2 + \varphi ,S _{4} = \varphi S _{3} = 1 + \varphi ,S _{5} = \varphi S _{4} = 1 .

When a soldier reaches the target square after some finite number of moves, the ending configuration has score

E = \varphi ^{0} + \epsilon , where \varphi ^{0} represents the contribution of the soldier on the target square and \epsilon represents the (small, but positive) contributions of the infinite number of soldiers that remain elsewhere on the plane.

Thus, we have shown that when the target square is in the fifth row above the infinite half-plane of soldiers, the starting configuration's score is exactly

S _{5} = 1 ; the ending configuration's score is E = 1+ \epsilon ; and since no kind of jump ever increases the score, we must have S _{5\ge} E . This is a contradiction; Q.E.D., it is impossible for any soldier to reach a square in the fifth row after a finite number of jumps.

References

^{[1] [2] [3] [4]}

• 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.

External links

• cut-the-knot.org explains the game
• A page describing several variations of the game, with recent references
  • Interactive version of the game (1)
• Interactive version of the game (2)
• Plus online magazine describes the game

Notes and References

1. Bell . George I. . Hirschberg . Daniel S. . Guerrero-Garcia . Pablo . The minimum size required of a solitaire army . INTEGERS: Electronic Journal of Combinatorial Number Theory . 2007 . 7 . G07. math/0612612.
2. Eriksson. Henrik. Lindstrom. Bernt. Twin jumping checkers in \Bbb Z ^{d} . European Journal of Combinatorics. 16 . 1995 . 2 . 153–157. 10.1016/0195-6698(95)90054-3. free.
3. Web site: Simon Tatham . Simon Tatham . Reaching row 5 in Solitaire Army (web version) .
4. Web site: Simon Tatham . Simon Tatham . Gareth Taylor . Reaching Row Five in Solitaire Army .