\documentstyle[12pt]{article}
\begin{document}
 
As a summer treat (or a winter treat for our Australian friends),
an old puzzle by J. H. Conway.
 
You have an infinite two dimensional grid.
The vertices are given by pairs of integers (x,y).
You have a large but finite collection of coins,
which you place on some of the vertices, at most one coin per vertex,
and initially restricted to the sites with nonnegative y
(that is, the upper half plane, including the x-axis).
 
Now you "jump" coins: if two coins are adjacent either vertically
or horizontally, with an empty space adjacent, then
you are allowed to pick up the first coin, jump
over the second coin, and land in the next space (the empty one).
The "second coin" is removed from the grid.
During the jumping phase,
coins are allowed to stray into the territory of negative y.
 
Your objective is to push a coin as far "down" as possible into the
territory of negative y.
 
If we started with coins at (0,0), (0,1), (1,0) and (2,0), the second
coin could jump over the first into position (0,-1), leaving us with
three coins at (0,-1), (1,0), (2,0).  The coin at (2,0) jumps over the
coin at (1,0), leaving us with two coins at (0,-1), (0,0).  One
final jump leaves us with a single coin at (0,-2).  But you can
do better than that, can't you?
 
Answer:
 
Let $\phi$ denote the golden ratio 1.618, with $\phi^2=\phi+1$.
Let the "value" of a position (x,y) be $\phi^{-|x|-y}$.
Let the "value" of a board be the sum of the values of the
occupied positions.
 
Claim 1: the value of the board does not increase when we make a jump.
 
Claim 2: the value of the initial position is strictly smaller
than $\phi^5$.
 
Assuming the truth of these claims, the value of the final position
must also be smaller than $\phi^5$.  So the final position cannot
contain a coin at (0,-5), or indeed at $(0,y)$ for $y \leq -5$.
By symmetry we can
see that there is no coin at $(x,y)$ for $y \leq -5$,
for any value of $x$.
So the most we can hope for is a coin at (0,-4).
 
One way to get a coin at (0,-4) is to
start with 24 coins at (0,0), (0,1), (1,0), (1,1), (1,2), (2,0), (2,1),
(3,0), (3,1), (3,2), (3,3), (4,0), (4,1), and the mirror reflections:
(-1,0), (-1,1), (-1,2), (-2,0), (-2,1),
(-3,0), (-3,1), (-3,2), (-3,3), (-4,0), (-4,1).
Then just start jumping.  With a little foresight you will
end up with a single coin at (0,-4).
 
Proof of Claim 1:
At each stage we replace coins at $(x,y)$ and $(x+1,y)$ with
a single coin at $(x+2,y)$ or at $(x-1,y)$,
or else replace coins at $(x,y)$ and $(x,y+1)$ with a single
coin at $(x,y+2)$ or at $(x,y-1)$.
Because of the condition $\phi^2=\phi+1$, the total "value" stays
the same if $(x,y)$ and $(x,y+1)$ are replaced by $(x,y-1)$,
or if $(x,y)$ and $(x+1,y)$ are replaced by $(x-1,y)$ (when $x \geq 1$)
or by $(x+2,y)$ (when $x \leq -2$).
In all other cases the total value decreases.
Look at the case where coins at $(x,y)$ and $(x,y+1)$ are replaced
by a coin at $(x,y-1)$.
The change in value is
$$- \phi^{-|x|-y} - \phi^{-|x|-(y+1)} + \phi^{-|x|-(y-1)}
= \phi^{-|x|-y}*(-1-\phi^{-1}+\phi^{+1}) = 0.$$
 
Proof of Claim 2:
The sum of the infinite geometric series
$S = \phi^{-0} + \phi^{-1} + \phi^{-2} + \phi^{-3} + \ldots $
is $S = 1/(1-\phi^{-1})$, which is equal to $\phi^2$.
Similarly the sum of $\phi^{-|x|}$, as $x$ ranges over all integers,
is $2S-1 = \phi^2 + \phi^2-1 = \phi^2+\phi = \phi^3$.
So the "value" of the entire half board, the points $(x,y)$ with $y$
nonnegative, is
 
$$\sum_{-\infty < x < \infty} \sum_{0 \leq y < \infty} \phi^{-|x|-y}$$
$$= \sum_{-\infty < x < \infty} \phi^{-|x|} *
\sum_{0 \leq y < \infty} \phi^{-y}$$
$$= (\phi^3)*(\phi^2)=\phi^5 .$$
We start with a finite subset of that half board, so our initial value
must be strictly less than $\phi^5$.
 
\end{document}
