# A Proof of the Optimal Leapfrogging Conjecture

Sam K. Miller, Arthur T. Benjamin

(August 7, 2023)

##  1 Introduction

Suppose we have some checkers placed in the lower left corner of a Go board,
and we wish to move them to the upper right corner in as few moves as
possible. There are no opponent pieces present, and the pieces move as they
would in the game of Chinese Checkers, where for one move, a piece may either
shift one unit in any direction, or repeatedly leapfrog over other pieces.

Let us consider the Go board as a subset of the non-negative integer lattice
$\mathds{Z}^{2}$. As an example, suppose we have four pieces placed at the
coordinates $(0,0)$, $(1,0)$, $(0,1)$, and $(1,1)$, and wish to move them to
the squares $(9,9)$, $(10,9)$, $(9,10)$, and $(10,10)$. For the pieces to
complete the task in as few moves as possible, the pieces must first be moved
into a configuration such that they may jump over each other in an optimal
way.

We may intuitively attempt lining the checkers up diagonally in what we will
call a snake configuration, that is, moving the pieces to coordinates $(0,0)$,
$(1,1)$, $(2,2)$, and $(3,3)$. By repeating the three-move process of shifting
the backmost piece to the right [$(0,0)\xrightarrow{}(1,0)$], leapfrogging
that piece to the front [$(1,0)\xrightarrow{}(3,4)$], then shifting it right
again [$(3,4)\xrightarrow{}(4,4)$], we can reach our destination in
$4+4+(3\times 7)=29$ moves. We say that the snake configuration has a speed of
2/3 since in 3 moves, it makes a forward progress of 2. (Every piece is
shifted in the direction (1, 1).)

However a faster method exists. We first move the pieces into what we call a
serpent configuration, with the pieces on coordinates $(0,0)$, $(1,0)$,
$(1,1)$, and $(2,1)$. Then we repeat the two-move process of leapfrogging the
backmost piece to the front [$(0,0)\xrightarrow{}(2,2)$] then leapfrogging the
new backmost piece to the front again [$(1,0)\xrightarrow{}(3,2)$], we may
reach our destination in $1+1+(2\times 8)=18$ moves. This is indeed the
fastest way of moving the checkers from the bottom left to the upper right.
See Figure 1. Note that the serpent configuration has a speed of 1, since it
requires only 2 moves to give it a forward progress of 2.

It was proved in [1] that in a wide class of optimization problems on lattice
structures (such as $\mathds{Z}^{n}$), the optimal way to move objects from
one location to another far away location, is to spend most of the time
repeatedly translating very efficient configurations. In their 1993 paper [2],
it was shown by Auslander, Benjamin, and Wilkerson that the maximum speed of
any configuration is 1, there are essentially only three configurations that
achieve this speed, and they have at most four pieces. It was conjectured that
with five or more pieces, the maximum attainable speed is 2/3. In this paper,
we prove that conjecture.

##  2 Abstracting the game

Suppose we have $p$ indistinguishable pieces and wish to move them in the
positive direction over the integer lattice $\mathds{Z}^{n}$. If a piece is
located at coordinate $l\in\mathds{Z}^{n}$, and some other coordinate
$l+e_{i}$ is not occupied by a piece (for unit vector $e_{i}$), then the piece
may shift there. Alternatively if $l+e_{i}$ is occupied but $l+2e_{i}$ is not,
the piece may hop over the occupant of $l+e_{i}$ to land at $l+2e_{i}$, where
it may remain or continue hopping over other adjacent pieces. One legal move
consists of either a shift or a jump, a sequence of one or more hops by a
single piece.

Figure 1: An example of the serpent’s $2$-move trajectory, consisting of 2
jumps. The placements in the leftmost and rightmost diagrams are translates,
and represented by the same configuration, the serpent. These two placements
have displacement 2, and require 2 moves to reach one from the other. Hence,
the serpent is a speed of light configuration, i.e. it has speed 1.

Define a placement of size $p$ as a finite subset of $\mathds{Z}^{n}$, denoted
by $X=\\{\vec{x}_{1},\dots,\vec{x}_{p}\\}$. Define the centroid of placement
$X$ to be

$c(X)=\frac{1}{p}\sum_{u=1}^{p}\vec{x}_{u}.$

For placements $X,Y$, define their displacement as

$d(X,Y)=\sum_{i=1}^{n}|c_{i}(X)-c_{i}(Y)|.$

For $m\geq 1$, an m-move trajectory $X_{0},X_{1},...,X_{m}$ is a sequence of
placements where $X_{u+1}$ is reachable from $X_{u}$ in a single legal move.
The speed of an $m$-move trajectory from $X_{0}$ to $X_{m}$ is

$s=\frac{d(X_{0},X_{m})}{m}.$

We say that placements $X,Y$ are translates if there exists
$\vec{a}\in\mathds{Z}^{n}$ such that $X+\vec{a}=Y$. We say that translates $X$
and $Y$ are represented by the same configuration of pieces, and define the
speed of a configuration $C$ to be the maximum speed attained by any
trajectory between two translates represented by $C$.

Auslander, Benjamin, and Wilkerson proved in 1993 the following: the maximum
speed of any configuration $C$ is 1, and that only three configurations
(called speed of light configurations) attain this speed in $\mathds{Z}^{n}$
for $n\geq 1$.[2] These configurations are:

  * •

The atom {$x$} (if $p=1$).

  * •

The frog {$x$, $x+e_{i}$}, $1\leq i\leq n$ (if $p=2$).

  * •

The serpent {$x$, $x+e_{i}$, $x+e_{i}+e_{j}$, $x+2e_{i}+e_{j}$} $1\leq i\neq
j\leq n$ (if $p=4$ and $n>1$).

