Coins on a Chessboard
A 35-year-old puzzle with extras
|DeLong Lecture Series source|
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, having earlier won the corresponding prize in Fundamental Physics. He divides his time between the University of Miami and the Institut des Hautes Études Scientifiques (IHES), which boasted Alexander Grothendieck at its inception. His IHES bio says that he is known for
…drawing on 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 as a teenager that uses 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 The only move in the game is that if a coin is on a square—say —and the squares to its right and one step forward are empty, then the coin can be removed from and new coins placed on the squares and Thus each coin “clones itself” into two while vacating the square it was on. Variously the board may be limited to or or allowed to be infinite up and/or rightward.
A subset of cells including is designated a “prison,” and initially one or more cells in (and perhaps some outside ) are occupied to make an initial configuration The game is won if moves are made to reach a configuration in which all cells in are empty. Figuratively speaking, the prisoners inside have broken out—their clones have escaped. The question is:
Given and , can the game be won? And what is the complexity of deciding this?
The simplest nonempty prison is and The stone escapes in one move. So let’s next take so that its movement is initially blocked. Then it can escape in four moves:
We need only give a move’s source square. At the end there are coins on . We might go on to try to clear and but let’s ask about that later. Go back to only but let’s widen the prison instead to After the first move we need to clear the new coins on and and their moves block each other at . But after the moves we win.
Now let’s make it harder by widening the prison to include too. We can still win in four more moves: Using a pretty applet designed by Seth Weiss of Lincoln-Sudbury Regional High School in Massachusetts, we have this configuration:
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 , perhaps adding too to ?
A Proof Idea
The most common starting setup in recent sources of this puzzle uses . 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 where is the distance to the lower-left corner in horizontal plus vertical steps.
The three coins have total weight , the corner contributing and the others each. The key idea is:
Every move by a coin preserves the total weight of the configuration .
If and when we clear the prison , the coins outside it must have total weight . Now the total weight of the infinite board is . We can verify this by noting that the bottom row has a geometric series summing to , and each further row has half the weight in each square, so the total is
The upshot is that the whole region outside contributes only weight , and hence any finite set of coins outside it must have total weight strictly less than . It is hence impossible to clear . This is a neat idea.
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 and having the ten cells within distance . The coin has weight but totals , leaving less than outside. This made the no answer fine for a timed question. The above case , however, only totals weight . So maybe it is possible—or maybe if we don’t require clearing ? We’ll leave that to you, our readers, with unlimited time.
A Surprising 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 reached this way can also be reached by strictly legal moves in a different order.
This yields the idea of a “diagonal sweep”: Given —or any configuration —go out by diagonals starting in the corner until the last diagonal that intersects a cell in . For each nonempty cell on each diagonal that belongs to , play these extended pile-on moves until it is empty; if the cell is not in , play until it has one coin. Stop after finishing the last diagonal even though the resulting configuration will generally be illegal with multiple-coin squares.
A single sweep can be executed in time at worst quadratic in the size of (assuming is connected). Amazingly, a simple property of decides whether the game is winnable. So the decision problem “can you win?” has a polynomial-time algorithm.
Can you work out what this telltale property is? Can you apply it to answer the cases left open above?
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 over obstacles like in chess but for strictly legal play the landing squares must be empty.
For example, a starting heads coin at can become tails at . Then we can replace by heads at and , and can jump over to give heads at and . The tails coin at is blocked from a knight’s move at . However, we can play four standard heads-coin moves to clear and finally occupy and with all coins heads again. The resulting configuration is:
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 has total weight
so it went down. However, the bottom row and leftmost column can never be used again. Hence it is equivalent to move one cell diagonally southwest. Then its weight is multiplied by giving Devising weighting rules to handle these multiple options and factors seems challenging but feasible.
I’ve just thought of this variant, and am not taking time to research it beyond some sanity checks before posting. So the field is all open for you, our valued readers. Does it allow every finite region 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. The games we’ve been discussing here are more similar to evolutions of two-state one-dimensional cellular automata but again our variants seem to be different.
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?
Update 2/27/16: See reader <a href=comment showing that not all regions can be cleared so the decision problem is nontrivial.
[“known for”->”drawing on” and added second prize in intro]