«Квант» — научно-популярный физико-математический журнал (издаётся с 1970 года)
Старый сайт журнала: kvant.ras.ru

Задача М829

Условие задачи (1983, № 10) Задача М829 // Квант. — 1983. — № 10. — Стр. 43; 1984. — № 1. — Стр. 47.

Докажите, что среди любых $2m+1$‍‍ различных целых чисел, по модулю не превосходящих $2m-1$‍,‍ найдутся три числа, сумма которых равна 0.

Н. В. Карташов

Всесоюзная математическая олимпиада школьников (1983 год, 9 класс)


Изображения страниц

Решение задачи (1984, № 1) Задача М829 // Квант. — 1983. — № 10. — Стр. 43; 1984. — № 1. — Стр. 47.

Докажем утверждение задачи индукцией по $m$‍.

При $m=1$‍‍ оно очевидно (единственная тройка чисел, удовлетворяющая условию, — это 0, 1 и $-1$‍).

Предположим, что оно доказано для $2m-1$‍‍ чисел, и рассмотрим любое множество $A$‍‍ из $2m+1$‍‍ чисел, по модулю не превосходящих $2m-1$‍.‍ Если в нём найдётся $2m-1$‍‍ чисел, по модулю не превосходящих $2m-3$‍,‍ то утверждение следует из предположения индукции. В противном случае в множестве $A$‍‍ есть хотя бы три из чисел $\pm(2m-2)$‍‍ и $\pm(2m-1)$‍.‍ Сменив при необходимости знаки у всех чисел из $A$‍,‍ можно добиться, чтобы это были числа $2m-1$‍,$2m-2$‍,‍ а также $-2m+1$‍(1-й случай) или $-2m+2$‍(2-й случай).

1-й случай. Разобьём все числа от $1$‍‍ до $2m-2$‍‍ на пары, дающие в сумме $2m-1$‍:$(1,2m-2)$‍,$(2,2m-4)$‍,$\ldots$‍,$(m-1,m)$‍,‍ а числа от $0$‍‍ до $-2m+1$‍‍ — на пары, дающие в сумме $-2m+1$‍:$(0,-2m+1)$‍,$\ldots$‍,$(-m+1,-m)$‍.‍ Получится $2m-1$‍‍ пар, содержащих все $2m$‍‍ чисел множества $A$‍,‍ кроме $2m-1$‍.‍ Поэтому хотя бы одна пара входит в множество $A$‍,‍ и составляющие её числа в сумме с $-2m+1$‍‍ или с $2m-1$‍‍ дадут 0.

2-й случай. Рассмотрим теперь $m-2$‍‍ пар $(1,2m-3)$‍,$(2,2m-4)$‍,$\ldots$‍,$(m-2,m)$‍‍ с суммой чисел $2m-2$‍‍ и $m$‍‍ пар $(0,-2m+1)$‍,$\ldots$‍,$(-m+1,-m)$‍‍ с суммой чисел $-2m+1$‍.‍ Эти $2m-2$‍‍ пар содержат все числа множества $A$‍,‍ кроме $2m-1$‍,$2m-2$‍‍ и $m-1$‍,‍ т. е. $2m-1$‍‍ чисел из $A$‍.‍ Следовательно, одна из них опять входит в множество $A$‍‍ и даёт нулевую сумму с $-2m+2$‍‍ или $2m-1$‍.

Н. Карташов


Метаданные Задача М829 // Квант. — 1983. — № 10. — Стр. 43; 1984. — № 1. — Стр. 47.

Предмет
Математика
Условие
Решение
Номера

1983. — № 10. — Стр.  [условие]

1984. — № 1. — Стр.  [решение]

Описание
Задача М829 // Квант. — 1983. — № 10. — Стр. 43; 1984. — № 1. — Стр. 47.
Ссылка
https://www.kvant.digital/problems/m829/