COOL MATH: Sand Piles
James Tanton - November 29, 2016
OPENING PUZZLERStack \(n\) coins at the origin on the number line and let them spread across it according to the following rule: Identify a stack with two or more coins on it and then “fire” that stack. That is, move two coins off the identified stack and set one coin one unit to the left and the other one unit to the right. Repeat this action until there are no stacks that can fire. Here is the start of one possible sequence of moves for a game starting with a stack of six coins.
Some questions: 1. Continue play with the six-coin game. What final configuration of coins do you reach? 2. Play the six-coin game a second time but make different choices as to which stack to fire when. Do you end up with the same final configuration of coins? Must you? 3. Must these games terminate? Could one fall into an infinite loop of fires? 4. Develop a general theory about these coin firing games. Must \(n\) coins placed at the origin stabilize to the same final configuration, irrespective of the choices made along the way? If so, can you say what the final configuration must be? Can you say anything about the number of fires made along the way? |
CHIP FIRING AND SANDPILES
“Chip firing” and sandpile patterns constitute a very active area of research today. Start with a diagram of edges and nodes and place chips on the nodes.
Each node has some count of edges emanating from it and whenever a node holds at least that many chips, it is ready to “fire,” to send one chip out along each emanating edge to a neighboring node. Chip firing theory asks: What happens in the long-run if we repeatedly perform fires (and does what happen in the long run depend on the order in which nodes fire)?
Sandpile theory is chip firing too, but the imagery is of a spreading pile of sand. Stack \(n\) grains in one cell of an infinite square grid. Any cell that contains a stack of four or more grains is considered unstable and can “topple,” sending one grain to each of its four neighbors: east, west, north, and south. One asks: What happens in the long-run if we topple unstable stacks?
Stunning pictures result in playing with sandpiles this way. In their paper “Laplacian Growth, Sandpiles, and Scaling Limits” Lionel Levine and Yuval Peres show the final results of letting initial single stacks of one-hundred thousand and one million grains topple and all the subsequent stacks that result topple too.
(Blue pixels indicate stacks with 3 grains, purple those with 2 grains, and red those with 1 grain.)
You can see more sandpile pictures here.
The opening puzzler asks us to study the mathematics of sandpiles on a line (or, equivalently, chip firing along nodes connected in a line).
ONE DIMENSIONAL SANDPILES
If you played with the opening puzzler, you will find that game does indeed stabilize to a fixed pattern, irrespective of the order of choices one makes along the way. Here are the final patterns starting with 1 up to 10 coins. (The numbers underneath each site gives the total number of times that site fired.)
Two observations:
Starting with \(2N\) coins at the origin, it seems that the final stable pattern consists of a row of \(N\) coins just to the left of the origin and a row of \(N\) coins to the right. If we start with \(2N+1\) coins, the extra coin sits at the origin.
The number of fires for the nodes seem to follow a pattern with the triangular numbers.
Let’s see if we can prove these suspicions true.
PROOFS
Let’s analyze the specific case of the game with ten or eleven coins. (We’ll be sure to point out how the ideas in this specific argument match a general argument.)
From playing the game, it looks like the pattern of triangular numbers could be important to think about.
(The \(n\)th triangular number is \(T_{n}=1+2+3+\cdots+n\). For a game starting with \(2N\) or \(2N+1\) coins, the general pattern of triangular numbers is \(T_1 T_2 T_3 \ldots T_N\ldots T_3 T_2 T_1\).)
Claim: As one plays the game, no particular cell will ever fire more than the number of times given by this pattern of triangular numbers.
Reason: Suppose, as you play the game, you do in fact fire a cell more times than the number indicated in the pattern. Consider the first time you do so.
Suppose, say, you fire a seventh time in a cell that was only meant to have six fires. That cell was initially empty and, in order to fire seven times from there during the course of play, a total of \(14\) coins must have appeared in that cell. Since this was the first time we exceeded our alleged limits, at most 3 coins and 10 coins appeared in that cell from fires in the neighboring cells. Not enough coins!
(In general, for a cell away from the origin, with a supposed limit of \(T_n\) fires, to be the first to exceed its limit, a total of \(2T_n+2\) coins must appear in that cell during play of the game. These coins can only come from the fires of neighboring cells. And since no site has yet exceeded its limit, fires from the two neighboring cells produce at most \(T_{n-1}+T_{n+1}\) coins in the cell under consideration. But
\(2T_n+ 2 = 1+2+\cdots +n+1+2+ \cdots +n+2\)
\(=T_{n-1}+T_{n+1}+1\)
\(>T_{n-1}+T_{n+1}.\)
There are not enough coins.)
Suppose instead we first exceed our limit on the number of fires at the origin. That is, we conduct a 16th fire there. This means a total of 32 coins appeared at the origin during the play of the game. But we started with 10 or 11 coins in that position and at most 10 and 10 appear coins from the fires of its neighbors. There are not enough coins!
(In general, to have \(T_N +1\) fires from the origin – and for this site is the first to exceed its firing limit – we need \(2T_N+2\) coins to appear there during play of the game. We start with either \(2N\) or \(2N+1\) coins at the origin and receive at most \(T_{N-1}+T_{N+1}\) more from neighboring fires, as no other site yet exceeds its limit. But
\(2T_N+2=2\left(1+2+\cdots +N\right)+2\)
\(=2T_{N-1} + 2N +2\)
\(>2T_{N-1}+2N+1.\)
Again, not enough coins.)
So there is no first cell that exceeds it bound on the number of fires as given by the triangular numbers.
We have also just shown that in playing the game one conducts at most \(1+3+6+10+15+10+6+3+1=55\) fires. This means that the game cannot go on forever, and so must stop.
Theorem: A game with \(2N\) or \(2N+1\) coins must stop with at most \(T_1 + T_2 + \cdots T_N + \cdots + T_2 + T_1\) fires.
| Exercise: Prove that \(T_1 + T_2 + \cdots T_N + \cdots + T_2 + T_1\) equals the sum of the first \(N\) square numbers. |
The bound on the number of fires for each cell given by the triangular pattern shows that the two cells four places from the origin fire at most once (and no cell further away fires at all). Thus, in the final stable configuration of the game, coins “spread” at most five places left and right of the origin. Consequently, all the coins sit within a span of 11 places.
Also, in a final stable configuration, no cell contains two or more coins. Thus for a game with 11 coins, the final configuration must be a contiguous row of 11 coins centered at the origin.
For a game starting with 10 coins, the final configuration must be the same picture, but with one cell vacant.
We suspect that the vacant cell must be the origin, the center cell. How might we argue this?
Suppose, to the contrary, a non-central cell is left empty after play of the game with 10 coins. Play that game with an 11th coin sitting at the origin that one never moves. This means we end up with a configuration akin to the following picture.
Now continue playing the game using the 11th coin. One can readily see that firing now eventually places a coin six units away from the origin. That is, we have, in effect played a game with 11 coins and wandered outside its proven bounded range. This contradiction is avoided only if indeed it was the central cell left vacant during the play of 10 coins.
This arguments applies to the general cases of starting with \(2N\) and \(2N+1\) coins. We have completed our series of proofs.
| Well, not quite! We proved that each cell fires no more than the number of times indicated by the pattern of triangular numbers.
Challenge: Prove that each cell must fire precisely the triangular number of times as given by the pattern \(T_1 T_2 T_3 \ldots T_N\ldots T_3 T_2 T_1\). |
RESEARCH CORNER
Can anything be said about the sandpile patterns that result in starting with two adjacent stacks of grains? (Unequal stacks of grains? Non-adjacent stacks?)
Care to join the research work on analyzing sandpiles on square grids? On triangular grids?
© 2016 James Tanton
