Chip-Firing

Today we'll look at some explorations based on the chip-firing game.

Setup

For this activity, you'll need some graphs and counters. Here are some graph worksheets you can use. For counters, the usual things like bingo chips or beads will work. I've made the vertices large to accommodate poker chips or counters that take up more space.

The premise of the chip-firing game is simple. A graph starts out with some number of counters distributed on the vertices. Each turn, the player chooses a vertex with at least as many counters on it as it has neighbors and then moves one counter from that vertex to each neighbor. This is called "firing" at that vertex. This continues until no moves are possible, which we'll call a dead-end, or we end up revisiting configurations.

Example

Here is a graph with the number of chips on each vertex given as a number:

Here is a sequence of moves that leaves that graph in a configuration where no further moves are possible:

Challenges

1. Suppose you have a long path with \(5\) chips stacked at one end.

   

   What is the farthest vertex from the start that you can end with a chip on?

2. How do things change if you start the pile on the second vertex from the left? Third?

3. What if you start with a pile of \(6\) chips on the leftmost vertex? \(7\) chips? \(8\)?

4. Suppose you have a cycle with \(5\) vertices and start with five chips all on one vertex.

   

   Can you find a sequence of moves that ends with no further moves possible?

5. What about \(6\) chips starting all on one vertex of a \(6\)-cycle? \(7\) chips on a \(7\)-cycle? \(8\) chips on an \(8\)-cycle?

6. If there was an \(n\)-cycle that you couldn't steer to a dead-end, is there a different way to set up \(n\) chips so that it can reach a dead end? Can you find such an arrangement close to starting with all of them on a single vertex?

7. Taking a cycle with an even number \(n\) of vertices, take \(n\) chips and place half of them on one vertex and half on another. Can you steer it to a dead-end? Does this depend on which vertices you choose?

Notes

• For cycles, if we label the vertices \(v_0, v_1, v_2, ..., v_{n-1}\), then firing on vertex \(k\) sends a chip to \(k-1 \,\, (\textrm{mod } n)\) and another to \(k+1 \,\, (\textrm{mod } n)\). In particular, if we look at the chips and add up their corresponding vertex indices, if the sum was \(s \,\, (\textrm{mod } n)\) before the firing, it is

  \[ (s-2k) + (k-1) + (k+1) \equiv s \,\, (\textrm{mod } n) \]

  after the firing. In particular, if we can reach a dead-end, the sum of the vertices of the chips must be the same at the end as when we started.

  Since each of the \(n\) vertices has degree \(2\), the only way to dead-end with \(n\) chips is to end with one chip on each vertex. This would mean a starting sum of

  \[ s = n \cdot k \equiv 0 \,\, (\textrm{mod } n) \]

  and an ending sum of

  \[ s = 0 + 1 + 2 + ... + (n-1) = \frac{n(n-1)}{2} \,\, (\textrm{mod } n) \]

  If \(n\) is odd, this last sum is \(s \equiv 0 \,\, (\textrm{mod } n)\). However, if \(n\) is even, this last sum is \(s \equiv n/2 \,\, (\textrm{mod } n)\). This allows us to rule out the possibility of a dead-end when \(n\) is even. It turns out that a dead-end is possible when \(n\) is odd.

• For paths, if we label the vertices \(v_0, v_1, v_2, v_3, v_4, ... \) from left to right and start with a stack of \(n\) chips on \(v_0\), then the game can dead-end with one chip each on vertices \(v_1, ..., v_n\). To see this, you can see that it's true for \(n = 1\). Then assume that for \(n\) chips you are able to end with a chip each on \(v_1, ..., v_n\). Starting with \(n+1\) chips, you can play with just \(n\) of them, leaving a chip each on vertices \(v_0, v_1, ..., v_n\). That chip on \(v_0\) can still move, however, and you will be able to propagate a chip forward each turn, eventually reaching a state forward each turn, either from \(v_0\) itself or because two chips sit on some other \(v_i\), eventually ending with a chip on each of \(v_1, ..., v_{n+1}\).

• It's not at all obvious, but it turns out that if a chip-firing game can end in a dead-end configuration, that is the only configuration it can end in. The kernel of the argument is that firing at a vertex decreases the chips at that vertex and either increases or leaves along the number of chips at all other vertices. This means that if we have a choice of firing at vertex \(v\) or vertex \(w\), if we choose \(v\), \(w\) remains fireable until we fire it, since the number of chips on it cannot decrease until then. This means that the game will not reach a dead-end until \(w\) has been fired. Also, if we fire vertex \(v\) and then \(w\), the configuration is identical to if we had instead fired \(w\) and then \(v\). In the course of playing to a dead-end configuration, then, the exact same vertex list gets fired with the exact same multiplicities, just possibly in different orders. This gives one possible argument for why the path result above is the best possible.

Extra Challenges

• How do things change for wheels instead of cycles? For a wheel with \(n+1\) vertices (\(n\) in a cycle and \(1\) adjacent to all \(n\) of them), what configurations of \(3n-1\) chips lead to dead-ends?

• For a complete graph on \(n\) vertices, what starting configurations of \(n(n-1)\) chips lead to dead-ends?

• For a complete bipartite graph on \(m\) and \(n\) vertices, what starting configurations of \(mn\) chips lead to dead-ends?

This post was sponsored by the Julia Robinson Mathematics Festival