Областная олимпиада по математике, 2004 год, 9 класс
Даны числа 1, 1, 2, 2, 3, 3, …, 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 пар (a1,a2),...,(a2n−1,a2n)удовлетворяющие условие. Обозначим через b1,...,bn остатки 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.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.