Задача 78578

Темы:    [ Арифметика остатков (прочее) ] [ Принцип Дирихле (прочее) ] [ Доказательство от противного ]

Сложность: 3+ Классы: 8,9,10

Условие

Все целые числа от 1 до 2n выписаны в строчку. Затем к каждому числу прибавили номер того места, на котором оно стоит.
Доказать, что среди полученных сумм найдутся хотя бы две, дающие при делении на 2n одинаковый остаток.

Решение

Пусть в строчку выписаны числа a₁, a₂, ..., a_2n. Предположим, что все числа  a₁ + 1,  a₂ + 2,  ...,  a_2n + 2n  дают разные остатки при делении на 2n. Тогда эти остатки равны 1, 2, ..., 2n. Поэтому  (a₁ + 1) + (a₂ + 2) + ... + (a_2n + 2n) = 2(1 + 2 + ... + 2n) ≡ 1 + 2 + ... + 2n (mod 2n).  Противоречие, поскольку
1 + 2 + ... + 2n = n(2n + 1) ≡ n (mod 2n).

Замечания

Ср. с задачей 78122.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	28
Год	1965
вариант
	1
Класс	10
Тур	2
задача
Номер	4