Jumping Pegs

Copyright © Karl Dahlke, 2023

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.

12345678910
A
B
C
D
E
F ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
G ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
H ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
I ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
J ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น

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, G3 jumps F3 to land in E3, and the peg at F3 is removed. This puts a peg in row E. Next, F5 jumps to F3, jumps to D3, 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

Leaves the board looking like this.

12345678910
A
B ๐Ÿ”น
C
D
E
F
G
H
I
J ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น

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. You have an entire half plane of pegs to work with, and yet you still can't get to row A. This is a bit surprising, at first, until you think about it for a while. The proof is quite beautiful.

I'll start with the approach, in general, 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 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. It might decrease, but it 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. r = (sqrt(5)-1)/2. r is about 0.618. 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. This is the same as 1/r2. s = 2.618 (approx)

The pegs to the left of F0 add up to s-1. Therefore the entire F row has a sum of 2s-1, about 4.236. To be precise, 2s-1 = 2/r2 - 1 = (2-r2)/r2 = (1+r)/r2. Multiply top and bottom by r and get (r+r2)/r3, or 1/r3. The F row contributes 1/r3 to the potential of the board.

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, which is 1/r5, approximately 11.09. This is the potential of the board in its start state.

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. 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. We cannot reach A0 in finitely many steps, or from a finite board.

Infinitely Many Moves

If you are in to set theory and ordinals, you might think there is more work to do, and perhaps there is. Row A can't be reached in finitely many moves, true, but 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.09. Every move is up or towards the middle, so that the potential of the board does not decrease. It must remain at 11.09 from start to finish. 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.

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 walks through a given hole t. It follows that infinitely many pegs pass through the hole above t, below t, left, or right. Suppose there are infinitely many moves heading down through t. That subtracts a fixed potential from the board infinitely often. The board has a finite potential, and always โ‰ฅ 0, so this is a contradiction. The same happens with infinitely many moves to the left; just put the midline somewhere to the right. The same happens with infinitely many moves to the right; just put the midline somewhere to the left. Finally, select a hole t that is highest, having infinitely many pegs passing through it, and traveling up. There is a limite, because lines above the A line cannot be reached. The hole u, just above t, has infinitely many pegs passing through it, but not traveling up. The moves through u go in a different direction, and that is a contradiction. Therefore, 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 only happens once, as l is taken off the board. This move becomes ready when k is in hole t, and l is in hole u, not to move again until the kl jump, and the pegs that would pass through v, prior to this move, have already done so. This is where we need finitely many pegs to pass through each hole. 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 move appears earlier in the sequence, and can be reached 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.

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, does it not? 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.

A Fun Infinite Sequence

Jump G1 over F1 to E1, and jump G3 over F3 to E3, and jump G5 over F5 to E5, and so on down the line for all the odd numbers. This is an infinite subsequence in the larger sequence. Next jump F0 to F2 to F4 to F6 to F8 and so on down the line. Next jump G0 to G2 to G4 to G6 to G8 and so on down the line. At the end, the peg that was originally in F0 is gone, even though it was never jumped. It isn't in any one place on the board. It's value decreases as it marches ever to the right. The value of those holes drop off geometrically. Since its value approaches 0, there is no harm in ignoring it when we calculate the board's potential. The books will balance. The same is true of the peg originally in G0.

As we proved earlier, every move in this sequence can be made in a finite number of steps.

Assume a peg k moves infinitely often in our sequence. It is never jumped, yet it has no specific location. If k is confined to a region, say a thousand rows and a thousand columns, then it passes through at least one hole infinitely often. This is a contradiction, thus it only dwells in this region for a finite amount of time. Pick a larger region, and k is only there for a finite time. As regions increase, k is beyond them for most of the sequence. This is the definition of "approaches infinity". Our peg k approaches infinity, and its value approaches 0. We can safely ignore it when computing the board's potential. The books will balance.

Shortest Sequence

We know that a sequence of moves places a peg in row B - what is the shortest sequence? Obviously such a sequence ends in B, perhaps B0, and it ends by jumping D0 over C0 to B0. Suppose this sequence causes a peg k to jump and land in a hole v, whence k does not jump again, and is not jumped. Let k be the last such peg in this sequence having this property. k in hole t jumps over l in hole u, to land in v, and stays in v thereafter. Nothing later in the sequence touches v. In an effort to build a shorter sequence, let's assume this move is not made. If no future peg lands in t or u, then we are done.

Suppose, further down the sequence, peg m lands in either t or u. Without loss of generality, say m lands in hole t. Oops, m is now blocked by peg k, which did not move out of the way.

think of t as t0, u as u0, and v as v0. m lands in t0 but it doesn't stay there, it jumps away, or is jumped, perhaps on the very next move, or perhaps 100 moves later. When the time comes, let k take this action instead. We want the sequence to continue as before. It doesn't matter if we use k or m.

Think of m as k1. It lives in hole t1, and jumps over l1 in hole u1, to land in hole v1, which is also known as t0. We can't make this move, because v1 is blocked. So don't make this move either. We're done, unless some other peg k2 lands on t1 or u1. If that happens, don't make that move, let k1 or l1 stand in for k2 the next time that peg moves or is jumped, and mark t2 and u2 as blocked. When any peg lands on a blocked hole, don't make that move, and mark two more holes as blocked.

