$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.
Best Answer
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):
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 ^_^