|
|
 |
Условие
За дядькой Черномором выстроились чередой бесконечное число богатырей разного роста. Докажите, что он может приказать части из них выйти из строя так, чтобы в строю осталось бесконечное число богатырей и все они стояли по росту (в порядке возрастания или убывания).
Подсказка
Возьмите самого высокого богатыря, потом самого высокого среди стоящих за ним, потом самого высокого среди стоящих за вторым выбранным, и т. д. Если это невозможно – найдите бесконечную подпоследовательность богатырей, стоящих в порядке убывания роста.
Решение
Назовём B-хвостом всю череду богатырей, стоящих за богатырем B. Рассмотрим два случая.
1) В одном из хвостов (B-хвосте) нет самого высокого богатыря. Возьмём в этом хвосте произвольного богатыря B1. За ним найдётся более высокий богатырь B2 (иначе самый высокий из богатырей между B и B1, включая последнего, был бы самым высоким в B-хвосте. Аналогично в B2-хвосте найдётся богатырь B3, который выше B2, и т. д. В результате получится бесконечная "возрастающая" череда богатырей.
2) В каждом хвосте есть самый высокий богатырь. Возьмем произвольного богатыря B. Пусть B1 – самый высокий в B-хвосте, B2 – самый высокий в B1-хвосте (он, конечно, ниже B1), B3 – самый высокий в B2-хвосте (он ниже B2), и т. д. В результате получится бесконечная "убывающая" череда богатырей.
Замечания
1. Эта задача – переформулировка известной теоремы:
из любой бесконечной последовательности можно выделить монотонную подпоследовательность.
2. Ср. с задачей 77915.
Источники и прецеденты использования
| web-сайт | |
| задача |
