Решение задачи 167

Условие:

За дядькой Черномором выстроилось чередой бесконечное число богатырей. Доказать, что он может приказать части из них выйти из строя так, чтобы в строю осталось бесконечно много богатырей и все они стояли по росту (не обязательно в порядке убывания роста).

Решение:

Примечание: самый низкий = ниже его никого нет (самых низких может быть несколько, или бесконечно, или может не быть).

Рассмотрим два случая:

1) Пусть среди богатырей нет самого низкого (такое вполне может быть, например, рост n-го богатыря равен 1/n метров). В этом случае верно следующее: для любого богатыря есть богатырь, который находится после него и который ниже него. Действительно, пусть после богатыря под номером k все богатыри имеют рост не меньше чем у него. Тогда среди первых k богатырей можно взять самого низкого (их конечное число), и этот богатырь будем самым низким среди всех, потому что он не выше всех среди первых k и он не выше всех следующих после k-го, так как все богатыри после k-го не ниже k-го, противоречие.

Возьмем самого первого богатыря. По вышесказанному утверждению найдется богатырь, который ниже первого (назовем его второй выбранный). Всем богатырям между 1-ым и вторым выбранным говорим выйти из строя. Далее находим богатыря, который ниже второго выбранного (назовем его третий выбранный). Всем богатырям между вторым выбранным и третьим выбранным говорим выйти из строя. И так далее, получится ряд из богатырей стоящих по не увеличению роста (могут быть богатыри с равного роста).

2) Пусть среди всех богатырей есть самый низкий (он может быть не один). Скажем ему выйти из строя. Если среди оставшихся нет самого низкого, то задача свелась к предыдущей. Пусть есть, скажем ему выйти из строя (заметим, что он не ниже предыдущего вышедшего из строя!). Если среди оставшихся нет самого низкого, то задача опять свелась к предыдущей. Если есть, то говорим ему выйти из строя. И так далее. Возможны два варианта: на каком-то этапе в строю можно найти самого низкого, тогда задача свелась к предыдущей или ни на каком этапе нет самого низкого из оставшихся в строю, тогда все богатыри, которым мы сказали выйти, стоят по не убыванию роста и их бесконечно. Тогда их вернем в строй, а остальным скажем выйти.

Источник: Московская математическая олимпиада, 1985-ый год.