Permutiamo troppe volte

[scambret]

Viene da qualche shortlist di qualche anno passato (2008?)

Trovare il numero di permutazioni $(a_1, ..., a_n)$ di $\{1,2,...,n\}$ t.c. risulta $2(a_1+...+a_k)$ multiplo di $k$ per ogni $k=1, 2, ..., n$

[karlosson_sul_tetto]

Sia $ P_n $ il numero di permutazioni che soddisfano le condizioni richieste per un insieme di $n$ elementi.
È facile vedere (a mano), che i primi $7$ valori dei $P_i$ sono: $1,2,6,12,24,48,96$. Si sono una pessima persona

Che numero deve stare all'$n$-simo posto? La condizione da verificare è che $2\cdot (a_1+...+a_{n-1})=\frac{2\cdot(n+1)\cdot n}{2}-2a_n=n(n+1)-2a_n$ sia divisibile per $n-1$. Dunque:
$(n-1)(n+1)+(n+1)\equiv 2a_n \pmod{n-1}$
$n-1+2\equiv 2a_n \pmod{n-1}$
$2\equiv 2a_n \pmod{n-1}$
Ci sono ora due casi: $n-1$ è pari o dispari. Se è dispari, allora nella relazione si può semplificare il $2$ ottenendo $a_n\equiv 1 \pmod {n-1}$ da cui $a_n$ o è $1$ o è $n$. Se è pari, allora oltre a $1,n$ ce un'altra soluzione: $\frac{n+1}{2}$ (si deve dimostrare o è ovvio...?). Tuttavia, $a_n=\frac{n+1}{2}$ non porta da nessuna parte: bisognerebbe trovare un $a_{n-1}$ tale che $2(a_1+...+a_{n-2})=n(n+1)-(n+1)-2a_{n-1}=(n-1)(n+1)-2a_{n-1}\equiv 0 \pmod {n-2}$
$(n-2)(n+1)+n-2+3-2a_{n-1}\equiv 0 \pmod {n-2}$
$3\equiv 2a_{n-1} \pmod {n-2}$. Tuttavia l'unico numero che risolve l'equazione è proprio $\frac{n+1}{2}$, che però è stato già usato (anche qua si può dare per scontato la sua unicità...?).

Ordunque, $a_n$ può essere solo $1$ o $n$. Nel caso $a_n=n$, allora il numero di permutazioni è $P_{n-1}$: a tutte le possibili permutazioni di un insieme di $n-1$ elementi basta aggiungere l'$n$-simo elemento che le completa.
Ora, il caso $a_n=1$. Gli altri $a_i$ appartengono all'insieme $(2,3,4,\ldots,n)$. Noto che se c'è una permutazione valida per questo insieme, ce n'è una appartenente all'insieme $(1,2,3,\ldots,n-1)$ e viceversa: metto in corrispondenza biunivoca $2$ con $1$, $3$ con $2$ e in generale $k$ con $k-1$. Se c'è una permutazione $(a_1 \ldots a_{n-1})$ che va bene, allora la corrispondente per l'insieme $(2,3,4,\ldots,n)$ sarà $(a_1+1, a_2+1, a_3+1, \ldots, a_{n-1}+1)$. Dunque anche in questo caso il numero di permutazioni è $P_{n-1}$. Abbiamo ottenuto che $P_n=2P_{n-1}$, quindi la formula chiusa per $n>3$ è $P_n=3\cdot 2^{n-2}$