49th International Mathematical Olympiad Spain

For each $n$ let $F_n$ be the number of permutations of $\{1,2,\dots ,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 $(a_1,a_2,\dots ,a_n)$ of $\{1,2,\dots ,n\}$. Then $n-1$ must be a divisor of the number $$\begin{array}{rl}& 2(a_1+a_2+\cdots +a_{n-1})=2((1+2+\cdots +n)-a_n)\\ & =n(n+1)-2a_n=(n+2)(n-1)+(2-2a_n).\end{array}$$ So $2a_n-2$ must be divisible by $n-1$, hence equal to $0$ or $n-1$ or $2n-2$. This means that $$a_n=1\text{or}{a}_n=\frac{n+1}{2}\text{or}{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{array}{rl}2(a_1+a_2+\cdots +a_{n-2})& =2((1+2+\cdots +n)-a_n-a_{n-1})\\ & =n(n+1)-(n+1)-2a_{n-1}=(n+2)(n-2)+(3-2a_{n-1})\end{array}$$ So $2a_{n-1}-3$ should be divisible by $n-2$, hence equal to $0$ or $n-2$ or $2n-4$. Obviously $0$ and $2n-4$ are excluded because $2a_{n-1}-3$ is odd. The remaining possibility ($2a_{n-1}-3=n-2$) 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 $(a_1,a_2,\dots ,a_{n-1})$ is a nice permutation of $\{1,2,\dots ,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,\dots ,n\}$.

If $a_n=1$ then $(a_1-1,a_2-1,\dots ,a_{n-1}-1)$ is a permutation of $\{1,2,\dots ,n-1\}$. It is also nice because the number $$2((a_1-1)+\cdots +(a_k-1))=2(a_1+\cdots +a_k)-2k$$ is divisible by $k$, for any $k\le n-1$. And again, any one of the $F_{n-1}$ nice permutations $(b_1,b_2,\dots ,b_{n-1})$ of $\{1,2,\dots ,n-1\}$ gives rise to a nice permutation of $\{1,2,\dots ,n\}$ whose last term is $1$, namely $(b_1+1,b_2+1,\dots ,b_{n-1}+1,1)$.

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