Problem 1836

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 $(a_{1}, a_{2}, \ldots, a_{n})$ of $\{1,2, \ldots, n\}$. Then $n-1$ must be a divisor of the number
$$\begin{aligned} & 2(a_{1}+a_{2}+\cdots+a_{n-1})=2((1+2+\cdots+n)-a_{n}) \\ & \quad=n(n+1)-2 a_{n}=(n+2)(n-1)+(2-2 a_{n}) . \end{aligned}$$
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(a_{1}+a_{2}+\cdots+a_{n-2}) & =2((1+2+\cdots+n)-a_{n}-a_{n-1}) \\ & =n(n+1)-(n+1)-2 a_{n-1}=(n+2)(n-2)+(3-2 a_{n-1}) \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 ($2 a_{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}, \ldots, a_{n-1})$ 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 $(a_{1}-1, a_{2}-1, \ldots, a_{n-1}-1)$ is a permutation of $\{1,2, \ldots, 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 \leq n-1$. And again, any one of the $F_{n-1}$ nice permutations $(b_{1}, b_{2}, \ldots, b_{n-1})$ of $\{1,2, \ldots, n-1\}$ gives rise to a nice permutation of $\{1,2, \ldots, n\}$ whose last term is $1$, namely $(b_{1}+1, b_{2}+1, \ldots, b_{n-1}+1, 1)$.

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$.