It was conjectured that the maximum attainable speed for any configuration on
$p\neq 1,2,4$ is $2/3$, which we may observe is attained by the snake
configuration with any number of pieces.[2] We will show that in
$\mathds{Z}^{2}$, aside from these speed of light configurations, the maximum
achievable speed is $2/3$.

##  3 Definitions and Properties

Let $m\in\mathds{Z}$ and placement $X\in\mathds{Z}^{n}$. Then border $l_{m}$
is defined by:

$l_{m}=\\{x\in X:||x||=m\\}.$

For a placement $X$, we may define the tail (respectively, head) of $X$, by
$t(X)=\min_{u}$ $|l_{u}|\geq 0$ (respectively, $h(X)=\max_{u}$ $|l_{u}|\geq
0$). Define the width of a placement $X$ $w(X)=h(X)-t(X)+1$. Define the back
border (respectively, front border) of $X$ as $T(X):=l_{t(X)}$ (respectively,
$H(X):=l_{h(X)}$).
For example, if in the first diagram in Figure 1, the lower left piece is at
$(0,0)$, then its configuration has a tail of 0 and a head of 3.

We now define an underlying configuration which reoccurs in optimal play. A
ladder of length $k>0$ is subset of a placement $X$:
$L=\\{p_{0},p_{1},...,p_{k}\\}\subseteq{X}$ such that $p_{0}$ is able to hop
over $p_{1},\dots,p_{k}$ successively. If $\\{p_{0}\\}=T(X)$ and $p_{k}\in
H(X)$, then we say $L$ is a true ladder of $X$. We call the move consisting of
$p_{0}$ jumping over the rest of the ladder pieces a climb, call $p_{0}$ the
base of the ladder, and the other pieces the rungs.

$p_{0}$$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$ Figure 2: An example of a placement
$X$ which contains a ladder. The ladder is
$\\{p_{0},p_{1},p_{2},p_{3},p_{4}\\}$, with $p_{0}$ is the base of the ladder,
and pieces $p_{1},p_{2},p_{3},p_{4}$ are the rungs. Here $\\{p_{0}\\}=T(X)$
and $\\{p_{4}\\}=H(X)$, so the ladder is a true ladder of $X$. $X$ has width
8.

######  Proposition 3.0.1.

If a configuration $X$ contains a true ladder $L$, $X$ has even width.

###### Proof.

Observe that when a piece $p$ hops over another piece $p^{\prime}$, then $p$
either increases or decreases its border by 2. Therefore since $l_{0}$ jumps
from $B_{t(X)}$ to $B_{h(X)+1}$, this implies $h(X)+1-t(X)$ is even. ∎

######  Proposition 3.0.2.

A placement $X$ with more than one piece can perform a move that
simultaneously increases $t(X)$ and $h(X)$ if and only if it has a true
ladder.

###### Proof.

$(\impliedby)$Performing a ladder climb increases both $t(X)$ and $h(X)$, as
$l_{0}$ moves from $T(X)$, leaving that border empty, and jumps in front of
$l_{k}\in H(X)$, thus advancing the front border.

$(\implies)$ If a move on $X$ exists that advances the front and back borders
forward, since only one piece can change positions, the back border must only
have one piece, and it must be the piece which moves. Call this piece $p$.
Since $X$ has more than one piece, $w(X)>1$, so $p$ must jump from $T(X)$ to
in front of $H(X)$. Denote the sequence of pieces hopped over by $p$ by
$p_{1}$, $p_{2}$, … $p_{k}$. Since $p_{k}\in H(X)$,
$\\{p_{0},p_{1},...,p_{k}\\}$ is a true ladder. ∎

We may classify possible moves into seven categories.

  * •

Ascent: A move that increases $h(X)$ and $t(X)$. This is necessarily a ladder
climb.

  * •

Front Push: A move that increases $h(X)$ but not $t(X)$.

  * •

Back Push: A move that increases $t(X)$ but not $h(X)$.

  * •

Dead Move: A move that changes neither the tail nor head of $X$.

  * •

Front Retreat: A move that decreases the head of $X$.

  * •

Back Retreat: A move that decreases the tail of $X$.

  * •

Reverse Ascent: A move that decreases both the head and the tail of $X$.

For example, in the placement in Figure 2, $p_{0}$ climbing the ladder would
be an ascent. $p_{4}$ shifting to the right would be a front push. $p_{0}$
jumping over $p_{1}$ and $p_{2}$ only would be a back push. $p_{5}$ shifting
in any direction would be a dead move.

An ascent is necessarily a ladder climb for nontrivial placements. For a legal
$m$-move trajectory $M=\\{X_{0},X_{1},...,X_{m}\\}$, where $X_{0}$ is a
translate of $X_{M}$, define the moveset of $M$ as a collection of moves
$m(M)=\\{x_{0}\to x_{0}^{\prime},$ … $,x_{m-1}\to x_{m-1}^{\prime}\\}$, where
$x_{i}$ is the location of the piece that moves in $X_{i}$, and
$x_{i}^{\prime}$ is the location of the moved piece in $X_{i+1}$.

######  Proposition 3.0.3.

In any moveset, the total number of front pushes, back pushes, front retreats
and back retreats which occur between two ascents must be even.

###### Proof.

Since ascents can only occur when a configuration has even width, the
configurations immediately before and after any ascents must have even width.
Therefore, the number of moves between two ascents which change the width
parity must be even. The four listed move types are the only move types which
change the parity of the width of a configuration, so the result follows. ∎

