Exercise 8. Determine all integers $n \geqslant 1$ such that there exists a permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of $(1,2, \ldots, \mathbf{n})$ satisfying the following condition:

$$
\mathrm{k} \mid \mathrm{a}_{1}+\mathrm{a}_{2}+\ldots+\mathrm{a}_{\mathrm{k}}
$$

for all $k \in\{1,2, \ldots, \mathrm{n}\}$.
Solution to Exercise 8 We start by looking at what happens for \( n=1,2,3: n=1,3 \) are solutions but \( n=2 \) is not. Let \( n>3 \) satisfy the property stated in the problem.

We have \( n \left\lvert\, a_{1}+a_{2}+\ldots+a_{n}=1+2+\ldots+n=\frac{n(n+1)}{2}\right. \) and thus \( \frac{n+1}{2} \in \mathbb{Z}: n \) is odd.

Next, \( n-1 \left\lvert\, a_{1}+a_{2}+\ldots+a_{n-1}=\frac{n(n+1)}{2}-a_{n}\right. \).

And \( n-1 \left\lvert\, \frac{(n-1)(n+1)}{2}\right. \) so \( n-1 \left\lvert\, \frac{n+1}{2}-a_{n}\right. \).

However, there is a "size issue" : \( -(n-1) < \frac{n+1}{2} - a_{n} < n-1 \) (since \( 1 \leq a_{n} \leq n \) and \( \frac{n+1}{2} \) is an integer).

Similarly, for \( n-2 \):

\( n-2 \left\lvert\, \frac{n(n+1)}{2}-\frac{n+1}{2}-a_{n-1}=\frac{(n-1)(n+1)}{2}-a_{n-1}\right. \).

And \( n-2 \left\lvert\, \frac{(n-2)(n+1)}{2}\right. \) so \( n-2 \left\lvert\, \frac{n+1}{2}-a_{n-1}\right. \).

As before, \( -(n-2) < \frac{n+1}{2} - a_{n-1} < n-2 \) and thus \( a_{n}=a_{n-1}=\frac{n+1}{2} \): this is absurd.

The only solutions are therefore 1 and 3.

Graders' Comments

Few students fully succeeded in solving the problem. The solutions are quite diverse overall, even though they revolve around the same idea.