IMO 2001 - P4

[Gianni De Rico]

Sea $n>1$ un entero positivo impar, y sean $k_1,k_2,\ldots ,k_n$ enteros dados. Para cada una de las $n!$ permutaciones $a=(a_1,a_2,\ldots ,a_n)$ de $1,2,\ldots ,n$, sea $$S(a)=\sum \limits_{i=1}^nk_ia_i$$ Demostrar que hay dos permutaciones $b$ y $c$, $b\neq c$, tales que $n!$ divide a $S(b)-S(c)$.

[Turko Arias]

Spoiler: mostrar

Sean $b_1, b_2, ..., b_{n!}$ el conjunto de todas las permutaciones posibles. Es claro que si existen índices $i, j$ con $ i\neq j$, tales que $S(b_i) \equiv S(b_j) (mod\ n!)$ ganamos. Supongamos que esto no sucede entonces, por lo que los restos de $S(b_1), ..., S(b_{n!})$ módulo $n!$ son, en algún orden, $0, 1, 2, ..., n!-1$. Tenemos entonces $\sum \limits_{i=1}^{n!}S(b_i) \equiv 0+1+2+...+(n!-1) (mod\ n!)$, de donde $\sum \limits_{i=1}^{n!}S(b_i) \equiv \frac{(n!-1)n!}{2} (mod\ n!) (1)$.
Pero por otro lado y aplicando la definición de $S(a)$ del enunciado, tenemos:
$\sum \limits_{i=1}^{n!}S(b_i)=\sum \limits_{i=1}^{n!}\left(\sum \limits_{j=1}^{n}k_jb_i^j\right)=\sum \limits_{j=1}^{n}\left(\sum \limits_{i=1}^{n!}k_jb_i^j\right)$.
Ahora bien, notemos que, fijando la posición $j$ y moviéndonos a lo largo de todas las permutaciones posibles, $b_i^j=k$ exactamente $(n-1)!$ veces, para cada $k$ entre $1$ y $n$, por lo que $\sum \limits_{i=1}^{n!}k_jb_i^j=k_j(n-1)!(1+2+...+n)=k_j(n-1)! \frac{n(n+1)}{2}=k_jn!\frac{n+1}{2}$. Como $n$ era impar, $\frac{n+1}{2}$ es entero, y viendo $mod\ n!$ nos queda $\left(k_j\frac{n+1}{2}\right) n!\equiv 0 (mod\ n!)$. Nos queda entonces $\sum \limits_{i=1}^{n!}S(b_i)=\sum \limits_{j=1}^{n}\left(\sum \limits_{i=1}^{n!}k_jb_i^j\right)=\sum \limits_{j=1}^{n}\left(k_j\frac{n+1}{2}\right) n! \equiv 0 (mod\ n!) (2)$.

Combinando $(1)$ y $(2)$ tenemos que $(n!-1)\frac{n!}{2} \equiv 0 (mod\ n!)$, pero como $n!-1$ es coprimo con $n!$ existe $a$ inverso módulo $n!$ de $n!-1$. Multiplicando por $a$ a ambos lados de la congruencia nos queda:
$a(n!-1)\frac{n!}{2} \equiv 0.a (mod\ n!)$, o equivalentemente $\frac{n!}{2} \equiv 0 (mod\ n!)$, pero $0< \frac{n!}{2}<n!$ y llegamos a un absurdo, luego existen dos permutaciones $a$ y $b$ tales que $S(a)\equiv S(b) (mod\ n!)$ como queríamos probar $\blacksquare$