For a move trajectory $M$, let $A(M)$ represent the number of ascents in
$m(M)$, $FP(M)$ represent the number of front pushes, $BP(M)$ the number of
back pushes, $DM(M)$ the number of dead moves, $FR(M)$ the number of front
retreats, $BR(M)$ the number of back retreats, and $RA(M)$ the number of
reverse ascents.

Now, define the weight $\omega(M)$ of a trajectory $M$ or its corresponding
moveset $m(M)$ as follows:

$\omega(M):=A(M)-(1/2)\cdot(FP(M)+BP(M))-2\cdot
DM(M)-(7/2)\cdot(FR(M)+BR(M))-5\cdot RA(M)$

This definition rewards (with higher weight) trajectories that make many
efficient moves (e.g. ascents) and penalizes trajectories that use moves that
make little forward progress or worse. For example, consider the trajectory
where we begin with a snake with 5 pieces, located at points
$\\{(0,0),(1,1),(2,2),(3,3),(4,4)\\}$, and in 3 moves (consisting of one back
push, one ascent, and one front push), translate it to the points
$\\{(1,1),(2,2),(3,3),(4,4),(5,5)\\}$. Such a trajectory, with speed 2/3,
would have weight $1-(1/2)(1+1)=0.$ Additionally, call the coefficient
corresponding to each move type the move weight. If a sequence of moves are
performed, then the weight of the sequence is the sum of all the move weights.
If we partition a trajectory $M=M_{1}\oplus M_{2}\oplus...\oplus M_{k}$, then
$\omega(M)=\omega(M_{1})+...+\omega(M_{k})$.

######  Lemma 3.1.

A $m$-move trajectory $M$ of a configuration $C$ has speed greater than $2/3$
if and only if $\omega(M)>0$

###### Proof.

Since the move types are mutually exclusive,
$A(M)+FP(M)+BP(M)+DM(M)+FR(M)+BR(M)+RA(M)=m$. Additionally, the displacement
of $M$ can be characterized by
$A(M)-RA(M)+(1/2)\times(FP(M)-FR(M)+BP(M)-BR(M))$. Therefore the speed of $M$
is

$\frac{A(M)-RA(M)+FP(M)/2-FR(M)/2+BP(M)/2-BR(M)/2}{A(M)+FP(M)+BP(M)+DM(M)+FR(M)+BR(M)+RA(M)}.$

It is straightforward to check:

$2/3<\frac{A(M)-RA(M)+FP(M)/2-FR(M)/2+BP(M)/2-BR(M)/2}{A(M)+FP(M)+BP(M)+DM(M)+FR(M)+BR(M)+RA(M)}\iff
0<\omega(M).$

∎

We next introduce an important theorem which, as a corollary, demonstrates
that most movesets do not have speed greater than 2/3.

######  Theorem 3.2.

For any trajectory $M$ with no two ascents occurring in a row and not both
beginning and ending with an ascent, $\omega(M)\leq 0$.

###### Proof.

After an ascent, if a front push, back push, front retreat, or back retreat
occurs, this changes the width of the placement, and since prior to the first
move the placement had even parity, for another ascent to occur, another one
of the listed moves must occur.

Without loss of generality let us assume $M$ begins with an ascent, therefore
it cannot end with one. Let us partition the moveset $m(M)$ into separate
blocks $B_{1},\dots,B_{k}$ where each block begins with an ascent and contains
no other ascents. Since no two ascents can occur in a row, each block must
consist of at least two moves. Additionally since each new block must begin
with an ascent, a block must end with a placement with even width.

$B_{i}$ contains one ascent and at least one other move $a$. If $a$ is any
type of move besides a front or back push, $\omega(B_{i})$ is negative.
Otherwise, if $a$ is a front push or back push the resulting placement has odd
width and another front push, back push, front retreat, or back retreat must
occur. This implies $\omega(B_{i})\leq 0$, with equality holding only when
$B_{i}$ is of the form $\\{A,FP/BP,FP/BP\\}$. Since $B_{i}\leq 0$ for all
$1\leq i\leq k$, $\omega(M)\leq 0$, as desired.

∎

Since we know that the maximum speed of a configuration is 1, and we are
looking at non-maximal configurations, every moveset has at least one non-
ascent move. Therefore, we will assume for the remainder of this paper that
the last move in any moveset is not an ascent.

##  4 $p=1,2,4$

For a configuration which is not speed of light, observe that it may reach
speed arbitrarily close to speed 1 by first shifting into a speed-of-light
configuration, repeating its set of moves sufficiently long, then moving back
to the original configuration. We will consider only trajectories which do not
use this strategy. Rigorously, if a trajectory between translates does not
perform any moves corresponding to any “speed-of-light” configuration’s
optimal moveset, call the corresponding configuration non-speed-of-light.

######  Theorem 4.1.

A non-speed-of-light configuration $C$ with 1, 2, or 4 pieces cannot have
speed greater than 2/3.

###### Proof.

When $p=1$, this is immediately true, since there is only one configuration,
and it can translate itself with speed 1 or - 1.

For $p=2$, any trajectory containing a jump (which must be an ascent) must
contain the frog’s optimal trajectory (a jump), therefore any non-speed-of-
light configuration is limited to only shifts. Therefore, the optimal
trajectory of $C$ cannot contain any ascents, thus $C$ cannot have speed
greater than 2/3.

