42-я Международная Математическая OлимпиадаСоединённые Штаты Америки, Вашингтон, 2001 год

Пусть $n$ — нечетное число, $n > 1$, и ${{k}_{1}},{{k}_{2}},\ldots ,{{k}_{n}}$ — данные целые числа. Для каждой из $n!$ перестановок $a=\left( {{a}_{1}},{{a}_{2}},\ldots ,{{a}_{n}} \right)$ чисел $1,2,\ldots ,n$ положим $S(a)=\sum\limits_{i=1}^{n}{{{k}_{i}}}{{a}_{i}}$. Докажите, что найдутся такие различные перестановки $b$ и $c$, что $S\left( b \right)-S\left( c \right)$ делится на $n!$.

Комментарий/решение

Предположим противное - тогда все $n!$ различных перестановок имеют разные остатки при делении на $n!$.

Сумма всех остатков $S(a)$ будет равна $\dfrac{n!(n!+1)}{2}$. С другой стороны, в такой сумме при каждом коэффициенте $k_{i}$ каждое число от 1 до $n$ побывает $(n-1)!$ раз. Поэтому сумма, подсчитанная другим способом, будет равняться: $\sum\limits_{i=1}^{n}{{{k}_{i}}}(n-1)!\dfrac{n(n+1)}{2}$. Теперь заметим, что последняя сумма делится на $n!$(ведь $n$ нечетное), а потому и первая сумма должна делится на $n!$, но: $\nu_2(n!) \le \nu_2(\dfrac{n!(n!+1)}{2}) = \nu_2(n!) +\nu_2(n!+1) - \nu_2(2) = \nu_2(n!) - 1 < \nu_2(n!)$, чего быть не может.

Значит у каких-то двух различных перестановок $S(b)$ и $S(c)$ одинаковый остаток при делении на $n!$.$\square$