## Fun Fact - Jumping Pegs

Take a traditional Battleship game and place 25 pegs in the lower left quadrant, rows F through J and columns 1 through 5. If you don't have a Battleship game, place 25 pennies in the lower left region of a checkerboard. The bottom row of the checkerboard is row J, and the left column is column 1. However, since the checkerboard only has 8 rows, not 10, you will have to pretend there is another row, i.e. row B, just above the checkerboard.

A peg moves by jumping over another peg and landing in an empty hole, whereupon the jumped peg is removed. Moves are always vertical or horizontal. Find a sequence of moves that leaves a peg in row B. For example, G5 jumps F5 to land in E5, and the peg at F5 is removed. This puts a peg in row E. Next, F3 jumps to F5, jumps to D5, which puts a peg in row D. You are looking for a sequence of moves that pushes a peg all the way up to row B. Pause, and try to solve the puzzle.

Answer: Here are the coordinates of the jumping pegs, in order.

G3 F5 F3 H4 H5 F5 I3 G3 E3 G2 G1 E1 I2 I1 G1 I5 J3 H3 F3 D3

Now that we know we can get to row B, prove that it is not possible to reach row A, even if the rows are infinite left to right, and even if there are infinitely many rows below row E. You have an entire half plane of pegs to work with, and yet you still can't get to row A.

I'll start with a hint, and then give the solution. Proving a negative is always difficult. It's a completely different mindset. The classic example from topology is that a sphere, made of perfectly stretchable rubber, cannot be deformed into a torus, i.e. an innertube. A ball and an innertube are just different shapes. That's pretty intuitive, but how can we prove it? Poincaré showed us the way. Look for a property of a shape that does not change as the shape is stretched and twisted and deformed. If this property is different for the sphere and the torus, then one cannot be stretched into the other. He found such a property, and thus proved a negative assertion in mathematics. The sphere and the torus are indeed different shapes. We want to do the same thing here. Look for a property of the entire board that does not change with a jump, yet the start position, a half plane of pegs below row E, and the end position, at least one peg in row A, produce different values for this property. That will prove a peg cannot reach row A. Pause, and try to complete the proof.

Answer: Suppose a peg reaches A0. Assign a value to every position in the plane as described below. Then, the potential of the board is the sum of the values of all the locations that contain pegs. This potential will be the property that is different from start to finish.

The value of each location is positive, and the sum is absolutely convergent. It doesn't matter how you order the numbers, the sum is the same. Therefore the potential of each board is well defined.

Values are defined in such a way that, after a jump, the potential of the board will not increase. Start with F0, 5 rows below A0. Let the value of F0 be 1. In other words, v(F0) = 1. Other values are based on the golden ratio r, such that r2 + r = 1. Apply the quadratic formula and solve for r. If q is the square root of 5, then r = (q-1)/2. Verify, if you wish, that r2 + r = 1. Set v(F1) = r, and v(F2) = r2, and notice that if F2 jumps over F1, to land in F0, then F1 and F2 are now empty, removing r+r2 from the potential, while F0 now has a peg, thus adding 1 to the potential. The potential is unchanged.

Let v(F3) = r3, v(F4) = r4, and so on down the line. If a peg jumps from F5 over F4 to F3, the potential decreases by r4+r5, and increases by r3. Factor out r3, and the potential changes by r3×(1-r-r2), which is no change at all. In general, any jump along the F line, moving towards F0, leaves the potential unchanged. Of course a jump to the right decreases the potential.

The F row is symmetric about F0. v(F-1) = r, v(F-2) = r2, and so on. If a peg is to the left of F0, and jumps right, the potential is unchanged. If the peg jumps left, the potential decreases. Finally, if a peg jumps across the midline, from one side of F0 to the other, the potential decreases by 1.

At the beginning, the F row is full of pegs. Starting with F0 and moving right, we have 1 + r + r2 + r3 + …, which is a geometric series. Call this s, and use the formula 1/(1-r) to find s. Remember that q is the square root of 5.

r = (q-1)/2

1-r = (3-q)/2

s = 1/(1-r) = 2/(3-q) = (6+2q)/(9-5) = (3+q)/2

The pegs to the left of F0 add up to s-1. Therefore the entire F row has a sum of 2s-1.

Let row G be r times row F. Let row H be r times row G. Let row I be r times row H. Continue this down the plane forever. As an exercise, what is the value of J3? Since v(F0) = 1, descend down to G0, H0, I0, and J0 and find r4. Then move right to J3 and find r7. By symmetry, v(J-3) also equals r7.

The sum of the values across the entire G row is r times 2s-1. The sum across row H is r2 times 2s-1. Take the infinite sum down the plane and obtain s times 2s-1. This is the potential of the board in its start state.

s × (2s-1) = (3+q)/2 × (2+q) = (11+5q)/2

