Высшая проба 2020, 11 класс, задача 5
( баллов) Дано несколько вещественных чисел, по модулю не превосходящих . Сумма всех чисел равна . Докажите, что из них можно выбрать несколько чисел так, чтобы при некотором натуральном сумма выбранных чисел отличалась от не более чем на .
Ответ
Для начала мы приведем ложное решение пятой задачи, с нетривиальной дырой. Желающим развить свою математическую культуру читателям предлагается в качестве полезного и непростого упражнения самостоятельно найти дыру в решении. Те кого интересует просто как решается задача № могут сразу читать настоящее решение ниже.
Ложное решение. Обозначим данные чисел за . Без ограничения общности будем считать, что . Если это не так, то будем доказывать утверждение задачи для чисел с положительной суммой. Из него будет следовать утверждение исходной задачи.
Докажем, что среди данных чисел существует набор из подряд идущих, удовлетворяющих неравенству из условия. То есть найдутся такие натуральные и (), что подмножество - искомое.
Обозначим через первый индекс, для которого , через - первый индекс, для которого , и так далее: по всем до . Рассмотрим также разности . Заметим что и определены, поскольку по крайней мере для выполняется неравенство для любого . Формально доопределим: и . Заметим теперь, что так как выбранные нами индексы были первыми для своего условия и так как все числа по модулю не превосходят , то все лежат на отрезке . Чисел всего (для от до ). Значит найдутся два индекса и , для которых . Без ограничения общности . Тогда
или . Тем самым, числа - искомые.
Настоящее решение. Обозначим данные чисел через . Без ограничения общности будем считать, что . Если это не так, то будем доказывать утверждение задачи для чисел с положительной суммой. Из него будет следовать утверждение исходной задачи.
Докажем, что среди данных чисел существует набор из подряд идущих, удовлетворяющих неравенству из условия. То есть найдутся такие натуральные и (), что подмножество - искомое.
Обозначим через первый индекс, для которого , через - первый индекс, для которого , и так далее: по всем от до . Рассмотрим также разности . Заметим что и определены, поскольку по крайней мере для выполняется неравенство для любого . Формально доопределим: и . Заметим теперь, что так как выбранные нами индексы были первыми для своего условия и так как все числа по модулю не превосходят , то все лежат на отрезке .
Предположим, все лежат на отрезке . Тогда, так как чисел всего (для от до ), найдутся два индекса и , для которых . Без ограничения общности . Тогда по определению чисел . Получаем:
или
Заметим, что можно взять , поскольку и . Тем самым, числа - искомые.
Пусть теперь для некоторого разность попала на полуинтервал . Докажем, что в этом случае подмножество - искомое. Для этого достаточно показать, что
Второе неравенство следует из определения , ведь - это первый индекс, для которого сумма стала не меньше . Первое неравенство равносильно следующему:
Но , и это больше , так как и $x_{m_i}\le