ВсОШ 2021, 10 класс, задача 4
Дано натуральное число и карточки, пронумерованные числами . На карточке с номером написано вещественное число , причем . Докажите, что можно выбрать 4 карточки так, чтобы сумма чисел на первых двух карточках отличалась от суммы чисел на двух других карточках менее чем на .
(А. Кузнецов)
Решение.
Обозначим . Назовем пару карточек неудачной, если написанные на них числа отличаются менее чем на . Карточки в такой паре имеют последовательные номера, потому что в противном случае числа на них отличаются более чем на , а при . Если карточка состоит в двух неудачных парах, то эти пары - и . В таком случае , противоречие. Следовательно, каждая карточка состоит максимум в одной неудачной паре.
Пусть нашлись две неудачные пары: и . В силу сказанного выше, все эти карточки различны. С другой стороны,
и задача решена. Здесь мы воспользовались тем, что и .
Пусть неудачных пар карточек не более одной. Если неудачная пара есть, пусть эта пара . Если таких пар нет, положим .
Обозначим через множество пар карточек с суммой номеров . Заметим, что , и при . Положим
число мы подберем позже. Тогда
Пусть в две пары вида и , здесь может быть как больше , так и меньше. Тогда и . Значит, , то есть может принимать не более значений. Для каждого из них удалим из карточку вида . В результате мы получим множество , удалив из не более пар карточек. Значит,
Заметим, что . Поскольку в каждой паре из сумма номеров карточек принимает значения от до , то сумма чисел на карточках из таких пар лежит в промежутке , длина которого равна . Тогда суммы чисел в каких-то двух парах карточек отличаются не более чем на
Остается доказать, что при некотором число
больше . Преобразуем числитель:
Значит,
Наконец, выберем число как целое число из промежутка . Тогда , поэтому
при .
Итак, мы получили, что суммы вида и для некоторых отличаются менее чем на . Остается проверить, что эти карточки разные. Предположим противное, по построению имеем и . Пусть, без ограничения общности, . Тогда , то есть карточки и образуют неудачную пару. Значит, это карточки и . Следовательно, и , противоречие.