5. In each vertex of a regular $n$-gon $A_{1} A_{2} \ldots A_{n}$, there is a certain number of coins: in vertex $A_{k}$, there are exactly $k$ coins, $1 \leqq k \leqq n$. We select two coins and move each of them to an adjacent vertex such that one moves in the clockwise direction and the other in the counterclockwise direction. Determine for which $n$ it is possible to achieve, after a finite number of such moves, that for any $k, 1 \leqq k \leqq n$, there will be $n+1-k$ coins in vertex $A_{k}$.

(Radek Horenský)
Solution. Let's assign each coin an index $i$ of the vertex $A_{i}$ on which it lies (a number from the set $\{1,2, \ldots, n\}$) and update the numbers assigned to the coins after each move of a pair of coins. First, let's see how the sum $S$ of all $n$ numbers assigned to the individual coins changes after one move.

If we do not move any of the two coins between vertices $A_{1}$ and $A_{n}$, the sum $S$ does not change, because one of the numbers assigned to the coins decreases by 1, the other increases by 1 (and the rest remain unchanged). Similarly, the sum $S$ will obviously not change if we move one coin from $A_{1}$ to $A_{n}$ and simultaneously the other from $A_{n}$ to $A_{1}$. If we move one coin from $A_{1}$ to $A_{n}$ and the other from $A_{i}$ to $A_{i+1}$ (where $1 \leqq i \leqq n-1)$, the sum $S$ will increase by $(n-1)+1=n$. Finally, if we move one coin from $A_{n}$ to $A_{1}$ and the other from $A_{i}$ to $A_{i-1}$ (where $2 \leqq i \leqq n$), the sum $S$ will decrease by $n$. From the complete analysis above, it follows that the remainder of the sum $S$ after division by $n$ never changes.

The sum $S$ in the initial position has the value

$$
1 \cdot 1+2 \cdot 2+\ldots+n \cdot n=\sum_{k=1}^{n} k^{2}=\frac{1}{6} n(n+1)(2 n+1)
$$

while in the desired target position, it should have the value

$$
\begin{aligned}
\sum_{k=1}^{n} k(n+1-k) & =(n+1) \sum_{k=1}^{n} k-\sum_{k=1}^{n} k^{2}= \\
& =\frac{1}{2} n(n+1)^{2}-\frac{1}{6} n(n+1)(2 n+1)=\frac{1}{6} n(n+1)(n+2)
\end{aligned}
$$

(we used the known formulas for the sum of the first and second powers of the first $n$ natural numbers). To achieve the desired goal, the two specified values of $S$ must give the same remainder when divided by $n$, i.e., their difference $\frac{1}{6} n(n+1)(n-1)$ must be a multiple of the number $n$. The number $\frac{1}{6}(n+1)(n-1)=\frac{1}{6}\left(n^{2}-1\right)$ must therefore be an integer. By substituting all individual remainders 0 to 5 modulo 6, we easily find that the found condition is satisfied precisely when the number $n$ gives a remainder of 1 or 5 when divided by six. In the next part of the solution, we will show that for all such $n$ the desired target positions can indeed be achieved.

We will describe one possible procedure. (The only) coin that is initially at vertex $A_{1}$, we will call $M$. We will continuously move all coins except $M$ in the same common direction. In the opposite direction, only the coin $M$ will be moved, without us continuously "caring" about its position. Its final position will be determined using the previously derived property of the sum $S$: the index $i$ of the vertex $A_{i}$ in which the coin $M$ will eventually end up is uniquely determined by the fact that the final value of the sum $S$ gives the same remainder when divided by $n$ as the initial value - the indices of all vertices form a complete system of remainders modulo $n$.

By the proposed procedure of continuous moving of the coin $M$, we can move any of the remaining coins (independently of the other remaining coins) to any vertex we choose. After a finite number of suitable moves, we will obviously achieve that all coins different from $M$ are in each vertex $A_{i}$ with index $i>1$ in the number prescribed by the task, i.e., $n+1-i$. It is entirely irrelevant that it is precisely $n+1-i$, but what is important is that the total number of coins in the initial position and the desired target position are obviously the same, so after the mentioned "securing" of the vertices $A_{2}, A_{3}, \ldots, A_{n}$ with coins different from $M$, there will be $n-1$ remaining coins different from $M$ in vertex $A_{1}$ and the last coin $M$ will end up in some, as yet undetermined, vertex. When will this be vertex $A_{1}$, and thus the goal will be achieved? Precisely when the number of vertices $n$ is such that the sum $S$ for the initial position gives the same remainder when divided by $n$ as the sum for the target position we are striving for. And we have already found all such $n$.

Answer. The desired goal can be achieved precisely when the number $n$ gives a remainder of 1 or 5 when divided by six.

Note. The described method of solution leads to the following conclusion: Given two arrangements of the same number of coins at the vertices of an $n$-gon, one can convert one to the other by the described moving of coins, precisely when both sums $S$, corresponding to these arrangements, give the same remainder when divided by the number $n$.