Областная олимпиада по математике, 2004 год, 9 класс

Даны числа 1, 1, 2, 2, 3, 3, $\dots$, $n$, $n$. При каких значениях $n$ эти числа можно так объединить в $n$ пар, чтобы сумма чисел, стоящих в каждой паре, давали при делении на $n$ различные остатки?

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

$Ответ:n-нечётное$

Пример для $n$ нечётное: пары $(1;1),(2;2),...,(n,n)$. Докажем что эти пары удовлетворяют от противного. Пусть найдутся $2$ суммы пар $(2i,2j)$ дающие одинаковый остаток при делении на $n$. Тогда $2(i-j)$ делится на $n$,тогда и $|i-j|$ делится $n$, но это невозможно так как $0<|i-j|<n$. Значит все суммы пар дают различные остатки при делении на $n$.

Теперь докажем что никакое чётное $n$ не является ответом. От противного, пусть нашлись какие-то $n$ пар ($a_{1},a_{2}),...,(a_{2n-1},a_{2n})$удовлетворяющие условие. Обозначим через $b_{1},...,b_{n}$ остатки $n$ пар при делении на $n$. Тогда рассмотрим сумму всех чисел и сумму остатков:

$a_{1}+...+a_{2n} \equiv b_{1}+...+b_{n} \pmod n$

$2•(1+2+...+n) \equiv 1+2+...+n$

Значит $n(n+1)/2$ делится на $n$. Но это невозможно при чётном $n$.

а разве не $n(n+1)/2?$

Ой, ну, да. Но это ни как не влияет на правильность решение. Исправил