C2. For every positive integer $n$ determine the number of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$ with the following property:
$2\left(a_{1}+a_{2}+\cdots+a_{k}\right) \quad$ is divisible by $k \quad$ for $k=1,2, \ldots, n$.
Solution. For each $n$ let $F_{n}$ be the number of permutations of $\{1,2, \ldots, n\}$ with the required property; call them nice. For $n=1,2,3$ every permutation is nice, so $F_{1}=1, F_{2}=2, F_{3}=6$.

Take an $n>3$ and consider any nice permutation $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of $\{1,2, \ldots, n\}$. Then $n-1$ must be a divisor of the number
$$
\begin{array}{l} 
2\left(a_{1}+a_{2}+\cdots+a_{n-1}\right)=2\left((1+2+\cdots+n)-a_{n}\right) \\
\quad= n(n+1)-2 a_{n}=(n+2)(n-1)+\left(2-2 a_{n}\right) .
\end{array}
$$

So $2 a_{n}-2$ must be divisible by $n-1$, hence equal to 0 or $n-1$ or $2 n-2$. This means that
$$
a_{n}=1 \quad \text { or } \quad a_{n}=\frac{n+1}{2} \quad \text { or } \quad a_{n}=n .
$$

Suppose that $a_{n}=(n+1) / 2$. Since the permutation is nice, taking $k=n-2$ we get that $n-2$ has to be a divisor of
$$
\begin{aligned}
2\left(a_{1}+a_{2}+\cdots+a_{n-2}\right) & =2\left((1+2+\cdots+n)-a_{n}-a_{n-1}\right) \\
& =n(n+1)-(n+1)-2 a_{n-1}=(n+2)(n-2)+\left(3-2 a_{n-1}\right) .
\end{aligned}
$$

So $2 a_{n-1}-3$ should be divisible by $n-2$, hence equal to 0 or $n-2$ or $2 n-4$. Obviously 0 and $2 n-4$ are excluded because $2 a_{n-1}-3$ is odd. The remaining possibility $\left(2 a_{n-1}-3=n-2\right)$ leads to $a_{n-1}=(n+1) / 2=a_{n}$, which also cannot hold. This eliminates $(n+1) / 2$ as a possible value of $a_{n}$. Consequently $a_{n}=1$ or $a_{n}=n$.

If $a_{n}=n$ then $\left(a_{1}, a_{2}, \ldots, a_{n-1}\right)$ is a nice permutation of $\{1,2, \ldots, n-1\}$. There are $F_{n-1}$ such permutations. Attaching $n$ to any one of them at the end creates a nice permutation of $\{1,2, \ldots, n\}$.

If $a_{n}=1$ then $\left(a_{1}-1, a_{2}-1, \ldots, a_{n-1}-1\right)$ is a permutation of $\{1,2, \ldots, n-1\}$. It is also nice because the number
$$
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 any $k \leq n-1$. And again, any one of the $F_{n-1}$ nice permutations $\left(b_{1}, b_{2}, \ldots, b_{n-1}\right)$ of $\{1,2, \ldots, n-1\}$ gives rise to a nice permutation of $\{1,2, \ldots, n\}$ whose last term is 1 , namely $\left(b_{1}+1, b_{2}+1, \ldots, b_{n-1}+1,1\right)$.

The bijective correspondences established in both cases show that there are $F_{n-1}$ nice permutations of $\{1,2, \ldots, n\}$ with the last term 1 and also $F_{n-1}$ nice permutations of $\{1,2, \ldots, n\}$ with the last term $n$. Hence follows the recurrence $F_{n}=2 F_{n-1}$. With the base value $F_{3}=6$ this gives the outcome formula $F_{n}=3 \cdot 2^{n-2}$ for $n \geq 3$.