Решение. Для начала мы приведем ложное решение пятой задачи, с нетривиальной дырой. Желающим развить свою математическую культуру читателям предлагается в качестве полезного и непростого упражнения самостоятельно найти дыру в решении. Те кого интересует просто как решается задача №5 могут сразу читать настоящее решение ниже.
Ложное решение. Обозначим данные n чисел за x1, x2, . . . , xn. Без ограничения общности будем считать, что S ≥ 0. Если это не так, то будем доказывать утверждение задачи для чисел yi = −xi c положительной суммой. Из него будет следовать утверждение исходной задачи.
Докажем, что среди данных чисел существует набор из подряд идущих, удовлетворяющих неравенству из условия. То есть найдутся такие натуральные s и t (1 ≤ s ≤ t ≤ n) что подмножество xs, xs+1, . . . , xt – искомое.
Обозначим через m1 первый индекс, для которого x1 + x2 + · · · + xm1 ≥ S/100, через m2 – первый индекс, для которого x1 + x2 + · · · + xm2 ≥ 2S/100, и так далее: x1 + x2 + · · · + xmi ≥ iS/100 по всем i до 100. Рассмотрим также разности ai = x1 + x2 + · · · + xmi − iS/100. Заметим что m100 и a100 определены, поскольку по крайней мере для n выполняется неравенство x1 + x2 + · · · + xn = S ≥ iS/100 для любого i. Формально доопределим: m0 = 0 и a0 = 0. Заметим теперь, что так как выбранные нами индексы были первыми для своего условия и так как все числа xi по модулю не превосходят 1, то все ai лежат на отрезке [0; 1]. Чисел ai всего 101 (для i от 0 до 100). Значит, найдутся два индекса i и j, для которых |ai − aj| ≤ 1/100. Без ограничения общности j > i. Тогда |(x1 + x2 + · · · + xmi) − (x1 + x2 + · · · + xmj) − iS/100 + jS/100| ≤ 1/100 или |xmi + xmi + 1 + · · · + xmj − (j − i) S/100| ≤ 1/100. Тем самым, числа xmi + 1 + · · · + xmj — искомые.
Настоящее решение. Обозначим данные n чисел за x1, x2, . . . , xn. Без ограничения общности будем считать, что S ≥ 0. Если это не так, то будем доказывать утверждение задачи для чисел yi = −xi c положительной суммой. Из него будет следовать утверждение исходной задачи.
Докажем, что среди данных чисел существует набор из подряд идущих, удовлетворяющих неравенству из условия. То есть найдутся такие натуральные s и t (1 ≤ s ≤ t ≤ n) что подмножество xs, xs+1, . . . , xt – искомое.
Обозначим через m1 первый индекс, для которого x1 + x2 + · · · + xm1 ≥ S/100, через m2 – первый индекс, для которого x1 + x2 + · · · + xm2 ≥ 2S/100, и так далее: x1 + x2 + · · · + xmi ≥ iS/100 по всем i до 100. Рассмотрим также разности ai = x1 + x2 + · · · + xmi − iS/100. Заметим что m100 и a100 определены, поскольку по крайней мере для n выполняется неравенство x1 + x2 + · · · + xn = S ≥ iS/100 для любого i. Формально доопределим: m0 = 0 и a0 = 0. Заметим теперь, что так как выбранные нами индексы были первыми для своего условия и так как все числа xi по модулю не превосходят 1, то все ai лежат на отрезке [0; 1].
Предположим, все ai лежат на отрезке [0; 1 − 1/100]. Тогда, так как чисел ai всего 100 (для i от 0 до 99), найдутся два индекса i и j, для которых |ai − aj| ≤ 1/100. Без ограничения общности j > i. Тогда mj ≥ mi по определению чисел mi. Получаем: |(x1 + x2 + · · · + xmj) − (x1 + x2 + · · · + xmi) + jS/k − iS/k| ≤ 1/k или |xmi + xmi+1 + · · · + xmj − (j − i)S/k| ≤ 1/k. Заметим, что можно взять n = j − i, поскольку j − i > 0 и j − i ≤ j < 100. Тем самым, числа xmi, xmi+1 + · · · + xmj — искомые.
Пусть теперь для некоторого i разность ai попала на полуинтервал (1 − 1/100, 1]. Докажем, что в этом случае подмножество x1, . . . , xmi−1 — искомое. Для этого достаточно показать, что
iS/k − 1/k < x1 + · · · + xmi−1 ≤ iS/100.
Второе неравенство следует из определения mi, ведь mi – это первый индекс для которого сумма стала не меньше iS/100. Первое неравенство равносильно следующему: x1 + · · · + xmi−1−iS/k > −1/100. Но x1 + · · · + xmi-1 − iS/k = ai − xmi, и это больше −1/100, так как am > 1 − 1/100 и xm ≤ 1.