Solution-1

Answer: All distributions where \(\sum_{i=1}^{n} i c_{i}=\frac{n(n+1)}{2}(\bmod n)\), where \(c_{i}\) denotes the number of coins the \(i\)-th child starts with.

Number the children \(1, \ldots, n\), and denote the number of coins the \(i\)-th child has by \(c_{i}\). A step of this process consists of reducing some \(c_{i}\) by \(2\), and increasing \(c_{i-1}, c_{i+1}\) by \(1\). (Indices are considered \((\bmod n)\).) Because \((i-1)-2 i+(i+1)=0\), the quantity \(\sum_{i=1}^{n} i c_{i}(\bmod n)\) will be invariant under this process. Hence a necessary condition for the children to end up with an uniform distribution of coins is that

\[\sum_{i=1}^{n} i c_{i}=\frac{n(n+1)}{2} \quad(\bmod n)\]

We will show that this condition is also sufficient. Consider an arbitrary initial distribution of coins. First, whenever child \(i\) has more than one coin and \(i \neq n\), have child \(i\) pass coins to its neighbors. (Child \(i\) does nothing.) Then, after some amount of such steps, it must eventually become impossible to do any more steps because no child except perhaps child \(i\) has more than 1 coin. (To see this, consider e.g. the quantity \(\sum_{i=1}^{n-1} i^{2} c_{i}\), which (as \((i-1)^{2}+(i+1)^{2}>2 i^{2}\)) increases at each step.) Hence we can reach a state of the form \(\left(z_{1}, \ldots, z_{n-1}, M\right)\), where \(z_{i}=0\) or 1 . Call such states semi-uniform states of irregularity \(M\). **Lemma:** If there is a string of children having coins \(a, \overbrace{1, \ldots, 1}^{k \text { ones }}, b, \overbrace{1, \ldots, 1}^{k \text { ones }}, c\), with \(b \geqslant 2\), after some sequence of steps we may reach the state \(a+1, \overbrace{1, \ldots, 1}^{k \text { ones }}, b-2, \overbrace{1, \ldots, 1}^{k \text { ones }}, c+1\). We call performing this sequence of steps long-passing coins. *Proof:* This is simply repeated application of the operation. We prove the lemma by induction on \(k\). For \(k=0\), this is just the operation of the problem. If \(k=1\), have the child with \(b\) coins pass coins, then both of their neighbors pass coins, then the child with \(b\) coins pass coins again. For \(k \geqslant 2\), first, have the child with \(b\) coins pass coins, then have both their neigbors send coins, giving the state

\[a, \overbrace{1, \ldots, 1}^{k-2}, 2,0, b, 0,2, \overbrace{1, \ldots, 1}^{k-2 \text { ones }}, c.\]

Now set aside the children with \(a, b\) and \(c\) coins, and have each child with 2 coins give them to their neighbors until there are no such children remaining. This results in the state

\[a+1,0, \overbrace{1, \ldots, 1}^{k-2}, b, \overbrace{1, \ldots, 1}^{\text {ones }}, 0, c+1.\]

By the induction hypothesis, we can have the child with \(b\) coins may pass a coin to each of the children with 0 coins, proving the lemma. **Claim:** We can reach a semi-uniform state of irregularity \(M \leqslant 2\). *Proof:* If \(M>3\), because there are only \(n\) coins in total, there must be at least two children with 0 coins. Consider the arc of the circle spanned by the two such children closest to the child with \(M\) coins. It has the form

\[0, \overbrace{1, \ldots, 1}^{a \text { ones }}, M, \overbrace{1, \ldots, 1}^{b \text { ones }}, 0\]

If \(a=b\), applying the previous lemma we can have the child with \(M\) coins long-pass a coin to each of the children with 0 coins, which yields a semi-uniform state with lower \(M\). Otherwise, WLOG \(a>b\), so we can have the child with \(M\) coins long-pass a coin to each of the children at distance \(b\) from it, reaching a state of the form \((\alpha:=a-b-1, \beta:=b)\)

\[0, \overbrace{1, \ldots, 1}^{\alpha \text { ones }}, 2, \overbrace{1, \ldots, 1}^{\beta \text { ones }}, M-2, \overbrace{1, \ldots, 1}^{c \text { ones }}\]

The children in the rightmost string of ones need make no further moves, so consider only the leftmost string. If \(\alpha<\beta\), have the child with \(2\) coins long-pass coins to the child with \(0\) coins to its left and some child with \(1\) coin to its right, reaching a new state of the form \(\overbrace{}^{\alpha \text { ones }} \beta\) ones

\[0, \overbrace{1, \ldots, 1}^{\alpha \text { ones }}, 2, \overbrace{1, \ldots, 1}^{\beta \text { ones }}, M-2\]

with a smaller \(\beta\). As \(\beta\) cannot decrease indefinitely, eventually \(\alpha \geqslant \beta\). If \(\alpha=\beta\), have the child with \(2\) coins long-pass to the child with \(M\) coins and the child with 0 coins, reaching a semi-uniform state of irregularity \(M-1\) as desired. Otherwise, \(\alpha<\beta\), so have the child with 2 coins long-pass to the child with \(M\) coins and a child with 1 coin, reaching a state of the form

\[0, \overbrace{1, \ldots, 1}^{x \text { ones }}, 2, \overbrace{1, \ldots, 1}^{y \text { ones }}, 0, \overbrace{1, \ldots, 1}^{z \text { ones }}, M-1\]

Now, consider only the substring between the two children with \(0\) coins, which has the form

\[0, \overbrace{1, \ldots, 1}^{x \text { ones }}, 2, \overbrace{1, \ldots, 1,0}^{y \text { ones }}, 0.\]

Repeatedly have the child in this substring with \(2\) coins long-pass to the closest child with 0 coins and some other child. If the other child has \(1\) coin, we have a new strictly shorter substring of the form \(0, \overbrace{1, \ldots, 1}^{x \text { ones }}, 2, \overbrace{1, \ldots, 1}^{y \text { ones }}, 0\). Hence eventually it must happen that the other child also has \(0\) coins, at which point we reach a semi-uniform state of irregularity \(M-1\), proving the claim. We have now shown that we can reach a semi-regular state of irregularity \(M \leqslant 2\), If \(M=1\), each child must have one coin, as desired. Otherwise, we must have \(M=2\), so there is one child with 0 coins, one child with \(2\) coins, and the remaining children all have \(1\) coin. Recall that the state we started with satisfied the invariant

\[\sum_{i=1}^{n} i c_{i}=\frac{n(n+1)}{2} \quad(\bmod n)\]

Because each step preserves this invariant, this must also be true of the current state. Number the children so that the child with \(M\) coins is child number \(n\), and suppose the child with 0 coins is child \(k\). Then

\[\frac{n(n+1)}{2}=\sum_{i=1}^{n} i c_{i}=\left(\sum_{i=1}^{n} 1 \cdot c_{i}\right)-k=\frac{n(n+1)}{2}-k(\bmod n),\]

so \(k=0 \pmod {n}\). But this is impossible, as no child except the child with \(M\) coins has an index divisible by \(n\). Hence we cannot end up in a semi-regular state of irregularity \(2\), so we are done.