We read all indices modulo $n$. Label the children $1, 2, \ldots, n$, and let $c_i$ be the number of coins child $i$ initially has. It is easy to show that $\sum_i ic_i$ is invariant modulo $n$, so we must have $\sum_i ic_i \equiv \tfrac12 n(n+1)\mod n$. We will show that, conversely, every such initial configuration works. Consider the system of equations \[ 2x_i - x_{i-1} - x_{i+1} = c_i - 1, \quad 1\leq i\leq n. \]The facts that $\sum_i (c_i-1) = 0$ and $\sum_i i(c_i-1) \equiv 0 \mod n$ imply that this system has a solution in the integers. (This is a pretty straightforward calculation, thus omitted.) If we add a constant to each $x_i$, we still have a solution, so the system has a solution in the natural numbers. Now let us take $x_i\in\mathbb{N}$ such that $2x_i - x_{i-1} - x_{i+1} = c_i - 1$. We apply the following algorithm: while there is a child with at least two coins, who has distributed less than $x_i$ times thus far, we let this child distribute two of their coins. Note that this procedure ends after at most $\sum_i x_i$ moves. We claim that, at the end of the procedure, every child has exactly one coin. Suppose this is not true. Then at the end of the procedure, there exists a child, say child $i$, with at least two coins. By construction of the algorithm, child $i$ must have distributed exactly $x_i$ times. Moreover, children $i-1$ and $i+1$ have distributed at most $x_{i-1}$ and $x_{i+1}$ times respectively. Thus, the net gain of child $i$ is at most $x_{i-1} + x_{i+1} - 2x_i$ coins. This means that child $i$ currently has at most $c_i + (x_{i-1} + x_{i+1} - 2x_i) = c_i - (c_i - 1) = 1$ coin, a contradiction. Thus, we can conclude that the procedure ends in the desired configuration.

My favorite C from the shortlist. In fact, it's true that every valid configuration has to terminate no matter how the moves are performed. I had a solution that relied on making the sums from all cyclic orderings equal that I'll post later.

Label the children 1, 2, \(\ldots\), \(n\) and let them have \(a_1\), \(a_2\), \(\ldots\), \(a_n\) coins, respectively (with indices modulo \(n\)). Note that \(a_1+2a_2+\cdots+na_n\) is invariant modulo \(n\), so for the desired distribution to be reachable, we must have \[n\;\Bigg|\;\sum_{i=1}^ni(a_i-1).\tag{\(\star\)}\]We show that if the initial distribution satisfies the above, then the desired distribution is reachable. Choose integers \(d_1\), \(\ldots\), \(d_n\) such that \[x_i-1=d_i-d_{i+1}\quad\text{for all }i.\]With \((\star)\), we can check that \(n\mid d_1+\cdots+d_n\), so by shifting \(d_i\) appropriately, we may set \(d_1+\cdots+d_n=0\). Then we may choose integers \(a_1\), \(\ldots\), \(a_n\) such that \[d_i=a_i-a_{i-1}\quad\text{for all }i \quad\text{and}\quad\min_ia_i=0.\]Thus we have nonnegative integers \(a_1\), \(\ldots\), \(a_n\) with \[x_i-1=2a_i-a_{i-1}-a_{i+1}\quad\text{for all }i.\] While there exists \(i\) with \(x_i\ge2\), note that \[1\le x_i-1\le2a_i\implies a_i\ge1,\]so decrease \(a_i\) by 1. This is equivalent to decreasing \(x_i\) by 2 and increasing \(x_{i-1}\) and \(x_{i+1}\) by 1. Do this until \(x_i\le1\) for all \(i\), and of course equality holds.

Here is a ring-theoretic way to think about this problem. Number the kids from $0$ to $n-1$ and let the $k$-th child have $c_k$ coins. Associate each configuration $(c_0, c_1, \dots, c_{k-1})$ with the polynomial $c_0 + c_1x + \dots + c_{n-1} x^{n-1}$. Then a step performed on the $k$-th child is equivalent to adding $x^{k+1} - 2x^k + x^{k-1} = x^{k-1}(x-1)^2$ to the polynomial, where $x^n = 1$. So we are working over the ring $\mathbb{Z}[x]/{\left(x^n - 1, (x-1)^2\right)}$ and we wish to find which polynomials are equivalent to $1 + x + \dots.+ x^{n-1}$. Note $x^n - 1 \equiv n(x-1) \pmod{(x-1)^2}$ so really the ring is $\mathbb{Z}[x]/{\left((x-1)^2, n(x-1)\right)} \simeq \mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z}$ given by \[c_0 + c_1x + \dots + c_{n-1} x^{n-1} \mapsto \left( \sum c_k, \left(\sum kc_k \bmod{n}\right) \right).\]Under this equivalence, we have $1 + x + \dots + x^{n-1} \mapsto (n, \tbinom{n}{2} \bmod{n})$, which basically finishes the problem minus some annoying positivity conditions. This has the advantage of basically solving the problem for any operation which is cyclically symmetric. @2below, yeah this is prolly true LOL; but I'd expect some hands-on ``Euclidean algorithm"-y trick to do the job but maybe I'm mistaken. in any case it helps get the right answer

