|
|
 |
Условие
а) Леша поднимается по лестнице из 10 ступенек. За один раз он прыгает вверх либо на одну ступеньку, либо на две ступеньки. Сколькими способами Леша может подняться по лестнице?
б) При спуске с той же лестницы Леша перепрыгивает через некоторые ступеньки (может даже через все 10). Сколькими способами он может спуститься по этой лестнице?
Решение
а) Обозначим через аn число способов подняться на лестницу из n ступенек, соблюдая условия задачи. Очевидно, a1 = 1, a2 = 2.
Пусть Петя запрыгивает на лестницу из n > 2 ступенек. Если первый прыжок был на две ступеньки, то ему осталось
запрыгнуть на n – 2 ступеньки, и число способов закончить подъем равно an–2. Если же первый прыжок был на одну ступеньку, то число способов закончить подъем равно an–1. Значит,
an = an–1 + an–2.
Это равенство позволяет, зная a1 и a2, вычислять последовательно все an (при этом будут получаться известные числа Фибоначчи):
a3 = 3, a4 = 5, a5 = 8, a6 = 13, a7 = 21, a8 = 34, a9 = 55, a10 = 89.
б) Каждую из 9 ступенек (кроме последней) Петя может либо перепрыгнуть, либо не перепрыгнуть независимо от того, на каких из верхних ступенек он останавливался. Поэтому количество способов спуститься по лестнице равно 29.
