{\huge Coins on a Chessboard}

An old puzzle with extras \vspace{.25in}

Maxim Kontsevich has established deep connections between algebraic geometry and mechanisms of physics. He won a Fields medal in 1998 for ``contributions to four problems of geometry'' and recently won one of the inaugural Breakthrough Prizes in Mathematics. He divides his time between the University of Miami and the Institut des Hautes \'Etudes Scientifiques (IHES), which boasted Alexander Grothendieck at its inception. His IHES bio says that he is

...known for the systematic utilization of known deformations of algebraic structures and the introduction of new ones that have been revealed to pertain to many other questions where there were no a-priori connections.

Today we discuss a much lighter topic he thought up at age 17 and other puzzles about coins on a chessboard.

The puzzle uses only coins---or pebbles or pawns---no other chess pieces. The game starts with one or more coins in squares near the lower-left corner, which we'll call square $latex {a1.}&fg=000000$ The only move in the game is that if a coin is on a square---say $latex {b4}&fg=000000$---and the squares $latex {c4}&fg=000000$ to its right and $latex {b5}&fg=000000$ one step forward are empty, then the coin can be removed from $latex {b4}&fg=000000$ and new coins placed on the squares $latex {b5}&fg=000000$ and $latex {c4.}&fg=000000$ Thus each coin ``clones itself'' into two while vacating the square it was on. Variously the board may be limited to $latex {8 \times 8}&fg=000000$ or $latex {n \times n}&fg=000000$ or allowed to be infinite up and/or rightward.

A subset $latex {P}&fg=000000$ of cells including $latex {a1}&fg=000000$ is designated a ``prison,'' and initially one or more cells in $latex {P}&fg=000000$ (and perhaps some outside $latex {P}&fg=000000$) are occupied to make an initial configuration $latex {C_0.}&fg=000000$ The game is won if moves are made to reach a configuration $latex {C}&fg=000000$ in which all cells in $latex {P}&fg=000000$ are empty. Figuratively speaking, the prisoners inside $latex {P}&fg=000000$ have broken out---their clones have escaped. The question is:

Given $latex {P}&fg=000000$ and $latex {C}&fg=000000$, can the game be won? And what is the complexity of deciding this?

Some Escapes

The simplest nonempty prison is $latex {P = \{a1\}}&fg=000000$ and $latex {C_0 = \{a1\}.}&fg=000000$ The stone escapes in one move. So let's next take $latex {C_0 = \{a1,a2,b1\}}&fg=000000$ so that its movement is initially blocked. Then it can escape in four moves:

$latex \displaystyle b1,b2,a2,a1. &fg=000000$

Now let's make it harder by widening the prison to include $latex {b2}&fg=000000$ too. We can still win in four more moves: $latex {b3,c3,c2,b2.}&fg=000000$ Using a pretty applet designed by Seth Weiss of Lincoln-Sudbury Regional High School in Massachusetts, we have this configuration:

\includegraphics[width=2.5in]{ChessPebbleConfig.png}

The next question to ask is, can we enlarge our cleared space one cell further? Or are too many clones stepping on each others' toes? This turns out to be equivalent to asking, can we win the case $latex {C_0 = \{a1\}}&fg=000000$, $latex {P = \{a1,a2,b1,b2,a3,\}}&fg=000000$ perhaps adding $latex {c1}&fg=000000$ too to $latex {P}&fg=000000$?

A Proof Idea

The most common starting setup in recent sources of this puzzle uses $latex {P = C_0 = \{a1,a2,b1\}}&fg=000000$. Can the clones win? This is featured in a video by Zvezdelina Stankova of Mills College and UC Berkeley for the Berkeley Math Circle, which she founded.

Here is the starting configuration together with the idea of assigning a weight to each square. The weight is $latex {1/2^d}&fg=000000$ where $latex {d}&fg=000000$ is the distance to the lower-left corner in horizontal plus vertical steps.

\includegraphics[width=2.5in]{ChessPebbleWeights.png}

The three coins have total weight $latex {2}&fg=000000$, the corner contributing $latex {1}&fg=000000$ and the others $latex {1/2}&fg=000000$ each. The key idea is:

Every move by a coin preserves the total weight of the configuration $latex {C}&fg=000000$.

If and when we clear the prison $latex {P}&fg=000000$, the coins outside it must have total weight $latex {2}&fg=000000$. Now the total weight of the infinite board is $latex {4}&fg=000000$. We can verify this by noting that the bottom row has a geometric series summing to $latex {2}&fg=000000$, and each further row has half the weight in each square, so the total is

