2008 IMO SL #C2

Let $n \in \mathbb N$ and $A_n$ set of all permutations $(a_1, \ldots, a_n)$ of the set $\{1, 2, \ldots , n\}$ for which

\[k|2(a_1 + \cdots+ a_k), \text{ for all } 1 \leq k \leq n.\]

Find the number of elements of the set $A_n$.

The answer is $\boxed{3 \cdot 2^{n-2}}$. 

Using the given condition, we can say that

\[ n-1 \mid 2\left(\frac{n(n+1)}{2} - a_n\right) = n(n+1) - 2a_n\]                                                                                                        $$\implies 2a_n\equiv n(n+1) \equiv 2\pmod{n-1}$$$$\implies a_n=1, a_n=\frac{n+1}{2}, \text{or } a_n=n.$$

Using the given condition repeatedly, and assuming that $a_n=\frac{n+1}{2},$ we see that

\[ n-2 \mid 2(a_1+\cdots+a_{n-2}) = 2\left[\frac{n(n+1)}{2}-\frac{n+1}{2}-a_{n-1}\right] = n^2-1 - 2a_{n-1},\]

$$\implies 2a_{n-1} \equiv n^2-1 = (n+1)(n-1)\equiv 3\pmod{n-2}$$

So, $a_{n-1}=\tfrac{n+1}{2}$, which means that $a_n \neq \frac{n+1}{2}$. Contradiction. Thus, $a_n=1$ or $a_n=n$. If $a_n=n$, there are  $|A_{n-1}|$ ways to finish. If $a_n=1$, then subtracting 1 from every element also gives $|A_{n-1}|$ ways to finish. Therefore, $|A_n| = 2|A_{n-1}|$. Since $|A_3| = 6$, we get $|A_n| = 3\cdot 2^{n-2}$, as desired. $\square$