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