Wow, a generalization of 1994 Shortlist C5!

A very disappointing problem to see on the SL if you're familiar with some chip-firing results; basically the entire problem can be solved by quoting one of the most famous chip-firing theorems, namely: Quote: In a chip-firing process on a finite simple connected graph, where there are fewer chips than graph edges, the process must terminate. Here it is in action: Enumerate the children with residues modulo $n$ in order. The task is possible if and only if \[ \sum_{c\text{ coin}} \text{child with coin } c = 0 + \dots + (n-1). \quad (\ast) \]The left-hand side is an invariant under moves, so this is necessary. To see it is sufficient, the idea is to ignore one of the coins. Now, there are only $n-1$ coins, so regardless of how the children trade coins, the process must terminate. Then, each child will have one coin, except for one child who has none. Here's the magical part. Add in the ignored coin. By $(\ast)$, the ignored coin must belong to the last child, and we're done! Th3Numb3rThr33 wrote: Under this equivalence, we have $1 + x + \dots + x^{n-1} \mapsto (n, \tbinom{n}{2} \bmod{n})$, which basically finishes the problem minus some annoying positivity conditions. Maybe I'm misreading, but I disagree that this "basically finishes" the problem, because I think the "annoying positivity conditions" are the entire content of this problem. If you permit children to have negative numbers of coins, the problem is much easier.

Suppose the $i$th child has $a_i$ coins. We claim that it is possible for each child to have exactly one coin if and only if $\displaystyle\sum_{i=1}^nia_i\equiv\frac{n(n+1)}2\pmod n$. Take all indices modulo $n$. If it is possible for each child to have one coin, then each transfer decreases $a_i$ by $2$ and increases $a_{i-1}$ and $a_{i+1}$ by $1$, so $\displaystyle\sum_{i=1}^nia_i$ changes by $(i-1)+(i+1)-2i\equiv0\pmod n$. The process ends when $\displaystyle\sum_{i=1}^nia_i\equiv\sum_{i=1}^ni\equiv\frac{n(n+1)}2\pmod n$, so we must have $\displaystyle\sum_{i=1}^nia_i\equiv\frac{n(n+1)}2\pmod n$. Now, suppose $\displaystyle\sum_{i=1}^nia_i\equiv\frac{n(n+1)}2\pmod n$. Let $\displaystyle\sum_{i=1}^ni(a_i-1)=cn$. Consider the equations

All of the $x_i$ are integers, so adding a large constant to all of the $x_i$ makes them all nonnegative, and they still satisfy the equation. Now, we claim each child must pass at most $x_i$ times. Suppose not. Take the smallest time when child $i$ passed more than $x_i$ times. Then, that child has at most $a_i-2(x_i+1)+x_{i-1}+x_{i+1}=a_i-2+1-a_i=-1$ coins, contradiction. Therefore, each child passes coins finitely many times, so the process must end in finite time, which means each child has one coin when the process ends. Therefore, each child has one coin if and only if $\boxed{\sum_{i=1}^nia_i\equiv\frac{n(n+1)}2\pmod n}$.

Numerate children by $1,2, \ldots ,n$ counterclockwise, and let the $i-$th child initially have $a_i$ coins (indices are taken modulo $n$). We claim, that the answer are all distributions for which $\sum_{\text{cyc}} ia_i\equiv \frac{n(n+1)}{2} \pmod n.$ Note that LHS modulo $n$ is the invariant under operations, so this equivalence is necessary. Next, assume that given distribution satisfy the condition. Observe that the system of equations $$1-a_i=x_{i-1}-2x_i+x_{i+1}$$have a solution in integers. Indeed, we have $x_{i-1}=1-a_i-2x_i+x_{i+1},$ so by induction $$x_1=\frac{n(n+1)}{2}-\sum_{\text{cyc}}^n ia_i -nx_2+(n+1)x_1\implies (x_1-x_2)\in \mathbb Z,$$and all $x_i$ are expressed as polynomials with integer coefficients from $x_1,x_2,$ giving the proclaimed result. Moreover, adding a constant to all $x_i$ we also get a solution, so the system has a solution in positive integers - henceforth we use a such one. Now let $i-$th child, who has at least two coins and had performed less than $x_i$ steps, make a turn. After at most $\sum x_i$ steps this process terminates - we claim that the resulting configuration satisfies. FTSOC the $m-$th child has at least $2$ coins after this point; therefore he had performed exactly $x_m$ steps. But then he has at most $a_i+x_{m-1}-2x_m+x_{m+1}=1$ coin, contradiction. The conclusion follows.

Let the children be $C_1,C_2,\dots,C_n$. Let $c_i$ be the number of coins $C_i$ has. Note that $\sum_{i=1}^{n}{ic_i}\pmod n$ is invariant, so we need \[c_1+2c_2+\dots +nc_{n}\equiv 1+2+\dots + n\pmod n\]We claim that this is enough. Consider equations \[1-c_i=d_i-d_{i-1}\]and note that $d_1+d_2+\dots+d_n\equiv 0\pmod n$, so WLOG assume it equals $0$. Therefore, set $d_i=e_{i+1}-e_{i}$ so that $1-c_i=e_{i+1}-2e_i+e_{i-1}$. Indeed, if we decrease a value $e_i$ by one, then the value of $c_i$ is decreased by $2$ and the values of $c_{i-1}$ and $c_{i+1}$ is each increased by one, so decreasing an $e_i$ by one is a single step. Thus, decrease all of them so that $e$ is constant, so $d$ is constant, so $c$ is constant, we're done.