For $p=4$, if $C$ has optimal trajectory without two ascents in a row, $C$ has
speed at most 2/3. Suppose then that $C$ has two ascents in a row, without
loss of generality let us assume its trajectory begins with two ascents. $C$
must have even width, and every border must contain a piece due to the parity
of the ends of each successive ladder. Since $C$ can perform two ascents in a
row, it has width 4. $C=\\{p_{1},p_{2},p_{3},p_{4}\\}$ with $p_{i}$ on
$l_{i}$. Say $p_{1}$ has jump
$p_{1}:\xrightarrow{p_{2}}a_{1}\xrightarrow{p_{4}}a_{2}$ for open locations
$a_{1},a_{2}$. $d(p_{1},p_{2})=1$, $d(a_{1},p_{2})=1$, and $d(a_{1},p_{4})=1$.
Similarly, write the next move by $p_{2}$ as
$p_{2}:\xrightarrow{p_{3}}b_{1}\xrightarrow{p_{1}=a_{2}}b_{2}$.
$d(p_{2},p_{3})=1$ $d(p_{3},b_{1})=1$, and $d(a_{2},b_{1})=1$.

Suppose $p_{1}$, $p_{2}$, and $p_{4}$ are collinear ($p_{1}$ on $x$, $p_{2}$
on $x+u_{i}$, $p_{4}$ on $x+3u_{i}$), $a_{2}$ = $x+4u_{i}$ and
$a_{1}=x+2u_{i}$. However for $p_{2}$ to jump over $p_{3}$ and $p_{1}$,
$p_{3}$ must occupy $a_{1}$, contradicting the assumption that $a_{1}$ is
open. Say $p_{1}$ starts on $x$, $p_{2}$ on $x+u_{i}$, then $a_{1}$ is
$x+2u_{i}$, $p_{4}$ starts on $x+2u_{i}+u_{j}$, and $a_{2}$ is
$x+2u_{i}+2u_{j}$. There are only two locations both adjacent to $p_{2}$ and 2
away from $a_{2}$, $a_{1}$ and $x+u_{i}+u_{j}$. However if $p_{3}$ is on
$x+u_{i}+u_{j}$ and we perform the two ascents, we have performed the serpent
configuration’s trajectory, a contradiction. These cases are visualized in
Figure 3 Thus it is impossible for a non-speed-of-light configuration $C$ to
have two ascents in a row, so $C$ must have speed at most 2/3. ∎

Figure 3: In the case of $p=4$, we cannot place $p_{3}$ without a
contradiction.

##  5 $p=3$

######  Theorem 5.1.

No configuration of 3 pieces $C$ exists with speed greater than 2/3.

###### Proof.

To show this, we will demonstrate that no placement $X$ exists for $p=3$ such
that two successive ascents are possible. If $X$ has two or three pieces
occupying the same border, then the back or front border has two pieces,
rendering successive ascents impossible. Otherwise assume $X$ has pieces
occupying all different borders. The only possible way for $X$ to be able to
perform a ladder climb is if it has width 4, since a piece jumping over two
other pieces can travel distance at most 4. Let us consider the four borders
passing through $X$, without loss of generality say $l_{1}-l_{4}$. $l_{1}$ and
$l_{4}$ must contain one piece each, $p_{1}$ and $p_{3}$ respectively,
implying the last piece, $p_{2}$ can either lay on $l_{2}$ or $l_{3}$. If
$p_{2}$ lies on $l_{3}$, $p_{1}$ cannot jump. Otherwise, $p_{2}$ lays on
$l_{2}$. If $p_{1}$ can perform an ascent, the pieces now lay on $l_{2}$,
$l_{4}$, and $l_{5}$, which implies $p_{2}$ cannot jump, as in Figure 4.

$\xrightarrow{}$ Figure 4: After a jump, $p$ is isolated and cannot jump.

Therefore no placement $X$ with $p=3$ pieces exists such that two consecutive
ascents can be performed, as desired. No such configuration of
$\mathds{Z}^{n}$ exists with speed greater than $2/3$. ∎

##  6 $p>4$ for $\mathbb{Z}^{2}$

We provide a proof that no configuration of greater than 4 pieces has a speed
greater than 2/3 in the 2-dimensional case. We are confident that the approach
taken here will produce the same sort of result in $\mathbb{Z}^{n}$, but we
shall not pursue that here. Recall that if a moveset has no consecutive
ascents, by Theorem 3.2, the moveset has speed at most 2/3, so our focus will
be on movesets that have consecutive ascents.

######  Lemma 6.1.

For $p>4$, there does not exist a configuration with a moveset containing 4 or
more consecutive ascents.

###### Proof.

Suppose for contradiction that there exists a configuration $C$ with moveset
containing more than 3 consecutive ascents. Then there can only be one piece
on each of the four backmost borders. Additionally, the width of $C$ prior to
moving must be at least 6. It follows that without loss of generality, we can
assume the first four pieces which ascend are located at
$(0,0),(1,0),(1,1),\&\,(2,1)$, as in Figure 5.

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$\times$$\times$$\times$$\times$$\ldots$$\times$$\times$$\times$$\times$$\times$$\times$$\times$
Figure 5: The back borders of $C$ before any moves on the left, and after the
first three ascents on the right. An $\times$ indicates a location a piece
cannot be located in that board state.

However, after the first 3 ascents, the piece at $(2,1)$ $p_{4}$ is not
adjacent to any pieces and therefore cannot ascend, a contradiction. ∎

Define a piece’s measure by taking its location modulo 2, $\mkern
1.5mu\overline{\mkern-1.5mu(x,y)\mkern-1.5mu}\mkern 1.5mu_{2}$. For example,
$p_{4}$ in the above diagram has measure $(0,1)$. Note that when a piece
jumps, its measure stays constant. This restricts the number of locations in
$\mathds{Z}^{2}$ a piece can jump to, given its starting position.

