Математикадан облыстық олимпиада, 2003-2004 оқу жылы, 9 сынып

Бізге 1, 1, 2, 2, 3, 3, $\ldots$, $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?$

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