Индукция в комбинаторике

Будем доказывать это утверждение индукцией по числу ступенек.

База для очевидна.

Переход: . Будем воспринимать лестницу из й ступеньки как лестницу из ступенек и ещё одной дополнительной ступеньки.

Первое решение. Если человек стоит на й ступеньке и при следующем ходе уходит с лестницы, то переход доказан. Если первым ходом он попадает на лестницу из ступенек, то будем считать, что он изначально стоял на ней.

(*) Пусть человек стоит на лестнице из ступенек. По предположению индукции он точно покинет её. Если он сойдёт с её 1-й ступеньки, то переход доказан. Если нет, то он встанет на -ю ступеньку. Здесь возможны два варианта: если на этой ступеньке стрелка показывает в сторону окончания лестницы, то переход доказан. Если нет, то стрелка развернётся в сторону выхода, и человек снова окажется на лестнице из ступенек. Рассуждения с места (*) повторятся, но теперь, в случае попадания на ю ступеньку, мы гарантируем, что он выйдет с лестницы. Переход доказан.

Второе решение. Предположим, что человек может бесконечно ходить по лестнице из й ступеньки. На ю ступеньку он может встать не более одного раза, потому что если он встал на неё и сошёл на ю ступеньку, то стрелка развернулась в сторону выхода, и в следующий раз при наступлении на неё человек точно сойдёт с лестницы. Тогда если человек не становится на ю ступеньку, то он бесконечно ходит по лестнице из ступенек, что противоречит предположению индукции. Если он всё-таки встал на ю ступеньку, то до этого он сделал конечное число шагов, а продолжить бесконечное число шагов он должен на лестнице из ступенек, что снова противоречит предположению индукции. Противоречие. Значит, он обязательно сойдёт с лестницы.