## Problem 5.

Among all permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$, ($n \geq 1$ integer), consider those that satisfy $2\left(a_{1}+a_{2}+\cdots+a_{m}\right)$ is divisible by $m$, for each $m=1,2, \ldots, n$. Calculate the total number of such permutations.
Solution.

Let $\mathcal{P}_{n}$ be the set of permutations of $\{1,2, \ldots, n\}$ that satisfy the conditions of the problem. The problem is to calculate $\left|\mathcal{P}_{n}\right|$. Observe that, for any $n$, the conditions are always satisfied for $m=1$, for $m=2$ and for $m=n$, so $\mathcal{P}_{1}, \mathcal{P}_{2}$ and $\mathcal{P}_{3}$ are, in each case, the set of all permutations and $\left|\mathcal{P}_{1}\right|=1,\left|\mathcal{P}_{2}\right|=2$ and $\left|\mathcal{P}_{3}\right|=6$.

Suppose that $\left(a_{1}, \ldots, a_{n}\right) \in \mathcal{P}_{n}$. Taking $m=n-1$, it must be that $(n-1) \mid 2\left(a_{1}+\cdots+a_{n-1}\right)=2\left(a_{1}+\cdots+a_{n}\right)-2 a_{n}=n(n+1)-2 a_{n}$. Looking at this relation in terms of congruences, we have $2-2 a_{n} \equiv 0 \bmod (n-1)$, or that $2\left(a_{n}-1\right)$ is a multiple of $n-1$, which is equivalent to $a_{n}-1$ being a multiple of $\frac{n-1}{2}$. Given the obvious bound $a_{n}-1 \leq n-1$, the only values that $a_{n}-1$ can take are $0, \frac{n-1}{2}$ or $n-1$. Therefore, $a_{n}$ can only be $1, \frac{n+1}{2}$ or $n$.

If $a_{n}=\frac{n+1}{2}$, then $n$ must be odd. The property of $\mathcal{P}_{n}$ for $m=n-2$ tells us, with a similar calculation as before, that $(n-2) \mid 2\left(a_{1}+\cdots+a_{n-2}\right)=n(n+1)-2 a_{n-1}-2 a_{n}=$ $(n-1)(n+1)-2 a_{n-1}$. Looking at this relation in terms of congruences modulo $(n-2)$, we get $3-2 a_{n-1} \equiv 0$ mod $(n-2)$, so $2 a_{n-1}-3$ must be a multiple of $n-2$ and this only happens if it is $n-1$. But this leads to $a_{n-1}=\frac{n+1}{2}=a_{n}$, which is absurd.

In conclusion, $a_{n}$ can only take the values 1 and $n$.

Let's study these two cases.

Case $a_{n}=n$. Then $\left(a_{1}, \ldots, a_{n-1}\right)$ is a permutation of $\{1,2, \ldots, n-1\}$. It is easily verified that it is from $\mathcal{P}_{n-1}$. Therefore, there will be as many permutations of $\mathcal{P}_{n}$ with $a_{n}=n$ as there are permutations in $\mathcal{P}_{n-1}$.

Case $a_{n}=1$. Now $a_{1}, a_{2}, \ldots, a_{n-1}>1$ and $\left(a_{1}-1, a_{2}-1, \ldots, a_{n-1}-1\right)$ is a permutation of $\mathcal{P}_{n-1}$. The correspondence $\left(a_{1}, a_{2}, \ldots, a_{n-1}, 1\right) \rightleftarrows\left(a_{1}-1, a_{2}-1, \ldots, a_{n-1}-1\right)$ is bijective. There will be as many permutations of $\mathcal{P}_{n}$ with $a_{n}=1$ as there are permutations in $\mathcal{P}_{n-1}$.

In short, $\left|\mathcal{P}_{n}\right|=2\left|\mathcal{P}_{n-1}\right|$ if $n>3$, from which, $\left|\mathcal{P}_{n}\right|=3 \cdot 2^{n-2}$.

Observation: The proof above gives us the recursive algorithm to obtain all permutations that satisfy the condition. For example, we know that the permutations of $\mathcal{P}_{3}$ are all. By adding a 4 to the end of each one, we get half of those of $\mathcal{P}_{4}$. The other half comes from adding 1 to each element of each permutation and adding a 1 at the end.