The potential of the board at the start, with a half plane of pegs below row E, is (11+5q)/2, or approximately 11.09. Each move keeps the potential of the board the same, or decreases it. At the end we need a peg in A0, which has a value of 1/r5. Rewrite 1/r as (q+1)/2, then raise this to the fifth and get (11+5q)/2. This is exactly the same as the start potential. The peg at A0 accounts for the value of the entire board. If A0 can be reached, then every move is up or towards the middle, so that the potential of the board never decreases, and at the end there is one peg in A0, and all the other pegs are gone. Obviously this cannot be accomplished by a finite sequence of jumps; there will always be pegs left somewhere on the board. That completes the proof. Row A cannot be reached.

In this construction, r can be no smaller, else a jump from F2 over F1 to F0 would make the potential larger. But what if we increase r just a little bit? That preserves the essence of the proof. As r is increased by ε, s gets a little bit larger, and the board's start potential is larger. At the same time, 1/r is smaller, and 1/r5 is smaller. The value of A0 is smaller, and is within range of the start position. A0 is no longer forbidden. The proof falls apart if r is just the tiniest bit larger. For our purposes, r really is the golden ratio. No other ratio will do. Click here for more applications of the golden ratio, including the Fibonacci sequence.

What if a peg gets to A0 after an infinite number of moves? The entire board is swept clean except for one last peg at A0, thus preserving the potential of the board at (11+5q)/2. Every move is up or towards the middle, so that the potential of the board does not decrease. It must remain at (11+5q)/2 from start to finish. Thus each peg starts at a particular point in the plane, marches inexorably up and to the middle, until, after a finite number of steps, it is finally jumped by another peg and disappears, or in the case of one special peg, it survives and lands on A0.

To avoid Zeno's paradox, moves are made faster and faster, perhaps each taking half as long as the previous, whence all the moves occur in a finite amount of time. That's ok, but the real challenge is defining an infinite sequence of moves. You might decide to jump G0 over F0 to E0, then G1 over F1 to E1, then G2 over F2 to E2, and so on down the line forever. That's an infinite sequence of moves, but you're not done. It is a sequence within the larger sequence. This is allowed under the rules of ordinal arithmetic. After that subsequence is done, you can make another move, and another, and another, such as I0 to G0, I1 to G1, I2 to G2, and so on, building another subsequence that is still part of the larger sequence of moves. The sequence can contain dozens of infinite subsequences, even an infinite number of infinite subsequences. However, the set of pegs is countable, and each move removes a peg, hence the entire sequence is countable. Can we get a handle on this sequence of sequences?

Suppose an infinite number of pegs walk through a given hole. Select the hole that is highest and closest to the midline, with infinitely many pegs passing through it. Each peg must move out of the way to get ready for the next one. Each peg jumps up or towards the middle, or is itself jumped by another peg heading up or towards the middle. At least one of the four holes, the two above or the two towards the middle, has infinitely many pegs passing through it. Remember that the highest central hole is A0, and exactly one peg lands on that hole. This is a contradiction, hence every hole has finitely many pegs passing through it.

Label each peg with its coordinates, so we know where it came from. In other words, each peg has a name, and is uniquely identifiable. A move in the sequence is when a specific peg k in hole t, jumps over another peg l in hole u, and lands in the empty hole v. This move is ready if k is in hole t, and l is in hole u, and the pegs that would pass through v before k have already done so. This move is expired when any future peg lands on t or u, or when any peg after peg k lands on v. The move can be made any time between ready and expired. The moves around it do not interfere with t u or v. This allows some rearrangement of the sequence.

The trick is to show that every move in the sequence could be accomplished in finitely many steps. This is clearly true of the first move, and for every move that is in a finite position within the sequence. Proceed by transfinite induction. Consider a move that carries peg k over peg l, from hole t over hole u to hole v. There is a prior move that makes this move ready. Perhaps that move puts k or l in position, or perhaps it moves a peg out of hole v. This prior move appears earlier in the sequence, and can be accomplished in finitely many steps. Follow this up with the kl move, and it too is accomplished in finitely many steps. This reasoning is valid for every move, including the move that carries a peg from C0 over B0 to A0. The puzzle is solved in a finite number of moves, and that is a contradiction. Therefore there is no solution, even if infinitely many moves are allowed.

Next consider the peg jumping problem in 3 dimensions. The board, as described above, with pieces below row E, lives in the plane of z = 0. Another copy of the board, with pegs below row E, floats above the first board at z = 1. There is another layer at z = 2, and z = 3, and z = -1, and so on. Can we get a piece up to A0? Sure we can. Push a piece of to B0 at z = 0, and do the same at z = 1. Jump B0 z=0 over B0 z=1 to B0 z=2. Within the plane z = 2, push a piece up to C0, then jump over the piece at B0 to land on A0.

Apply the potential proof to limit the distance a piece can travel above the F line. The sum, within z = 0, is s times 2s-1. This is multiplied by 2s-1 to encompass all the layers, i.e. the entire half space of pegs. This is the start potential.