We assume without loss of generality that a moveset $M$ begins with the
maximum number of ascents. Note that this implies $M$ ends in a non-ascent.
Define an isolating partition of $M$ as follows. First, partition $m(M)$
sequentially into blocks $A_{1},...A_{k}$ such that each block begins with two
or more consecutive ascents, but does not have consecutive ascents anywhere
else and does not end with an ascent. So each new block begins at every
occurrence of a sequence of two or more consecutive ascents, and ends with a
non-ascent. This partition of $M$ is unique. For example, if a configuration
had moveset of type $\\{A,A,A,FP,DM,BP,A,A,DM,DM,A,FP,BP\\}$, then the moveset
would be partitioned into blocks $A_{1}=\\{A,A,A,FP,DM,BP\\}$,
$A_{2}=\\{A,A,DM,DM,A,FP,BP\\}$.

Let $L(A_{i})$ be the number of ascents $A_{i}$ begins with. In our example,
$L(A_{1})=3$ and $L(A_{2})=2$. By Lemma 6.1, $L(A_{i})\leq 3$. Since $A_{i}$
ends with a non-ascent, $\omega(A_{i})<L(A_{i})$. We wish to show
$\omega(A_{i})\leq 0$ for all $i$, since $\omega(M)=\omega(\sum
A_{i})=\sum\omega(A_{i})$. Hence if $\omega(A_{i})\leq 0$ for all $i$, then
$\omega(M)\leq 0$. So it suffices to only consider blocks rather than entire
movesets. Since $A_{i}$ can only begin with 2 or 3 ladder climbs, we only have
these two cases to consider.

Call a block $A_{i}$ for which $\omega(A_{i})\leq 0$ suboptimal. Recall that

######  Lemma 6.2.

If a consecutive sequence of moves $S\subset A_{i}$ satisfies
$\omega(S)+L(A_{i})\leq 0$, then necessarily, $\omega(A_{i})\leq 0$, and thus
$A_{i}$ is suboptimal.

###### Proof.

We may assume without loss of generality that $S$ does not begin with an
ascent, since if it does, then removing the initial ascents produces another
consecutive sequence of moves satisfying the same condition. We may also
assume that the move following $S$ is an ascent or the end of the block, since
otherwise, we may extend $S$ until the move following it is an ascent.

Now, partition $A_{i}$ into smaller blocks in the following way: let the first
block contain all consecutive initial ascents.. Then, until the beginning of
$S$ is reached, partition the moves so each block begins with a non-ascent and
continues until an ascent is reached, and let the block end with an ascent.
Each of these blocks will contain exactly one ascent and contain at least one
non-ascent, since $A_{i}$ only contains one sequence of consecutive ascents.
By assumption, the last move before $S$ begins is an ascent, so this
partitioning continues until $S$ is reached. Let $S$ be the next block. Then,
partition the remaining moves of $A_{i}$ in the same way as in the proof of
Theorem 3.2, that is, by letting each block begin with an ascent and
continuing until another ascent is reached. These blocks will also contain
only one ascent.

By the same arguments used in the proof of Theorem 3.2, all blocks $B$ which
are not the first block and $S$ satisfy $\omega(B)\leq 0$. Since the only
blocks remaining are $S$ and the first one, which has weight $L(A_{i})$, by
summing the weights of each block, we conclude that $\omega(A_{i})\leq 0$. ∎

Call $S$ a suboptimal sequence of moves, and call any consecutive sequence of
moves $S$ that is not suboptimal optimal. For example, if 2 ascents were
followed by 4 front pushes, the four front pushes would be a suboptimal
sequence of moves, and the block $A_{i}$ would therefore be suboptimal. Our
strategy is to show that any block $A_{i}$ must contain a suboptimal sequence
of moves.

######  Lemma 6.3.

If a block $A_{i}$ begins with exactly three ascents, $\omega(A_{i})\leq 0$.

###### Proof.

Observe that if $A_{i}$ begins with exactly three consecutive ascents, the
initial placement is forced to have a serpent configuration at the back, and
after the three ascents, the resulting configuration is forced to have a
serpent configuration in the front, as demonstrated in Figure 6.

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p$$p_{1}$$p_{2}$$p_{3}$$\times$$\ldots$$\times$$\times$$\times$$\times$$\times$
Figure 6: The borders before and after the first three ascents. The red
borders denote forced placements. An $\times$ indicates a location a piece
cannot be located in that board state.

By considering move weights, it suffices to demonstrate that a consecutive
sequence of moves in $A_{i}$ occurs with weight $-3$, that is, a suboptimal
sequence of moves must occur. Since each non-ascent has weight at most $-1/2$
if six non-ascents occur between two ascents, then the condition is satisfied.
Note that if five non-ascents occur between two ascents, a sixth must occur by
Proposition 3.0.3. Alternatively, if two dead moves occur or one dead move and
one front/back push occurs, the condition is also satisfied for the same
reasoning. Finally, any front retreat, back retreat, or reverse ascent is
immediately suboptimal.

Call the border containing the backmost piece prior to moving $l_{1}$. We
first consider two cases, if $l_{4}$ has exactly 1 piece or if $l_{4}$ has two
or more pieces.

If $l_{4}$ has two or more pieces, first suppose the next ascent occurs from
$l_{4}$. This implies that one of the pieces on $l_{4}$ must front push or
dead move from $l_{4}$ first. Observe that a ladder climb to the front from
$l_{4}$ cannot be performed unless $p$ or $p_{2}$ moves, since the pieces from
$l_{4}$ can only hop over $p_{1}$ and $p_{3}$ by parity. If a piece from
$l_{4}$ dead moves, then since an ascent can still not occur, another move
must be made before an ascent is possible, so since a dead move and one more
non-ascent has been performed, there is a suboptimal sequence of moves.

Therefore, a possibly optimal sequence of moves must have a piece from $l_{4}$
make a front push before the other performs the ascent. A front push consists
of a ladder climb from $l_{4}$ to beyond the front border, but one of $p$ or
$p_{2}$ must move before that is possible. If $p$ or $p_{2}$ performs a dead
move, then after the ladder climb from $l_{4}$, a suboptimal sequence of moves
will be forced to occur before the next ascent.

