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