First, let some child be the $0$th, and let the child $i$ clockwise from the $0$th child be the $i$th child, for $0 \le i \le n-1.$ Let the $i$th child start with $a_i+1$ coins, for some integers $a_i.$ We will show that it is possible for each child to have exactly one coin if and only if $S=\sum_{i=0}^{n-1} ia_i \equiv 0 \pmod{n}.$ First, notice that $S \pmod{n}$ is an invariant, and at the end, it clearly must be $0,$ so initially, it must be as well. Now, consider a sequence $M$ of moves, such that the $i$th child gives coins $K+(n-i) \frac{S}{n} - \sum_{j=1}^{n-i-1} ja_{i+j}$ times, where $K$ is an arbitrary constant large enough to make the expression positive for all $i.$ We can easily check that following this sequence of moves, every child ends up with exactly $1$ coin. Notice that this sequence may be invalid, as it is possible that it results in some child having a negative amount of coins at some time. Now we will show that there is a rearrangement of the sequence $M$ in which no child ever has a negative amount of coins. Suppose otherwise; then consider the rearrangement of $M$ that has the latest first invalid move. Consider the situation before the invalid move is performed. Clearly there must be some child $C$ with at least $2$ coins, as otherwise all children would have exactly one. We also know that $C$ does not give coins later in the sequence, or we could swap the positions of the invalid move and the move where $C$ gives coins to create a rearrangement with a later first invalid move. However, the number of coins that $C$ has must decrease, since at the end he will have one coin, but his number of coins can only decrease if he gives coins, which is a contradiction. Therefore, there is a rearrangement of $M$ that is valid, so we are done.

Let the children be roots of unity. Obviously, the product of the children is preserved, so we must have that the product of the children is the product of the roots of unity to finish. Now we show this is sufficient. Take the obtainable configuration with: 1. Minimal value of the sum of squares of the number of children per element. 2. Minimal total number of elements inside of some nonzero contiguous block of nonzero elements with an element that has $\geq 2$ children on it. I claim this must be either all $1$s or a single $2$, a single $0$, with the rest being $1$s. Basically, take that contiguous block and operate on all its elements starting from the element with $\geq 2$ children and working your way out. If either end of the contiguous block has $\geq 2$ children, this operation will decrease the sum of squares in the first condition. Otherwise, the length of the contiguous block decreases by $2$, decreasing the second condition. The only case where this operation fails is if the contiguous block contains either all $n$ elements or $n-1$ of the elements. These correspond to the two equality cases respectively. Notice that whether a config falls into the all $1$ case or a single $2$, a single $0$, with the rest being $1$s case is exactly equivalent to whether the product is equal to the product of all the roots of unity, so we are done.

Here is the official solution. An easy sol with Generating Function.

More about it......

AND MORE .......

posting for storage but i didn't solve :sadge: So basically you realize that it probably makes sense that we can get pretty close to the value. This motivates mods. Unfortunately I didn't see the invariant though I think it's a consequence of some other 2011 problem I've seen. Welp. Now creating the system of equations is pretty natural. At this point I tried to scale one of the values down to $0$ and then induct. Pretty sad though, since if the required number of moves is $x_i$ at a certain configuration and we assume that some value $a_i\ge 2$ Then clearly \[2x_i-x_{i+1}-x_{i-1}=a_i-1\]and now $x_i\ge 1$ and we just move this coin which just works. (The system of equations has an integer solution thanks to the invariant) AHHHHHHHHHHHHHHHHHHHHHHHHHHHHH.

Solved with ishan, amoghsus, C9, stqrlight. USAMO 2011/2

HamstPan38825 wrote: Solved with ishan, amoghsus, C9, stqrlight. USAMO 2011/2 Solved without ishan, amoghsus, C9, stqrlight. ELMO Shortlist 2023/C8

Label the kids $c_1,c_2,\dots,c_n$ and let them each have $g_1,g_2,\dots,g_n$ gifts, respectively. The arrangement works iff, $$\sum_{i=1}^{n}{ig_i}\equiv \frac{n(n+1)}{2}\pmod{n}$$The first direction is clear as the sum on the right is invariant. Now we need to show that all such configurations work. If you never let $c_1$ pass gifts then you must reach a state where all other $c_i$ have $1$ or $0$ gifts as you are never able to visit the same configuration twice. Now if $c_1$ passes gifts and they continue down the line it pushes blocks of $1$'s away from $c_1$ or fills in a $1$ adjacent to $c_0$. If $g_1\geq 3$ it is not hard to see that such a move will still result in all other $c_i$ having $1$ or $0$ coins. It is not hard to see $g_1=2$ is impossible. This finishes the construction.