If $p$ or $p_{2}$ ladder climbs to perform a front push, a ladder climb from
$l_{4}$ still cannot be performed, so necessarily, a front push must occur by
the piece that previously moved. After this, it may be possible for a piece,
call it $p^{\prime}$ from $l_{4}$ to front push. The only optimal move
afterwards is another front push, and since the remaining piece on $l_{4}$ can
only hop over $p_{1}$ and $p_{3}$ in the front borders, for an ascent to be
possible, $p^{\prime}$ must front push. If an ascent is not possible, then
since four front pushes have occurred and another non-ascent must occur, a
suboptimal sequence of moves must happen. Otherwise, suppose an ascent from
$l_{4}$ happens. The sequence of moves performed is $A,A,A,FP,FP,FP,FP,A$, and
the sequence of moves after the consecutive ascents has weight -1. Now, if a
new sequence of moves of weight -2 occurs, the total sequence will be
suboptimal.

From the initial configuration, Figure 6, it is necessary that the pieces on
$l_{4}$ were either farther than distance 2 away, or were distance 2 away, but
must have hopped over separate pieces. Thus, there are 2 pieces on $l_{5}$. If
the next ascent occurs from $l_{5}$, the border beyond $p_{3}$ is empty and
requires a piece there to build a ladder. This border cannot be filled by a
back push since $l_{5}$ has 2 pieces, and thus, a dead move must occur before
the ascent, forcing a suboptimal sequence of moves. Otherwise, if the next
ascent occurs from beyond $l_{5}$, since a ladder climb from $l_{5}$ to the
front is impossible, a dead move must occur when bringing the pieces on
$l_{5}$ forward, again, forcing suboptimality. We conclude that if $l_{4}$
began with 2 or more pieces, and the first ascent after the three initial ones
occurred from $l_{4}$, there is a suboptimal sequence of moves.

Otherwise, suppose $l_{4}$ contains at least 2 pieces, and the first ascent
after the initial three happens beyond $l_{4}$. In this case $l_{4}$ must be
cleared, but neither piece can front push (a ladder climb to in front of
$p_{3}$). If one piece dead moves forward and the other front pushes, then a
suboptimal sequence of moves occurs. Otherwise, if no dead move occurs, then
necessarily, one of $p$ or $p_{2}$ front pushes twice to open the ladder, then
a piece front pushes from $l_{4}$, and another back pushes to clear $l_{4}$.
However by a previous argument, there must be at least 2 pieces on $l_{5}$, so
another move must occur before an ascent can. Since 5 moves have occurred,
suboptimality is forced. Thus, if $l_{4}$ began with at least 2 pieces, a
suboptimal sequence of moves must occur.

Now, suppose $l_{4}$ has one piece, and let $p$ be the original front border
piece. The back of the initial configuration must necessarily must be in the
situation in Figure 7:

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$\times$$\times$$\times$$\times$$\ldots$$\times$$\times$$\times$$\times$$\times$$\times$$\times$
Figure 7: The left diagram is the initial configuration, and the right diagram
is the configuration after the three consecutive ascents.

If the next ascent occurs on $l_{4}$, then again, $p$ is forced to dead move,
and since $p_{4}$ is isolated, another piece must move to be adjacent to it.
If these are separate moves, then two dead moves have been performed, a
sequence of moves with weight $-4$. Otherwise, suppose these are the same
move, so $p_{4}$ ascends right after. Then there is a new serpent
configuration at the front, and two pieces on $l_{5}$, namely $p_{5}$ and the
piece $p_{4}$ hopped over to ascend (which is necessarily $p$ as in Figure 6),
as pictured in Figure 8.

$p$?$p$?$p_{5}$$p_{4}$$p_{1}$$p_{2}$$p_{3}$$\ldots$$\times$$\times$$\times$$\times$
Figure 8: The configuration after $p_{4}$ ascends, in the case where $l_{4}$
has one piece and the next ascent follows from $l_{4}$. There are necessarily
two pieces on $l_{5}$ and a serpent configuration in the front preventing an
ascent from occurring.

Since the previous two moves have weight $-1$, it is enough to show the next
sequence of moves must have weight $-2$. Thus it suffices to assume no dead
move can occur. Note that the parity is correct for an ascent to occur, as the
pieces on $l_{5}$ can hop over $p_{2}$ and $p_{4}$, but given the front of the
configuration, no ascent can occur. At least two front pushes (or a dead move)
must occur in the front borders before one of the pieces on $l_{5}$ can climb
to the front. However, this is three front pushes, implying a fourth front or
back push must occur before an ascent can occur, so there must be a sequence
of moves with weight $-2$ if the next ascent is to occur from $l_{5}$.

Otherwise, if the next ascent happens beyond $l_{5}$, it is straightforward to
see that a sequence of moves must first occur with weight $-3$, and we
conclude that in any case, $\omega(A_{i})\leq 0$. ∎

######  Lemma 6.4.

If a block $A_{i}$ begins with exactly two ascents, $\omega(A_{i})\leq 0$.

###### Proof.

By considering move weights, it suffices to demonstrate that a sequence of
moves in $A_{i}$ after the two ascents occurs with weight -2, that is, a
suboptimal sequence of moves must occur. In particular, it suffices to show
either a dead move occurs or 4 front or back pushes occur between ascents.
However, by Proposition 3.0.3, it suffices to show only 3 front or back pushes
occur rather than 4. First observe that the starting and ending configurations
after the two ascents must be as follows at the front and back borders
respectively, pictured in Figure 9.

