Permutaties

Opgave - IMOSL 2008 dag 1 vraag 9

Voor elk natuurlijk getal $n$, Bepaal het aantal permutaties $(a_1, a_2, \dots, a_n)$ van de verzameling $\{1, 2, \dots , n\}$ met de volgende eigenschap:
$2(a_1 + a_2 + · · · + a_k)$ is deelbaar door $k$ voor $k = 1, 2, \dots , n$

Oplossing

Claim: het aantal dergelijke permutaties wordt gegeven door $3\cdot 2^{n-2}$

We kunnen de deelbaarheidsvoorwaarde herschrijven naar een stelsel:
$$\begin{cases} n-1\mid n(n+1)-2a_n \\ n-2\mid n(n+1)-2a_n-2a_{n-1}\\ n-3\mid n(n+1)-2a_n-2a_{n-1}-2a_{n-2} \\ \vdots \\ 3\mid n(n+1) -2a_n-2a_{n-1}-\dots -2a_4\end{cases}$$
Dit impliceert dat we alleen hoeven te tellen hoeveel mogelijkheden er zijn voor $a_n, a_{n-1},\dots, a_4$ (de deelbaarheidsvoorwaarde is altijd waar voor $k=1,2$). Nadien vermenigvuldigen we dit aantal mogelijkheden met $3!=6$, het aantal keuzes voor $a_3, a_2, a_1$.
Voor het aantal mogelijkheden $a_n, a_{n-1},\dots, a_4$ te tellen, bewijzen we straks een lemma. Dit lemma zal impliceren dat als we een reeks van $a_n,a_{n-1},\dots,a_k$ ($4< k \leq n$) gegeven hebben die aan de eerste $n-k$ vergelijkingen voldoet van het stelsel, dan zijn er exact twee mogelijkheden voor het volgende getal $a_{k-1}$. Dit impliceert direct dat er $2^{n-3}$ mogelijkheden zijn voor deze getallen, aangezien er voor $a_n$ ook twee mogelijkheden zijn, zoals bewezen in het lemma dat dadelijk volgt.

Lemma: a) er zijn twee mogelijkheden voor $a_n$, nl. $a_n=1$ of $a_n=n$
b)Gegeven een mogelijkheid $a_n,a_{n-1},\dots,a_k$ ($ 4 < k\leq n$) die voldoet aan de eerste $n-k+1$ vergelijkingen van het stelsel hierboven, zijn er twee mogelijkheden voor $a_{k-1}$, namelijk het grootste, resp. kleinste getal dat nog niet in de eerdere lijst van getallen $a_i$ voorkwam.

inductiebasis: Voor $k=n$: $n-1\mid n(n+1)-2a_n$ en dus $2\equiv n(n+1) \equiv 2a_n \pmod{n-1}$, dit geeft als oplossingen $a_n=1,n$ of $\frac12(n+1)$ mocht dat laatste een geheel getal zijn. Veronderstel dat $n+1$ even is. Dan moet wegens de tweede vergelijking van het stelsel dat $n-2\mid n(n+1)-(n+1)-2a_{n-1}$ en dus $2a_{n-1}\equiv 3 \pmod{n-2}$. De enige gehele oplossing binnen het bereik van de $a_i$’s is $a_{n-1}=\frac12(n+1)$, maar dat mogen we niet gebruiken omdat $a_n$ al die waarde had.

inductiestap:
Wegens de inductiehypothese kunnen de getallen $a_n,a_{n-1},\dots,a_k$ verdeeld worden in de twee groepen $1,2,\dots b-1,b$ en $a,a+1\dots, n-1, n$. Hierbij is dus $b$ de grootste van de kleinste getallen en $a$ de kleinste van de grootste getallen (met de conventie dat $b=0$ wanneer $a=n-k+1$ en $a=n+1$ wanneer $b=k$). Dan is $a-b=k$ en $ n(n+1) -2a_n-2a_{n-1}-\dots -2a_k=(k-1)(a+b)$
De $(n-k+1)$-de vergelijking is dus $(k-1)(a+b)\equiv 2a_{k-1}\pmod{k-2}$, oftewel $ 2a_{k-1}\equiv a+b \pmod{k-2}$. Rekening houdende met $ b < a_{k-1} < a=b+k$, heeft deze laatste vergelijking 3 oplossingen, namelijk $a_{k-1}=b+1,a-1$ en $\frac{1}{2}(a+b)$, mocht dat laatste bestaan. We bewijzen dat $a_{k-1}=\frac{a+b}{2}$ nooit werkt, mocht $a+b$ even zijn:
In de $(n-k+2)$-de vergelijking deze oplossing invullen geeft $k-3 \mid (k-1)(a+b)-(a+b)-2a_{k-2}$ oftewel $2a_{k-2}\equiv a+b \pmod{k-3}$. Echter, rekening houdende met dat $b < a_{k-2} < a=b+k$, hebben we als enige oplossing $a_{k-2}=\frac12(a+b)$, wat niet kan omdat deze al gelijk was aan $a_{k-1}$.
QED