s × (2s-1)2 = (3+q)/2 × (2+q)2 = (47+21q)/2 = 46.978

Move up one row from A0 and the value is 1/r6, or 9+4q. This is well within range of the start potential. Move up another row and you're still ok, but three rows above A yields a value of 1/r8 = (47+21q)/2. This is not accessible by any finite sequence of jumps, nor by an infinite sequence, as per the earlier proof. In 3 dimensions you are limited to the 7 rows above the half space of pegs.

Since 2s-1 = 1/r3, the n dimensional version of this game can push a peg no farther than 3n-2 rows above the half space of pegs. This is true even in one dimension.

In 3 space, is there a sequence of moves that pushes a peg up to the seventh row? There is - take a moment, or perhaps a few hours, and see if you can find such a sequence.

Here is my solution. It's not trivial, and it's probably not the shortest solution, but it uses subroutines, which is how computer programmers think. The goal is to build a column of pegs C5 D5 E5 F5 G5 within the layer z = 1. If this can be done for layer 1, then it can be done for layers 2 3 4 and 5. The result is a 5 by 5 grid of pegs extending up to row C. Use the earlier 20 move construction to push a peg 4 levels above row C, which is the highest row that can be attained. Thus it is sufficient to build a column of pegs from G5 up to C5.

Start by issuing the jumps G5 F7 F5 H6 H7 F7 I5 G5 E5. This pushes a peg up to C5, the top of our column, and it leaves an empty space in the half plane of pegs from I to F in column 5 and from H to F in columns 6 and 7. This looks like Utah upside down, so I will call it the Utah move. If this looks familiar, it's because you have seen it before. It is the start of the 20 move sequence that pushes a peg up 4 rows.

Let's eat away at this gap from below. Jump I7 J5 J7 K5 I5. This lowers the gap by 2 and leaves a peg in G5. To review, column 5 has pegs in C5, G5, and L5 and below. You can do this again if you like, lowering the gap by 2 and leaving a peg in I5. Do this one more time, so that there is a peg in K5. Now column 5 contains C5 G5 I5 K5 P5 and below.

For the first time, mine from the left. Jump L3 L5 J5, leaving the peg in H5. Now we have C5 G5 H5.

Apply the Utah move on its side, clearing a gap in rows F G and H on the right, and pushing F8 over to F5. Then jump G5 over F5 to E5. The column now contains C5 E5 H5.

Apply the Utah move on its side, clearing a gap in rows I J and K on the right, and pushing I8 over to I5. Jump I5 over H5 to G5. The column now contains C5 E5 G5.

Jump I3 J3 J5 H5 F5. The column now contains C5 D5.

Jump F3 G3 H3 G5. The column now contains C5 D5 E5 H5. We are missing F5 and G5.

Apply the Utah move on its side, clearing a gap in rows F G and H on the left, and pushing F2 over to F5. Apply the Utah move again, clearing a gap in rows I J and K on the left, and pushing I2 over to I5. Jump I5 over H5 to G5. That completes the column, C5 D5 E5 F5 G5, and such a column, across 5 levels, pushes a peg 4 rows above C, and 7 rows above F. Mission accomplished. Some quick math shows the solution contains 5×75 + 20 or 395 moves, though there is room for improvement.

The 20 move sequence that pushes a peg 4 rows up does not use all 25 pegs in the 5 by 5 grid. Only the middle layer, z = 3, requires C5 through G5. The other layers use C5 through F5. To accomplish this, start with Utah as before, then jump I3, then another Utah starting at row I and placing a peg in F3. Jump G3 G5 to lplace a peg in E5. perform Utah from the right, then F5 F3 H3 J3 K3 K5 I5 G5, then Utah from the left. This is 47 moves, thus 4×47 + 75 + 20 = 283.

Building the column C5 D5 E5 F5 in the top and bottom layers is easier if you use the outer layers to help. I'll illustrate with z = 5, the top layer. Perform Utah as before, then F3 G3 G5, giving C5 and E5. Fill in F5 by jumping F5 z=7 over F5 z=6 into F5 z=5. Then, within z = 6, jump F3 G5 F7 F5, producing D5. Do the same within z = 7, and jump D5 from z=7 to z=5. That completes the column in just 22 moves. The sequence is now 2×22 + 2×47 + 75 + 20 = 233 moves.

Jump G3 in layers 6 and 7, to fill in the G5 line, then perform Utah entirely within the G plane to push a peg from G5 z6 down to G5 z3. This consumes 11 moves, but it means we didn't have to fill in G5 in z3. We could have set that column to C5 D5 E5 F5, as we did with z2 and z4. The sequence is now 2×22 + 3×47 + 11 + 20 = 216 moves. I can eke out another three moves, but it probably isn't worth explaining. If you can do this in less than 200, please let me know.