$latex \displaystyle 2 + 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots = 4. &fg=000000$

Now try applying this idea to the cases in the last section. Kontsevich originally contributed the puzzle to the 1981 Soviet ``Tournament of the Towns'' math competition with the easier case of a single coin in the corner with $latex {P}&fg=000000$ having the ten cells within distance $latex {3}&fg=000000$. The coin has weight $latex {1}&fg=000000$ but $latex {P}&fg=000000$ totals $latex {3\frac{1}{4}}&fg=000000$, leaving less than $latex {1}&fg=000000$ outside. This made the no answer fine for a timed question. The above case $latex {P = \{a1,a2,a3,b1,b2,c1\}}&fg=000000$, however, only totals weight $latex {2\frac{3}{4}}&fg=000000$. So maybe it is possible---or maybe if we don't require clearing $latex {c1}&fg=000000$? We'll leave that to you, our readers, with unlimited time.

A Surprise Algorithm

One further idea that makes playing the game less dependent on strategy is we can allow moves that pile up more than one coin on a square, provided we later clear all but one coin on that square. Any legal configuration $latex {C}&fg=000000$ reached this way can also be reached by strictly legal moves in a different order.

This yields the idea of a ``diagonal sweep'': Given $latex {C_0}&fg=000000$---or any configuration $latex {C}&fg=000000$---go out by diagonals starting in the corner until the last diagonal that intersects a cell in $latex {P}&fg=000000$. For each nonempty cell on each diagonal that belongs to $latex {P}&fg=000000$, play these extended pile-on moves until it is empty; if the cell is not in $latex {P}&fg=000000$, play until it has one coin. Stop after finishing the last diagonal even though the resulting configuration $latex {C'}&fg=000000$ will generally be illegal with multiple-coin squares.

A single sweep can be executed in time at worst quadratic in the size of $latex {P}&fg=000000$ (assuming $latex {P}&fg=000000$ is connected). Amazingly, a simple property of $latex {C'}&fg=000000$ decides whether the game $latex {(P,C_0)}&fg=000000$ is winnable. So the decision problem ``can you win?'' has a polynomial-time algorithm. If you are stumped you can always consult a 1995 paper by Fan Chung, Ron Graham, John Morrison, and Andrew Odlyzko which proved this result and much more. A 2010 paper by Qiang Zhen and Charles Knessl explores more of the beautiful numerical results and problems that associate to this puzzle.

Now With Real Coins

We at GLL always try to offer something new, and this is where we will finally justify calling the markers coins. Let a coin that is heads move as above but also have the option of cloning itself into three coins that are tails, filling the cell one diagonal step northeast as well as one cell up and to the right. A coin that is tails can clone itself into two tails coins as before, but can also clone into two heads coins each a knight's move northeast. The knight moves can jump like in chess but for strictly legal play the landing squares must be empty.

For example, our heads coin at $latex {a1}&fg=000000$ can become tails at $latex {a2,b2,b1}&fg=000000$. Then we can replace $latex {a2}&fg=000000$ by heads at $latex {b4}&fg=000000$ and $latex {c3}&fg=000000$, and $latex {b2}&fg=000000$ can jump over to give heads at $latex {c4}&fg=000000$ and $latex {d3}&fg=000000$. The tails coin at $latex {b1}&fg=000000$ is blocked from a knight's move at $latex {c3}&fg=000000$. However, we can play four standard heads-coin moves to clear $latex {c3}&fg=000000$ and finally occupy $latex {c3}&fg=000000$ and $latex {d2}&fg=000000$ with all coins heads again. The resulting configuration $latex {C}&fg=000000$ is:

\includegraphics[width=2.5in]{KnightPebbles.png}

Thus the new rules have enabled us to win Kontsevich's original impossible case. This was possible because the new rules do not conserve weight. The configuration $latex {C}&fg=000000$ has total weight

$latex \displaystyle \frac{3}{16} + \frac{2}{32} + \frac{3}{64} + \frac{2}{128} = \frac{5}{16} = 0.3125, &fg=000000$

I've just thought of this variant, and amid much else going on do not have time to pursue it more now, so the field is all open for you, our valued readers. Does it allow every finite region $latex {P}&fg=000000$ to be cleared? If so, what tightening of the rules would make the decision problem nontrivial again? Could it be undecidable? Similar questions for John Conway's game of Life are undecidable. Games of this kind are more similar to evolutions of two-state one-dimensional cellular automata but again ours seem to be different.

Open Problems

Do you find our new heads/tails version of the chessboard pebbling game interesting? Is its decision problem nontrivial, and is there an efficient algorithm for it?