
5. In each vertex of a regular $n$-gon $A_{1} A_{2} \ldots A_{n}$ there lies a certain number of coins: in the vertex $A_{k}$ there are exactly $k$ coins, for each $1 \leqslant k \leqslant n$. We choose two coins and move each of them into one of the neighbouring vertices in such a way that one is moved clockwise and the other anti-clockwise. Decide for which $n$ it is possible to achieve, after a finite number of steps, that for each $k, 1 \leqslant k \leqslant n$, there are exactly $n+1-k$ coins in the vertex $A_{k}$.


Solution. We assign to each coin the index $i$ of the vertex $A_{i}$ in which it lies (thus $i \in\{1,2, \ldots, n\}$ ), and we update these numbers after each movement. Let us observe how the sum $S$ of all these numbers can change upon a single movement.

If no coin is moved between the pair of vertices $A_{1}$ and $A_{n}$, then the sum $S$ remains unchanged, since one of the numbers assigned to the coins increases by one, while the second one decreases by one (and the other are unaffected). Similarly, $S$ does not change if we move one coin from $A_{1}$ into $A_{n}$, while moving the other coin from $A_{n}$ into $A_{1}$. If one coin is moved from $A_{1}$ into $A_{n}$ and the other from $A_{i}$ into $A_{i+1}$ (where $1 \leqslant i \leqslant n-1$ ), then the sum $S$ is increased by $(n-1)+1=n$. Finally, if we move one coin from $A_{n}$ into $A_{1}$ and the other coin from $A_{i}$ into $A_{i-1}$ (where $2 \leqslant i \leqslant n$ ), then the sum $S$ decreases by $n$. In summary, it follows that the remainder of $S$ upon division by $n$ does not change.

In the original position, the sum $S$ equals

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

while in the desired final position, it would be equal to

$$
\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 have used the familiar formulas for the sums of the first $n$ natural numbers and of their squares). Thus these two values of $S$ should give the same remainder upon division by $n$, i.e. their difference $\frac{1}{6} n(n+1)(n-1)$ should be divisible by $n$. The number $\frac{1}{6}(n+1)(n-1)=\frac{1}{6}\left(n^{2}-1\right)$ thus must be an integer. Checking all the possible values 0 to 5 of the remainders mod 6 we find that this happens if and only if $n$ has remainder either 1 or 5 upon division by 6 . In the rest of this solution, we show that for all such $n$ it is indeed possible to move the coins into the desired position.

Let us denote the (single) coin which is originally in the vertex $A_{1}$ by $M$. We will be moving all coins except $M$ in the same common direction, while the only coin moved in the opposite direction will be $M$ (and we will not be bothered about the actual position of $M$ during the process). The final position of $M$ will be determined by the above property of the sum $S$ : the index $i$ of the vertex $A_{i}$, in which $M$ finds the final position, is uniquely determined by the fact that the final value of the sum $S$ must give the same remainder upon division by $n$ as its initial value - this is so because the indices of the vertices form a complete system of remainders $\bmod n$.

Using the above procedure of permanently moving the coin $M$, we can achieve that any one of the other coins can be moved into any vertex we choose (without changing the locations of the remaining coins, except $M$ ). After a finite number of steps, we can thus achieve that there are exactly $n+1-i$ coins different from $M$ in the vertex $A_{i}$, for each $i>1$; in the remaining vertex $A_{1}$, there will be $n-1$ coins different from $M$ (since the total number of coins remains the same all the time), while the coin $M$ ends up in some - as yet unknown - vertex. If we can show that this vertex is $A_{1}$, then we are finished. However, this happens if and only if the number $n$ of vertices is such that the sum $S$ gives the same remainder upon division by $n$ in the initial and in the final position. And we have found all such $n$ in the fist part of the solution.

Answer. The coins can be moved into such position if and only if $n$ gives remainder either 1 or 5 upon division by six.
