Всесиб 2025, 9 класс, задача 3

Ответ. Хорошими являются все натуральные числа от до включительно, кроме чётных
чисел от до .

Решение. Сначала докажем, что все нечётные числа , , , ...,, хороши для любых
последовательностей из условия. Рассмотрим произвольную такую последовательность.
Число ∙ ∙ является суммой всех её членов, и, очевидно, хорошее. Дальше
будем укорачивать эту последовательность следующим образом: если последовательность
начинается или заканчивается на , убираем эту двойку (или любую из них), а если она
начинается и заканчивается на , убираем из неё обе этих единицы. В результате сумма
членов полученной последовательности на каждом шагу уменьшается на , поэтому,
проделав таких шага, мы найдём в исходной последовательности
подпоследовательности со всеми суммами , , , ..., .
Теперь построим последовательность, для которой все чётные числа от до не
являются хорошими. В ней первые членов и последние членов равны , а остальные
равны . Любая её подпоследовательность с чётной суммой членов не содержит хотя бы
одну единицу, поэтому она не содержит хотя бы двоек и её сумма не превосходит
∙ , то есть меньше .
Осталось доказать, что все чётные числа , , , ...,, хороши для любых
последовательностей из условия. Снова рассмотрим произвольную такую
последовательность и единицы, встречающиеся первой и последней среди всех её членов,
если смотреть слева направо. Всего в последовательности двоек, поэтому либо до первой
единицы, либо после последней единицы идут не больше двоек. Удалим из исходной
последовательности данную единицу и соответствующие ей крайние двойки, получим
последовательность с чётной суммой членов, не меньшей, чем ∙ . Теперь
проделаем с ней процедуру укорачивания, описанную в первом абзаце, получим в ней
подпоследовательности с суммами членов , , ..., .