Условие
За дядькой Черномором выстроилось чередой бесконечное число богатырей. Доказать,
что он может приказать части из них выйти из строя так, чтобы в строю осталось
бесконечно много богатырей и все они стояли по росту (не обязательно в порядке
убывания роста).
Решение
Пусть в череде богатырей не существует богатыря наименьшего роста. Это
означает, что для каждого богатыря найдётся богатырь меньшего роста и тогда
искомая цепочка легко строится последовательным выбором все меньших и меньших
по росту богатырей. Если же имеется богатырь
A1 наименьшего роста, то отбрасываем его и среди оставшихся выбираем богатыря
A2 с наименьшим ростом (если же такого
A2 нет, то для оставшихся проходит описанное выше рассуждение и утверждение задачи доказано). Далее, отбрасывая
A1 и
A2,
из остальных богатырей выбираем
A3 с наименьшим ростом (если такого
A3 нет, то всё доказано), потом
A4,
A5 и т. д. В результате получаем
цепочку стоящих по росту богатырей
A1,
A2,
A3, ....
Источники и прецеденты использования
