Chip-Firing Games

Have you ever been at the beach with a handful of sand, sprinkling the tiny grains such that they begin to form a perfect cone? But while you’re admiring this beautifully symmetric creation, a process of destruction inevitably begins to take place. Starting with a single grain of sand beginning to slip, it will crash into multiple other grains causing it also to slip, and you can only watch in horror as one grain after another cascades into each other and an entire face of your beautiful sand cone collapses!

However, to many of us, that dramatic avalanche of sand might not only trigger grief, but also a primal longing to model this network of sand in which, individual stacks of sand are able to send sand to adjacent stacks, leading to these destructive avalanches.

Well if that is you, look no further, because we will now find such a model once and for all!

First, we need to decide what our network will be, and how we will represent sand. Our best choice for the network is the tried and true connected graph $G(V,E)$ where two vertices are adjacent if they share an edge. Thus we can drop individual grains of sand at each vertex, and we will call each of these grains “chips”, such that the chip configuration of our graph will be $\{c_1,c_2,...,c_n\}$ where $c_i$ is the number of chips/sand at vertex $v_i$.

Now to replicate the avalanches we saw on the beach, we also define a vertex to “fire” as sending $1$ of its chips to each adjacent vertex. This way we hope that if enough vertices fire simultaneously we will see the entire sand pile collapse. Wait! But what if a vertex has fewer chips than adjacent vertices, after all, we can’t have a stack of sand with negative sand! So we will call a vertex $v_i$ “ready to fire” iff the vertex has more chips than adjacent vertecies (ie. $c_i>$), and our model will consist of choosing a vertex that is “ready to fire”, firing it, then repeating.

This all seems great, we have created our model and can watch these avalanches without going to the beach, yet it seems slightly uncomfortable that we must choose a vertex to fire among those “ready to fire”... I mean we can’t have freedom of choice in math! But does it actually make a difference which one you choose to fire first? Let’s see what happens if we fire one vertex instead of another.

Let’s say $v_1$ and $v_2$ are both ready to fire, and we decide to fire $v_1$ first. We see that firing $v_1$ could only have increased the chips at $v_2$⁠, so $v_2$ is still able to fire! In this way, since any vertex that is ready to fire will always be ready to fire until it is actually fired, the way we select what to fire doesn’t actually matter. Aha! Once again we see that free choice is just an illusion!

Now let’s have some fun playing out this game with some different initial configurations.

Hmmm... Sometimes our model seems to reach a chip configuration where no chip is “ready to fire”, but other times it seems to go on forever. We’ll call a chip configuration in which no vertex can fire as “stable”, and these will mark the end of our game.

Now this seems to give rise to the question: which configurations will end in a stable configuration and which will go on forever?

To answer this, we’ll look at the total number of chips. If the number of total chips $c$ in the system is greater than $2m-n$⁠, where $n$ is the number of vertices and $m$ is the number of edges, then since $$\sum =2m,$$ by pigeon-hole principle one vertex will always have at least $\mathrm{deg}{v}_i$ chips. Thus there will always be a vertex “ready to fire” and our sand will move around forever.

Now let’s attempt a lower bound: What if $c$ is less than $m$? Let’s say we have a number of all the chips/sand grains prior to firing, this way they are distinct. If we begin firing vertices, we can assign each chip to the edge it first travels down. This way we can imagine that every time a vertex fires, chips just travels across the edge it was assigned, so that ways each chip is always on one of the endpoints of its assigned edge. But because $c<m$⁠, there will always be at least one edge without a chip assigned to it, which means both vertices that are the endpoints of that edge will never fire. And moreover, in a connected graph that fires forever, a vertex that never fires will always be taking up chips from its surrounding vertices, making it impossible for the graph to fire forever!