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