4
$\begingroup$

There is an infinite chessboard. The chessboard is divided in two by a horizontal line that extends indefinitely. Above the dividing line, the cells of the chessboard must remain empty. Below you can place as many pawns as you like in any way you like. To move a pawn you perform the following move: a pawn jumps over an adjacent pawn to an empty cell. The pawn that was stepped over is eaten and disappears from the chessboard while the one that jumps can only do so horizontally or vertically but not diagonally. Evidently, there cannot be two pawns per cell. Also, a pawn cannot move unless it eats another pawn.

For example, if there is a pawn in cell B1 and a pawn in cell C1, then the pawn in B1 can jump to the right into the cell D1 by eating the pawn in C1, which is removed from the board. Similarly, the pawn in C1 can eat the pawn in B1 by jumping into cell A1.

The goal is to get a pawn as high as possible above the horizontal dividing line. What is the highest line above the horizontal dividing line that can be reached?

Improve this question
$\endgroup$
10
  • 6
    $\begingroup$ This sounds more like peg solitaire than life. $\endgroup$
    – fljx
    Commented Nov 30, 2022 at 15:06
  • 2
    $\begingroup$ This is a classic puzzle which I would have thought had been discussed on PSE before, but I can't find it. It is best known as rot13(Pbajnl'f Fbyqvref). $\endgroup$
    – Jaap Scherphuis
    Commented Nov 30, 2022 at 15:54
  • 1
    $\begingroup$ Rot13 encoding is easily encoded/decoded using rot13.com. It is often used here avoid spoilers in comments. $\endgroup$
    – Jaap Scherphuis
    Commented Nov 30, 2022 at 15:57
  • 1
    $\begingroup$ Does this answer your question? Checkers with the devil $\endgroup$
    – Ankoganit
    Commented Nov 30, 2022 at 18:46
  • 2
    $\begingroup$ As fljx noted, this is not game of life. It's a pity this question is titled as such, but I guess it's OP's right in this case. $\endgroup$
    – justhalf
    Commented Dec 4, 2022 at 3:32

2 Answers 2

Reset to default
6
$\begingroup$

This is the classic Conway's Soldiers problem, but not a duplicate of Checkers with the devil because diagonal jumps are not permitted. The highest reachable row above the line with a finite number of moves is the fourth.

The same weighting argument applies: a target square on the fifth row has weight 1 and all other squares have weight $\varphi^{\text{Manhattan distance to target}}$ (where $\varphi$ is the inverse of the golden ratio, not the golden ratio itself). No move can increase the total weight of all occupied squares, but the target configuration has weight 1, as does the configuration where the whole lower half-plane is filled with pawns. Thus no finite sequence of moves can bring a pawn to the fifth row – although an infinite process of moves suffices.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The question doesn't specify that infinite sequence of moves is not allowed. So I guess technically the answer is fifth, then? $\endgroup$
    – justhalf
    Commented Dec 1, 2022 at 3:07
  • $\begingroup$ It is inaccurate to describe the process given in that paper as a "sequence". Indeed, the paper references an earlier result that showed that no sequence, even if indexed over ordinals, not just natural numbers, can reach the fifth row. Ordinals only have infinite ascents. Any decreasing sequence must be finite. But their process requires infinite descents. This is why they structured it with time as a real variable, even though the set of times where changes are made is only countably infinite. $\endgroup$
    – Paul Sinclair
    Commented Dec 2, 2022 at 21:46
1
$\begingroup$

The explanation:

A pawn can jump through another, so if the goal is to just go forward from the top left corner (emphasis on top), give a value to each occupied cell depending on the vertical + horizontal distance $x+y$ from this corner ($F_n$ to the $n$th "farthest"). The more pawns are used, the more chance to go farther, so we can assume all cells are occupied, or at least there's a perfect rectangle. $F_{n+1}/F_n$ converges to $[sqrt(5)+1]/2$, making $(F_n+F_{n-1}+...+1)/F_n$ converge to $[sqrt(5)+3]/2$. $(F_n+2F_{n-1}+...+2)/F_n$ (first line starting from both sides) converges to $sqrt(5)+2$. The entire rectangle converges to $[sqrt(5)+2]*[sqrt(5)+3]/2 = [sqrt(5)+11]/2$. This is between the fifth and sixth powers of $[sqrt(5)+1]/2$, so we can move at most five squares ahead given infinite pawns.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "close the gaps" - The pawns only jump, like solitaire. They can't just step forward without jumping. $\endgroup$
    – Jaap Scherphuis
    Commented Nov 30, 2022 at 15:48
  • $\begingroup$ Corrected my answer. $\endgroup$
    – Nautilus
    Commented Dec 6, 2022 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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