Processing math: 80%

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


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

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

пред. Правка 2   1
3 года 10 месяца назад #

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

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

Теперь докажем что никакое чётное n не является ответом. От противного, пусть нашлись какие-то n пар (a1,a2),...,(a2n1,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.

  1
3 года 10 месяца назад #

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

пред. Правка 2   0
3 года 10 месяца назад #

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