Here is an illustration. Move 80 jumps G3 over F3 to E3, and that peg doesn't move again. Move 81 jumps G5 over G4 to G3, but if we didn't make move 80, then G3 is blocked, and we don't make move 81 either. Move 82 jumps G2 over G3 to G4; this too is blocked. It's easy to see how several moves in a row could be blocked.

At each step, the original move can proceed, or is blocked. If it proceeds then there are two holes left behind, in the original sequence and in the modified seequence. If it is blocked, two holes have pegs, that use to be empty. Never is there an empty hole that use to have a peg in it.

As we consider the next move, the two pegs that would participate in the jump are there. We make this move, iff the third hole is vacant.

At the end of the original sequence, the modified sequence is shorter. This is a contradiction, hence there is no peg k that jumps and then remains - other than the peg in B0 of course.

The final picture has a peg in B0, and no other pegs above the F line, and quite a few holes below the E line. Each hole represents a peg removed, but one of those pegs removed sits at B0. The number of moves is the number of holes minus 1. This is indeed the case in our example, where 20 moves places a peg at B0, and leaves 21 holes behind. A 4 by 5 grid of holes, and one hole in the J line.

The peg in B0 adds a potential of 1/r4 to the board; the holes must subtract at least this much to balance the books. Start with the highest value, which is 1, and work down. Use a calculator if you wish; it's easier than algebra.

1 + 3r + 5r2 + 7r3 + 3r4 = 1/r4

That's 19 holes, or 18 moves. We need at least 18 moves, and we did it in 20, so that's pretty good, and probably minimal.

Three Dimensions

Let's 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 earlier proof to limit the distance a piece can travel above the F plane. Recall that 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. It is 1/r8, approximately 46.978.

Move up one row from A0 and the value is 1/r6. The next row is 1/r7, and the next row is 1/r8. This is exactly the potential of our 3 dimensional board. 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 construct 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.

12345678910
A
B
C ๐Ÿ”น
D
E
F ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
G ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
H ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
I ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
J ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น

9 jumps, in a prescribed order, push a piece 3 rows up, and leave an empty Utah space behind. In reality, the peg that was in I5 went all the way up to C5, but I like to think of it, metaphorically, as pushing F5 up to C5.

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 Utah gap by 2 and leaves a peg in G5. To review, column 5 has pegs in C5, G5, and L5 and below. Do this again, 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.

12345678910
A
B
C ๐Ÿ”น
D
E
F ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
G ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
H ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
I ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
J ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
K ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
L ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
M ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
N ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
O ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น
P ๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น๐Ÿ”น

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 surely 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. That is easier to attain. Recall the 20 move sequence that pushes a peg up to B5. Make 19 of the 20 moves, leaving pegs in C5 and D5. Now assume a peg somehow appears in G5 after x moves. perform Utah from the right, pushing F8 to F5, Then G5 over F5 to E5. Finally Utah from the left, pushing F2 to F5. That's 38+x moves.

The in-plane method to produce G5 is K3 K4 I3 L5 J5 K7 K6 I7 I5. x = 9, and we populate F5 through C5 in 47 moves. That's 75 + 4*47 + 20 = 283 moves.

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 over to G5 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 after all. 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. Order is important here. We have to do the outer layers, z1 z5, with help from above and below, then the middle layers, z2 z3 z4, then the Utah in the G plane to set G5 z3.

Revisit the sequence of 47 moves, and try to create G5 from another plane. Look at the layers below. Jump G3 over to G5 in layers 0 and -1 to fill in the G5 line, then make 3 moves entirely within the G plane to push a peg from G5 z0 up to G5 z2. x is 5, thuse layer 2 is done in 43 moves.

The G plane is spent in layers 6 and 7 and beyond, so inject G5 this way. 3 moves in the H plane pushes a peg to H5 z4, then within z4, J7 K5 I5. Thus x = 6. That's 44 moves. The sequence is now 22 + 43 + 47 + 44 + 22 + 11 + 20, which is 209.

Let's eke out one more. Within the G plane, we made two moves, then Utah, to place G5 at z=3, because that layer needs G5 through C5. That was 11 moves, but we can do it in 9. Jump G3 over to G5 in layers 6 and 7, as we did before, then 3 moves in the G plane sets G5 in z4. Jump I5 to G5 in z6, then within the g line, z9 to z7 to z5 to z3 This saves two, but downstream it costs one. Remember that we injected H5 at z=4 in 3 moves. Now we have to jump H3 to H5 in z6 to restore the H plane, then the 3 moves to set H5 in z4. 22 + 43 + 47 + 45 + 22 + 9 + 20 = 208.

These ones and twos are fine, but is there a strategy I haven't thought of that would save another 10 or 20? I don't think so. Let's compute the theoretical minimum number of moves to get to layer 7.

The final peg adds 1/r7 to the potential, 29.034. We must subtract this from the potential by the holes in F and below. Start with the hole with the highest value, then work down. F5 z3 is 1. The 5 adjacent pegs are r. The 13 holes in the next pyramid are r2.