$p_{1}$$p_{2}$$p$$p_{1}$$p_{2}$$\ldots$$\times$$\times$$\times$$\times$ Figure
9: The borders before/after the ones indicated by red in the above diagrams
are forced placements. A $\times$ indicates a location a piece cannot be.

Call the border containing the piece $p_{1}$ which is farthest back $l_{1}$.
We begin by considering two cases, if $l_{3}$ has exactly 1 piece, $p_{3}$, or
if it has multiple pieces $p_{3}$ and $p_{3}^{\prime}$. Then, we consider sub-
cases and determine that any trajectory must eventually become suboptimal.

First, suppose $l_{3}$ has at least 2 pieces initially, $p_{3}$ and
$p_{3}^{\prime}$. Let us consider the next two moves following the ascents. If
either is a dead move or worse, the trajectory is suboptimal, so suppose the
next two moves are front or back pushes. Since $l_{3}$ has at least 2 pieces,
the first move must be a front push. If the front push is not performed by
$p_{3}$ or $p_{3}^{\prime}$, then the next move must also be a front push, but
since the width of the configuration is odd after the first front push,
$p_{3}$ or $p_{3}^{\prime}$ could not have performed the front push. Since
$l_{3}$ contains two pieces still, the next move is not an ascent, so the
sequence of moves is suboptimal.

Otherwise, suppose the first front push was a ladder climb from $l_{3}$ to the
front. Without loss of generality suppose $p_{3}$ makes the climb. If the
second move is a back push from $l_{3}$, since there is a serpent
configuration consisting of $p,p_{1},p_{2},p_{3}$, a ladder climb is not
possible afterwards, and thus the trajectory is suboptimal.

Instead, suppose the second move is a front push. Since there is a serpent in
the front, the only move which allows for a ladder climb (necessarily by
$p_{3}^{\prime}$) is $p_{3}$ shifting forward. Then, a ladder climb by
$p_{3}^{\prime}$ must finish by hopping to where $p_{3}$ was prior to
shifting, then hopping over $p_{3}$. This implies $p_{3}$ and $p_{3}^{\prime}$
originally had the same measure, so they were distance at least 4 away.
Therefore, there must be at least 2 pieces on $l_{4}$ which $p_{3}$ and
$p_{3}^{\prime}$ hopped over, $p_{4}$ and $p_{4}^{\prime}$, as pictured in
Figure 10.

$p_{4}^{\prime}$$p_{4}$$p$$p_{1}$$p_{2}$$p_{3}$$p_{3}^{\prime}$$\ldots$ Figure
10: Right: the only possibly optimal trajectory if 2 pieces started on
$l_{3}$, five moves in. Left: a corresponding possible placement on $l_{4}$
five moves in.

By a parity argument, $p_{4}$ and $p_{4}^{\prime}$ cannot hop over $p,p_{2},$
or $p_{3}$, as they are on an even-numbered border. If the next ladder climb
occurs from beyond $l_{4}$, then $p_{4},p_{4}^{\prime},$ and $p_{3}^{\prime}$
all must move first, which is necessarily a sequence of moves with weight at
maximum -2. Otherwise, if the next ladder climb occurs on $l_{4}$, the pieces
in front of $p$ which can be used in the ladder are $p_{1}$ and
$p_{3}^{\prime}$. However, a piece needs to move to the border between the
ones containing $p_{2}$ and $p_{3}$, and by parity, this piece cannot come
from $l_{4}$. Hence, this must be a dead move, and we conclude that if $l_{3}$
began with 2 or more pieces, then $\omega(A_{i})\leq 0$.

Otherwise, suppose $l_{3}$ began with exactly 1 piece on it. We consider
subcases based on where the next ascent in the the trajectory occurs from and
the number of pieces on the following borders. First, suppose the next ascent
comes from $l_{4}$ or beyond. If $l_{4}$ contains more than one piece, then in
order for the trajectory to be optimal, the next two moves must be a back push
from $l_{3}$, then a front push from $l_{4}$. However, this is impossible,
since a back push from $l_{4}$ must be a ladder climb, but by a parity
argument of where the frontmost border is, a ladder climb from $l_{4}$ cannot
advance the front border.

Otherwise, suppose the next ascent comes from $l_{4}$ or beyond and that
$l_{4}$ contains exactly one piece. The necessary starting configuration is
pictured in Figure 11.

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$p$$p_{1}$$p_{2}$$\ldots$$\times$$\times$$\times$$\times$
Figure 11: On the left, part of the necessary configuration if $l_{4}$
contains one piece, prior to the first two ascents. On the right, the front
borders after the first two ascents.

Then for an optimal trajectory, the next two moves following the two ascents
must be a back push from $l_{3}$ and a front push elsewhere (by assumption an
ascent is not allowed). Assume the same piece does not perform the two moves,
since otherwise, an ascent would be a faster trajectory, which would reduce to
the previous lemma. Note that the front push cannot occur from $l_{4}$ by
parity. Moreover, the back push from $l_{3}$ must hop over the sole piece on
$l_{4}$, because otherwise, after the two moves there would be 2 pieces on
$l_{4}$.

Finally, note that the front push must necessarily come from $p_{2}$ if an
ascent is possible afterwards, since it is clear that a front push from
$p_{1}$ prevent ascents, and front pushes from any other piece result in a
serpent configuration at the front which prevents an ascent. Hence, after the
front and back push, if an ascent is possible, there must be two pieces on
$l_{5}$: the piece which $p_{2}$ hopped over in its ascent, and the piece
$l_{4}$ is to hop over first in its ascent (this may be $p_{3}$). After
$p_{4}$ ascends, we now are in the configuration pictured in Figure 12.

