Proof for "coin sharing" game

Question

$m$ coins are distributed in some fashion to $n$ people arranged in a circle. A game "move" is as follows: a person that has at least two coins gives two coins away, one to the person to her left and one to the person to her right. The game ends when there are no more moves.

By the pigeonhole principle, is easy to see that the game never ends when $m>n$. If $m=n$, the game can end or continue forever, depending on the initial distribution of coins. I'm looking for a proof that the game always ends when $m<n$.

---

This is not from a book. Someone (don't know who) wrote a math enrichment lesson based on it (pigeonhole principle, etc.) but did not provide a proof. I'm trying to reuse it for another lesson.

Coin sharing can be simultaneous, but it turns out that this is not important, the "moves" can be performed in any order (I don't have a nice proof for this either).

I tried assigning to each position a number that decreases with each move, for example the maximum average for blocks of adjacent people that have at least one coin.
If you do all the coin exchanges inside a block of adjacent people with at least one coin each, only the people at the two ends are affected (they lose a coin).

I also tried induction (without success, obviously). A block of adjacent people with a total of coins acts, in some ways, like a block of −1 people with a total of −1 coins.

Another interesting fact (again, without proof) is that no coin will do a complete revolution around the circle.

Answer 1

The game you are considering is called a "Chip-Firing Game" in the literature, and variants of this game are fairly well studied. In particular, the problem you have posed (as well as several related problems) are solved in this paper (Chip Firing Games on Graphs - Bjorner, Lovasz, and Shor).

For ease of reference, I will paraphrase the proof below:

---

Let $G$ be a graph with $n$ vertices, $m$ edges, and $N$ chips assigned to its vertices.

In a step of the game, a vertex $v$ with more chips than its degree "fires" $deg_v$ many chips, one to each of its neighbors. The game ends when no vertex can fire.

Theorem (Bjorner, Lovasz, Shor):

• If $N > 2m-n$ the game is infinite
• If $m \leq N \leq 2m-n$ there exists initial configurations guaranteeing either a finite or an infinite game
• If $N < m$ then the game is finite

I will only summarize the proof of the last bullet - the rest is in the linked paper.

Let $f(v)$ denote the chips on node $v$. Consider an acyclic orientation of $G$, and let $T = \Sigma_v \max\{0, f(v) - \deg^+(v)\}$. This is the quantity we will show decreases.

Call a node $u$ deficient if $f(u) < \deg^+(u)$. Since $N < m$, there must exist a deficient node. Consider the first $v$ that is fired. Clearly $f(v) \geq \deg(v)$. After firing, reverse the orientation of all edges leaving $v$. We do not create a cycle, and moreover we do not increase $T$.

Edit (clarification of why $T$ is nonincreasing): Note the summand of $T$ corresponding to $v$ decreases by $\deg(v) - \deg^+(v)$. This is because we lose $\deg(v)$ many chips on $v$, but we are no longer subtracting the $\deg^+(v)$ many outgoing edges (since we flipped them). However, for each neighbor $u$ of $v$, if it was connected by an outgoing edge of $v \to u$, the $T$ summand of $u$ does not increase (since $f(u)$ and $\deg^+(u)$ both increase by $1$. If instead $u$ is among the $\deg(v) - \deg^+(v)$ vertices such that $u \to v$ is an edge, then the $T$ summand corresponding to $u$ increases by at most $1$.

Indeed if a node $u$ adjacent to $v$ is deficient, then $T$ decreases. If none of the adjacent vertices was deficient, then the set of deficient nodes did not change.

Thus $T$ decreases over time (since eventually nodes which used to be deficient will have to fire, and $T$ decreases each time this happens), and the game is finite.

---

A good example to play with to get comfortable with how the proof works is the following graph:

I've fixed an initial orientation in advance, but you could do it with any (acyclic) orientation you please.

---

Of course, for your example we can take $G$ to be a cycle on $n$ vertices, and so $n=m$. The part of the theorem we just proved, then, says that if the number of coins $N$ is less than $n$, the game always terminates. As desired.

---

Thanks for the problem! Researching a solution led to a lot of cool places.

Hope this helped ^_^

Answer 2

Start by labeling the coins $c_1, \cdots, c_m$.

Lemma 1: If we pick a person and don't allow them to pass coins, the game terminates.

proof: Label the people $1$ through $n$ counterclockwise starting with the person that can't pass. For a coin $c$, let $p(c)$ denote the number of the person holding $c$. Then the variant

$$\sum_{i = 1}^m p(c_i)^2$$

increases on each move so the process terminates.

We will describe a sequence of moves by the sequence of the people passing.

Lemma 2: If one sequence of moves terminates, then all sequences of moves terminate.

proof: Suppose towards a contradiction that the sequence of moves $a_1, \cdots, a_k$ (remeber $a_1, a_2, \cdots a_k$ are people) terminates but another sequence $b_1, b_2, \cdots$ is infinite. Let $i$ be the minimal index such that there is a person who appears more times in the sequence $b_1, \cdots, b_i$ than in $a_1, \cdots, a_k$.

Then this person is $b_i$ and the number of coins $b_i$ has after a sequence of moves is the number of coins $b_i$ had initially, minus twice the number of times they passed, plus the number of times a neighbor of theirs has passed.

But now we see that $b_i$ has at least two more coins after the sequence $a_1, \cdots, a_k$ than after the sequence $b_1, \cdots, b_i$ but this contradicts $a_1, \cdots, a_n$ being a terminating sequence.

---

By lemma two, it suffices to find a terminating sequence of moves. Define a base position to be a position where all but one person has at most one coin.

Define the height of a position to be the maximum number of coins a person has. The problem is equivalent to showing that we can get to a position with height one.

By lemma 1, we can get to a base position. Thus it suffices to show if we are in a base position with height greater than one, then we can transition to a base position with strictly smaller height which we will prove below:

proof: Suppose we are in a base position with height $h > 1$ and let $p$ be the person with $h$ coins. Label $h - 1$ of his coins bad, and label every other coin as good which means everyone has at most one good coin. By pigeon hole, there is a person $q$ with no coins.

We will perform a sequence of strings of moves so that the following hold:

• $q$ never passes.
• At the end of every string of moves, each person has at most one good coin.
• $q$ never receives any good coins.

If we can find moves as above, by lemma 1 the process will eventually terminate at which point $q$ will have at most $h-1$ coins (since there were only $h-1$ bad coins) and everyone else will have at most one coin so we will be in a base position with height smaller than $h$ and we will be done.

Contsruction of Above Moves: Say a state is calm if every person has at most one good coin and $q$ has no good coins. Suppose we are in a calm state and $r$ is a person other than $q$ with more than one coin. We need to show there exists a string of moves that doesn't involve $q$ passing that results in another calm state.

• Case 1: $r$ has no good coins: Then $r$ passes two bad coins and the resulting state will be calm.

• Case 2: $r$ has a good coin: Then by pigeon hole, there is a person $s$ other than $q$ with no good coins. WLOG suppose the clockwise arc from $r$ to $s$ does not pass through $q$. (Otherwise the counter-clockwise arc doesn't pass through $q$) Then $r$ passes his good coin clockwise and while any person has two good coins, that person passes them. This string of moves is a clockwise string of adjacent moves starting at $q$ and must result in a calm state before reaching $s$.

So we have constructed the moves and are done.