Serbian Mathematical Olympiad

Solution:

Let us denote by $F_{n}$ the number of elements of the set $A_{n}$. We have $F_{1}=1, F_{2}=2$ and $F_{3}=6$. For $n>3$, consider any permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ in $A_{n}$. Since $n-1$ divides $2\left(a_{1}+\cdots+a_{n-1}\right)=n(n+1)-2 a_{n} \equiv 2-2 a_{n}(\bmod n-1)$, it follows that $a_{n}$ equals $1, \frac{n+1}{2}$ or $n$.

Suppose that $a_{n}=\frac{n+1}{2}$. Then $n-2$ divides $2\left(a_{1}+\cdots+a_{n-2}\right)=n^{2}-1-2 a_{n-1} \equiv 3-2 a_{n-1}(\bmod n-2)$. Hence we must have $2 a_{n-1}-3=n-2$, but then $a_{n-1}=\frac{n+1}{2}=a_{n}$, a contradiction.

If $a_{n}=n$, then $\left(a_{1}, \ldots, a_{n}\right) \rightarrow\left(a_{1}, \ldots, a_{n-1}\right)$ is a bijective mapping onto the set $A_{n-1}$, so there are $F_{n-1}$ such permutations.

If $a_{n}=1$, then $\left(a_{1}-1, \ldots, a_{n-1}-1\right)$ is a permutation of $\{1, \ldots, n-1\}$ which belongs to the set $A_{n-1}$, since $2\left(\left(a_{1}-1\right)+\cdots+\left(a_{k}-1\right)\right)=2\left(a_{1}+\cdots+a_{k}\right)-2 k$ is divisible by $k$ for $1 \leqslant k \leqslant n-1$. As in the previous case, there are $F_{n-1}$ such permutations.

We conclude that $F_{n}=2 F_{n-1}$ for $n>3$, which together with $F_{3}=6$ gives $F_{n}=3 \cdot 2^{n-2}$ for $n \geqslant 3$.