$p$?$p_{5}$$p$$p_{1}$$p_{2}?$$p_{4}?$$\ldots$ Figure 12: The configuration
after $p_{4}$ ascends. The question marks denote where piece locations are not
forced.

Now, for the trajectory to stay optimal, the next ascent must occur from
$l_{5}$, since otherwise it would take two moves to clear $l_{5}$ and at least
one to alter the front borders so that an ascent is possible. Pieces from
$l_{5}$ may only hop over $p$ and $p_{4}$ in the front borders, so they must
be in the next ladder. This implies that in the next two moves before the
ascent, a piece must move to the border between $p_{1}$ and $p_{2}$. However,
this must be a dead move or worse, since $l_{5}$ contains at least two pieces
and thus cannot initiate a back push. Thus, all movesets for which the next
ascent comes from $l_{4}$ or beyond are suboptimal.

Finally, we consider the case where the next ascent comes from $l_{3}$, and
$l_{3}$ contains only one piece. Since an ascent cannot immediately occur, the
next two moves if they are to be optimal must be front pushes. It is quick to
see that the only possibilities are either $p_{1}$ pushing twice or another
unlabeled piece coming from an odd-numbered border pushing twice, as pictured
in Figure 13.

$p$$p^{\prime}$$p_{2}$$p_{1}$$p$$p_{1}$$p_{2}$ Figure 13: Note that the
location of $p^{\prime}$ on the left or $p_{1}$ on the right are not uniquely
determined.

If $p_{3}$ cannot ascend, the sequence of moves must be suboptimal, so assume
$p_{3}$ can ascend, the third ascent so far in the moveset. We now consider
cases based on which border the fourth ascent occurs from. If the fourth
ascent occurs from $l_{4}$ or any even numbered border, these pieces cannot
hop over $p$, $p_{2}$, or $p^{\prime}$($p_{1}$) in the left-hand (resp. right-
hand) cases.

In the left-hand case from Figure 13, before the next ascent, a piece must
move to the border between $p_{2}$ and $p^{\prime}$, $p_{2}$ must move for
$p_{1}$ to be free to be hopped over, and $p^{\prime}$ must move so the
frontmost piece can be hopped over. These must necessarily be performed as
front or back pushes for optimality, however if these are performed as front
or back pushes, this is at least 3 separate moves, making the sequence
suboptimal.

In the right-hand case from Figure 13, pieces must move to the border between
$p$ and $p_{2}$ and the border between $p_{2}$ and $p_{1}$, and $p_{1}$ must
move so the frontmost piece can be hopped over. Again, these must be performed
as front or back pushes for optimality, but as front or back pushes, this is
at least 3 separate moves, making the sequence suboptimal.

Finally, suppose the fourth ascent occurs from $l_{5}$ or beyond. There is
necessarily at least one piece on $l_{4}$ which must front push, and $p_{3}$
must move to open the ladder it climbed. If there are two pieces on $l_{4}$,
then there are 3 moves that must occur which is suboptimal, so suppose there
is only one piece on $l_{4}$, $p_{4}$, which both $p_{3}$ and $p_{1}$ hopped
over. By similar arguments to earlier, $p_{4}$ cannot hop forward, it must
shift to $l_{5}$. Now, if there are 2 or more pieces on $l_{5}$, then
suboptimality is forced, as one must move before the ascent, which totals 3
moves before the ascent. However, it is possible that $l_{5}$ contains only
one piece, $p_{4}$, as $p_{5}$ as shown in Figure 14 could have been the piece
to front push prior to the ascent of $p_{3}$.

$p_{1}$$p_{2}$$p_{3}$$p_{4}$$p_{5}$$p$$p_{5}$$p_{2}$$p_{1}$$p_{3}$$\ldots$$\times$$\times$$\times$$\times$$\times$
Figure 14: On the left, the necessary setup if $l_{4}$ and $l_{5}$ only have
one piece, and on the right, in the lone scenario where $l_{5}$ front pushed
before $p_{3}$ ascended.

In this case, then $p_{4}$ can ascend and optimality is still preserved.
However, there must be two different pieces on $l_{6}$, the piece $p_{5}$ hops
over when it front pushes, and the piece $p_{3}$ hops over after hopping over
$p_{4}$ when it ascends. By a similar argument as earlier, the next ascent
occurring from $l_{6}$ forces suboptimality, and it is straightforward to see
that at least 3 unique moves must occur for the next ascent to occur from
$l_{7}$ or beyond. Thus, if after the initial 2 ascents, the next ascent
occurs from $l_{3}$, and $l_{3}$ only contained one piece, suboptimality is
forced. We have exhausted all cases, and conclude that $\omega(A_{i})\leq 0$.

∎

######  Theorem 6.5.

If $C$ is a configuration with 5 or more pieces, then $C$ has speed less than
or equal to $2/3$.

###### Proof.

Consider any $m$-move trajectory $M$ of $C$. If $M$ has no consecutive
ascents, then Theorem 3.2 implies $M$ has speed at most 2/3. Otherwise,
perform an isolating partition of $M=\sum_{i=1}^{n}A_{i}$. By the two previous
lemmas, $\omega(M)=\omega(\sum A_{i})=\sum\omega(A_{i})\leq 0$, as desired. ∎

Acknowledgment. The authors are grateful to the referees for many valuable
suggestions and corrections.

## References

  * [1] Arthur T. Benjamin, Graphs, Maneuvers, and Turnpikes, _Operations Research_ , 38(2), 202–216, 1990.
  * [2] Joel Auslander, Arthur T. Benjamin and Daniel S. Wilkerson, Optimal Leapfrogging, _Mathematics Magazine_ , 66(1):14–19, 1993.