Математикадан 42-ші халықаралық олимпиада, 2001 жыл, Вашингтон

$n$ — тақ сан, $n > 1$ және ${{k}_{1}},{{k}_{2}},\ldots ,{{k}_{n}}$ — берілген бүтін сандар болсын. $1,2,\ldots ,n$ сандарының әрбір $a=\left( {{a}_{1}},{{a}_{2}},\ldots ,{{a}_{n}} \right)$ болатын $n!$ орын ауыстырулары үшін $S(a)=\sum\limits_{i=1}^{n}{{{k}_{i}}}{{a}_{i}}$ есептейміз. $S\left( b \right)-S\left( c \right)$ саны $n!$--ге бөлінетіндей әр түрлі $b$ және $c$ орын ауыстырулары табылатынын дәлелдеңіздер.

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

Предположим противное - тогда все $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$