3. let $n$ be a natural number. Determine the number of permutations $\left(a_{1}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$ with the following property:

$$
2\left(a_{1}+\ldots+a_{k}\right) \quad \text { is divisible by } k \text {} \quad \forall k \in\{1,2, \ldots, n\}
$$

## Solution
We call a permutation with this property good. For $n \leq 3$ all permutations are good. Furthermore, it is easy to see that for every good permutation $\left(a_{1}, \ldots, a_{n}\right)$ also the two permutations

$$
\left(a_{1}, \ldots, a_{n}, n+1\right) \quad \text { and } \quad\left(a_{1}+1, a_{2}+1, \ldots, a_{n}+1,1\right)
$$

are good. We now show that for $n \geq 3$ every good $(n+1)$ permutation arises in this way from a good $n$ permutation. Thus, there are exactly $3 \cdot 2^{n-2}$ good $n$-permutations for $n \geq 3$.

Let $\left(a_{1}, \ldots, a_{n+1}\right)$ be a good permutation. Then in particular

$$
\begin{aligned}
n \quad & 2\left(a_{1}+\ldots+a_{n}\right)=2\left(1+2+\ldots+(n+1)-a_{n+1}\right)=(n+1)(n+2)-2 a_{n+1} \\
= & n(n+3)-2\left(a_{n+1}-1\right)
\end{aligned}
$$

and therefore $2\left(a_{n+1}-1\right)$ is divisible by $n$. Because of $0 \leq 2\left(a_{n+1}-1\right) \leq 2 n$ only the possibilities $a_{n+1}=1, a_{n+1}=\frac{n}{2}+1$ and $a_{n+1}=n+1$ remain. Assume the second is the case. Similar to before, you get

$$
\begin{aligned}
& n-1 \mid 2\left(a_{1}+\ldots+a_{n-1}\right)=2\left(1+2+\ldots+(n+1)-a_{n+1}-a_{n}\right) \\
& =(n+1)(n+2)-(n+2)-2 a_{n+1}=(n-1)(n+3)-\left(2 a_{n}-3\right)
\end{aligned}
$$

and therefore $2 a_{n}-3$ is divisible by $n-1$. Because of $n \geq 3$, $-(n-1)<2 a_{n}-3<$ $3(n-1)$ now applies and only the possibilities $a_{n}=\frac{n}{2}+1=a_{n+1}$ remain, a contradiction.

Thus $a_{n+1}=1$ or $a_{n+1}=n+1$ applies. In the first case $\left(a_{1}-1, \ldots, a_{n}-1\right)$ is a good $n$-permutation, in the second case $\left(a_{1}, \ldots, a_{n}\right)$ is such a permutation. Thus, all good $(n+1)$ permutations do indeed arise from good $n$ permutations in the manner described above. This concludes the proof.