Permutaties

Opgave - IMO 2001 dag 2 vraag 1

Zij $n$ een oneven getal groter dan 1 en zij $c_1, c_2, \ldots, c_n$ gehele getallen. Voor alle permutaties $a = (a_1, a_2, \ldots, a_n)$ van de verzameling $\{1,2,\ldots,n\}$, definiëren we $S(a) = \sum_{i=1}^n c_i a_i$. Bewijs dat er 2 permutaties $a \neq b$ bestaan van $\{1,2,\ldots,n\}$ zodat $n!\mid S(a)-S(b)$.

Oplossing

$S_{n!}$ stelt de verzameling van permutaties van $\{1,2,\dots n\}$ voor.
Veronderstel dat $S(a)\not\equiv S(b) \pmod{n!}$ voor alle $a,b\in S_{n!}$, id est, $\{S(a)\mid a\in S_{n!}\}$ vormt een compleet restklassensysteem modulo $n!$.

We zeggen dat $a\sim b$ voor $a,b\in S_{n!}$ als $a$ een cyclische permutatie is van $b$. Dit is duidelijk een equivalentierelatie, en laat dus $X_1,X_2,\dots X_{(n-1)!}$ de partionering van $S_{n!}$ zijn, geïnduceerd door de equivalentierelatie $\sim$.

Dan is $$\sum_{a\in X_i}S(a)\equiv\sum_{i=1}^n c_i(0+1+\dots+n-1)=\frac12 n(n-1)\sum_{i=1}^nc_i\pmod{n!}$$
En dus hebben we $$\sum_{j=1}^{(n-1)!}\sum_{a\in X_j}S(a)\equiv\frac12 n!(n-1)\sum_{i=1}^nc_i\equiv 0\pmod{n!}$$
(waarbij we in de laatste stap gebruik maakten dat $2\mid n-1$)

Maar, we berekenen nu anders, door gebruik te maken dat alle $S(a)$ alle resten modulo $n!$ doorlopen: $$\sum_{j=1}^{(n-1)!}\sum_{a\in X_j}S(a)\equiv 0+1+2+\dots +n!-1=\frac{1}{2}n!(n!-1) \equiv -\frac12n!\pmod{n!}$$

(bij de laatste stap gebruikten we $n>1$)
Nemen we deze twee berekeningen samen, bekomen we $n!\mid \frac{1}{2}n!$, contradictie.

Bijgevolg waren er wel $2$ verschillende permutaties $a,b$ met $S$ gelijk aan elkaar modulo $n!$.

QED