1 + 5r + 13r2 + 25r3 + 41r4 + 61r5 + 47r6 = 29.058

The sum of holes is 193. One hole is offset by the peg at the top, so we need at least 192 moves to accomplish this.

Diagonal

We already generalized the peg jumping problem to n dimensions, now let's explore another variation. Assume the pegs jump diagonally, like checkers. For example, G3 jumps over F4 and lands on E5, removing the peg in F4. How far up can we go?

If you play this game on a physical checkerboard, you see that the pieces remain on white squares or black squares, and never the twain shall meet. I will try to get a piece up to A5, thus the pegs in F1, F3, G2, H1, etc, don't matter. Remove all those pegs, so that the remaining pegs have gaps between them.

tilt your head 45 degrees, and the pegs look like a grid with vertical and horizontal jumps. Perhaps we can use some of the earlier machinery - something mathematicians love to do.

Apply the Utah maneuver to (metaphorically) push F4 up to C7. (Actually I1 advances up to C7.) Tilt your head back, and Utah pushes the lead peg up and to the right. Here are the 9 jump points.

G3 H6 F4 J4 I3 H6 I1 G3 E5

Now C7 stands alone. We are going to sneak up below C7 and jump over it to B6. Jump G9 over F8 to E7. Then jump F6 to D8 to B6. B6 stands alone after 12 moves.

Perform Utah from the right, heading up and to the left. This deposits a peg once again in C7. We're not quite ready for Utah though, because G9 is missing. I could fix this from the left in just 3 moves, but I'm going to fix it from the right, because I want to retain J6 for the future. Jump G13 to E11 to G9. That's fine, but now we lost F10. Jump H12 to F10, but now we lost H12 and G11. Jump J14 to H12, but now we're missing G11 and I13. Jump G15 to I13 to G11. Use a 7 move pattern to push K15 up to H12. L16 I17 K15 M13 N18 L16 J14. Finally K11 to I13, and we're ready for Utah. Here are the 9 jump points.

G11 H8 F10 J10 I11 H8 I13 G11 E9

Finally C7 jumps B6 to A5. A5 stands alone after 36 moves.

That's farther than we got before, but I'm still not satisfied, I want to reach row ฮ‘, i.e. the row above A. I have a peg in A5, let's put another in C3. This builds a ladder of alternating pegs heading up to ฮ‘6.

This suggests a Utah up and to the right, pushing F0 up to C3, but we're missing H2 and I1. I want to fill these in, but I don't want to disturb J0, I need that for Utah too. Jump K3 to I1. Jump L0 to J2. Jump M3 to K1 to I3. Use Utah to push M1 up to J4. N0 O3 M1 Q1 P0 O3 P-2 N0 L2. Then J4 jumps I3 to fill in H2. Now Utah is ready.

G-1 H2 F0 J0 I-1 H2 I-3 G-1 E1

We have A5 and C3 after 59 moves.

Let Utah push J6 up to G3. K7 L4 J6 N6 M7 L4 M9 K7 I5

Jump G3 over F2 to E1. We have E1 C3 A5 in a line, after 69 moves.

It's easy from here. Jump K-1 to I-3, J-4 to H-2, G-5 to I-3 to G-1, and F-4 to H-2 to F0 to D2 to B4 to ฮ‘6. We have reached row ฮ‘ in 78 moves. Clearly diagonal goes farther than rectilinear.

A proof, similar to the above, puts a finite cap on our vertical wanderings, but the cap is beyond ฮ‘, so there is still more work to do. I'll present the proof below, but we need to improve it, because ฮ‘ is probably as high as we can go in reality.

Assume the peg that reaches the highest row does so in column 0 or 1. This will establish the midline.

The value of G1 is 1. This continues up and to the right, and up and to the left, in a V pattern, just as it did in the earlier proof. v(F0) = v(F2) = v(E-1) = v(E3) = v(D4) = โ€ฆ = 1. Step down to I1 and the value is r. This continues up along the diagonals. v(H0) = v(H2) = v(F-1) = v(F3) = v(E4) = โ€ฆ = r. The value of K1 is R2, and so on up the diagonals. The value of E1, which is not populated at the outset, is 1/r. The value of C1 is 1/r2, and so on. A jump up and toward the midline does not change the potential of the board. Other jumps reduce the potential. This is all familiar.

Only the alternate holes contain pegs, those that participate in the jups to push a peg up to ฮ‘, or higher. The value of the F line is 2s-1, just as it was before, but there is an extra 1. The G line is (2s-1) times r. The H line is (2s-1) times r2, but there is an extra r2. The I line is (2s-1) times r3. This continues down the board. The infinite sum is (2s-1)/(1-r) + 1 + r2 + r4 + โ€ฆ The first term is (2s-1)/r2, which is the same as 1/r5. The second sum is 1/(1-r2), which is 1/r. Thus the potential is 1/r5 + 1/r, approximately 12.708. 1/r6 is higher than this potential, and is unattainable. This is 11 rows up, row ฮ– in our Greek letter nomenclature. The best we can hope for is ฮ•, 10 rows up.