В школе математики и программирования лестница с первого этажа на второй этаж состоит из двух пролетов, состоящих из 8 и 9 ступенек. Сколькими способами десятиклассник Вася может спуститься по ней, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки?
Найдем рекуррентную формулу, которая выражает число Nk способов для десятиклассника Васи спуститься по лестнице, состоящей из k ступенек, если он может шагать на следующую ступеньку, или перешагивать через ступеньку, или прыгать через две ступеньки.
Если тогда у Васи имеется только единственный способ остаться на начальном месте — не шагать, поэтому
Если тогда у Васи имеется только один способ спуститься по лестнице, состоящей из одной ступеньки, то есть шагнуть на следующую ступеньку с начальной нулевой ступеньки, то есть
Если тогда у Васи имеется два способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через ступеньку с начальной нулевой ступеньки, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку со второй ступеньки, на которую можно попасть двумя способами, или перешагнуть через ступеньку с первой ступеньки, на которую можно попасть одним способом, или перешагнуть через две ступеньки с начальной нулевой ступеньки, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с третьей ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку со второй ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с первой ступеньки, на которую можно попасть способом; то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с четвертой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с третьей ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки со второй ступеньки, на которую можно попасть способом, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с пятой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с четвертой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с третьей ступеньки, на которую можно попасть способом, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с шестой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с пятой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с четвертой ступеньки, на которую можно попасть способом, то есть
Если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с седьмой ступеньки; на которую можно попасть способами, или перешагнуть через ступеньку с шестой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с пятой ступеньки, на которую можно попасть способом; то есть
Наконец, если тогда у Васи имеется три способа спуститься по лестнице, состоящей из двух ступенек, то есть шагнуть на следующую ступеньку с восьмой ступеньки, на которую можно попасть способами, или перешагнуть через ступеньку с седьмой ступеньки, на которую можно попасть способами, или перешагнуть через две ступеньки с шестой ступеньки, на которую можно попасть способом, то есть
Так как на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, поэтому нужно перемножить полученные два числа вариантов N8 и N9, то есть искомое число вариантов равно произведению
Заметим, что нами получена рекуррентная формула которая справедлива для любого натурального k.
Ответ:
Приведем другое решение.
Заметим, на каждом из двух пролетов лестницы десятиклассник Вася спускается отдельно от другого пролета, поэтому можно найти число способов спуститься для каждого пролета в отдельности и перемножить полученные два числа вариантов.
Решим задачу для пролета, состоящего из 8 ступенек. Будем нумеровать ступеньки цифрами от 0 до 8, где цифра 0 означает самую верхнюю ступеньку, цифра 8 самую нижнюю ступеньку, а один шаг будем обозначать в виде a – b, где a и b — номера ступенек, на которых находился Вася за время этого шага. Также будем писать число ступенек, которые преодолел Вася за время шага.
Вася может перепрыгнуть через две ступеньки на третью ступеньку не более двух раз. Он может перепрыгнуть через две ступеньки два раза несколькими способами.
Если оставшиеся две ступеньки он преодолевает одним шагом, то имеется всего три варианта:
Шаги | 0−3−6−8 | 0−3−5−8 | 0−2−5−8 |
Число ступенек | 3, 3, 2 | 3, 2, 3 | 2, 3, 3 |
Если же оставшиеся две ступеньки он преодолевает двумя шагами, то имеется всего шесть вариантов:
Шаги | 0−3−6−7−8 | 0−3−4−5−8 | 0−1−2−5−8 |
Число ступенек | 3, 3, 1, 1 | 3, 1, 1, 3 | 1, 1, 3, 3, |
Шаги | 0−3−4−7−8 | 0−1−4−5−8 | 0−1−4−7−8 |
Число ступенек | 3, 1, 3, 1 | 1, 3, 1, 3 | 1, 3, 1, 3 |
Таким образом, получаем вариантов.
Вася перепрыгнуть через две ступеньки один раз несколькими способами, для каждого варианта запишем для краткости только число ступенек.
Число | 3, 1, 1, 1, 1, 1 | 3, 1, 1, 1, 2 | 3, 1, 1, 2, 1 | 3, 1, 2, 1, 1 | 3, 2, 1, 1, 1 |
ступенек | 3, 1, 2, 2 | 3, 2, 1, 2 | 3, 2, 2, 1 | ||
1, 3, 1, 1, 1, 1 | 1, 3, 1, 1, 2 | 1, 3, 1, 2, 1 | 1, 3, 2, 1, 1 | 1, 3, 2, 2 | |
1, 1, 3, 1, 1, 1 | 1, 1, 3, 1, 2 | 1, 1, 3, 2, 1 | |||
2, 3, 1, 1, 1 | 2, 3, 1, 2 | 2, 3, 2, 1 |
Полученное число вариантов нужно умножить н 2 из-за симметрии относительно середины лестничного пролета. Таким образом, получаем вариантов. Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.
Если Вася перепрыгнул через одну ступеньку четыре раза, то такой вариант один: 0−2−4−6−8.
Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить две единицы рядом с тремя двойками. При этом есть четыре вариант а расставить единицы рядом.
Число ступенек | 2, 2, 2, 1, 1 | 2, 2, 1, 1, 2 | 2, 1, 1, 2, 2 | 1, 1, 2, 2, 2 |
A также есть
Число ступенек | 2, 2, 1, 2, 1 | 2, 1, 2, 2, 1 | 1, 2, 2, 2, 1 | 2, 1, 2, 1, 2 |
1, 2, 2, 1, 2 | 1, 2, 1, 2, 2 |
Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки рядом с четырьмя единицами.
При этом есть пять вариантов расставить двойки рядом.
Число ступенек | 2, 2, 1, 1, 1, 1 | 1, 2, 2, 1, 1, 1 | 1, 1, 2, 2, 1, 1 | 1, 1, 1, 2, 2, 1 |
1, 1, 1, 1, 2, 2 |
А также есть — десять вариантов расставить двойки не рядом.
Число ступенек | 2, 1, 2, 1, 1, 1 | 2, 1, 1, 2, 1, 1 | 2, 1, 1, 1, 2, 1 | 2, 1, 1, 1, 1, 2 |
1, 2, 1, 2, 1, 1 | 1, 2, 1, 1, 2, 1 | 1, 2, 1, 1, 1, 2 | 1, 1, 2, 1, 2, 1 | |
1, 1, 2, 1, 1, 2 | 1, 1, 1, 2, 1, 2 |
Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить одну двойку рядом с шестью единицами, то есть имеется семь вариантов.
Число ступенек | 2, 1, 1, 1, 1, 1, 1 | 1, 2, 1, 1, 1, 1, 1 | 1, 1, 2, 1, 1, 1, 1 | 1, 1, 1, 2, 1, 1, 1 |
1, 1, 1, 1, 2, 1, 1 | 1, 1, 1, 1, 1, 2, 1 | 1, 1, 1, 1, 1, 1, 2 |
Наконец, если Вася вообще не перепрыгивал через ступеньки, тогда имеется только один вариант: 0−1−2−3−4−5−6−7−8 с числом ступенек 1, 1, 1, 1, 1, 1, 1, 1.
Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно
Таким образом, искомое число вариантов для пролета из 8 ступенек равно
Теперь решим задачу для пролета, состоящего из 9 ступенек. Будем нумеровать ступеньки цифрами от 0 до 9, где цифра 0 означает самую верхнюю ступеньку, цифра 9 — самую нижнюю ступеньку.
Вася может перепрыгнуть через две ступеньки на третью ступеньку не более трех paз.
Если Вася перепрыгнул через две ступеньки на третью ступеньку три раза, то имеется только один вариант: 0−3−6−9. Поэтому получаем вариант.
Вася может перепрыгнуть через две ступеньки дв раза несколькими способами. Оставшиеся три ступеньки он может преодолеть по разному.
Если он один раз перепрыгивает через одну ступеньку, то имеется двенадцать вариантов:
Шаги | 0−3−6−8−9 | 0−3−5−8−9 | 0−2−5−8−9 |
Число ступенек | 3, 3, 2, 1 | 3, 2, 3, 1 | 2, 3, 3, 1 |
Шаги | 0−3−6−7−9 | 0−3−5−6−9 | 0−2−5−6−9 |
Число ступенек | 3, 3, 1, 2 | 3, 2, 1, 3 | 2, 3, 1, 3 |
Шаги | 0−3−4−7−9 | 0−3−4−6−9 | 0−2−3−6−9 |
Число ступенек | 3, 1, 3, 2 | 3, 1, 2, 3 | 2, 1, 3, 3 |
Шаги | 0−1−4−7−9 | 0−1−4−6−9 | 0−1−3−6−9 |
Число ступенек | 1, 3, 3, 2 | 1, 3, 2, 3 | 1, 2, 3, 3 |
Если же оставшиеся три ступеньки он преодолевает тремя шагами, то имеется всего десять вариантов:
Шаги | 0−3−6−7−8−9 | 0−3−4−5−6−9 | 0−1−2−3−6−9 |
Число ступенек | 3, 3, 1, 1, 1 | 3, 1, 1, 1, 3 | 1, 1, 1, 3, 3 |
Шаги | 0−3−4−7−8−9 | 0−1−4−7−8−9 | 0−3−4−5−8−9 |
Число ступенек | 3, 1, 3, 1, 1 | 1, 3, 3, 1, 1 | 3, 1, 1, 3, 1 |
Шаги | 0−1−4−5−6−9 | 0−1−2−5−8−9 | 0−1−2−5−6−9 |
Число ступенек | 1, 3, 1, 1, 3 | 1, 1, 3, 3, 1 | 1, 1, 3, 1, 3 |
Шаги | 0−1−4−5−8−9 | ||
Число ступенек | 1, 3, 1, 3, 1 |
Таким образом, получаем варианта.
Вася может перепрыгнуть через две ступеньки один раз несколькими способами. Оставшиеся шесть ступенек он может преодолеть по разному.
Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить три двойки рядом с одной тройкой, то есть имеется четыре варианта. Для каждого варианта запишем для краткости только число ступенек.
Число ступенек | 2, 2, 2, 3 | 2, 2, 3, 2 | 2, 3, 2, 2 | 3, 2, 2, 2 |
Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки и две единицы рядом с одной тройкой, то есть имеется тридцать таких вариантов.
Число | 2, 2, 3, 1, 1 | 2, 2, 1, 1, 3 | 2, 1, 1, 2, 3 | 1, 1, 2, 2, 3 | |
ступенек | 2, 2, 1, 3, 1 | 2, 1, 2, 3, 1 | 1, 2, 2, 3, 1 | 2, 1, 2, 1, 3 | 1, 2, 2, 1, 3 |
1, 2, 1, 2, 3 | |||||
2, 3, 2, 1, 1 | 2, 3, 1, 1, 2 | 2, 1, 1, 3, 2 | 1, 1, 2, 3, 2 | ||
2, 3, 1, 2, 1 | 2, 1, 3, 2, 1 | 1, 2, 3, 2, 1 | 2, 1, 3, 1, 2 | 1, 2, 3, 1, 2 | |
1, 2, 1, 3, 2 | |||||
3, 2, 2, 1, 1 | 3, 2, 1, 1, 2 | 3, 1, 1, 2, 2 | 1, 1, 3, 2, 2 | ||
3, 2, 1, 2, 1 | 3, 1, 2, 2, 1 | 1, 3, 2, 2, 1 | 3, 1, 2, 1, 2 | 1, 3, 2, 1, 2 | |
1, 3, 1, 2, 2 |
Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить четыре единицы рядом с одной двойкой и одной тройкой, то есть имеется тридцать таких вариантов.
Число | 2, 3, 1, 1, 1, 1 | 2, 1, 1, 1, 1, 3 | 1, 1, 1, 1, 2, 3 | ||
ступенек | 2, 1, 3, 1, 1, 1 | 1, 2, 3, 1, 1, 1 | 2, 1, 1, 1, 3, 1 | 1, 2, 1, 1, 1, 3 | 1, 1, 1, 2, 3, 1 |
1, 1, 1, 2, 1, 3 | |||||
2, 1, 1, 3, 1, 1 | 1, 1, 2, 3, 1, 1 | 1, 1, 2, 1, 1, 3 | |||
1, 2, 1, 3, 1, 1 | 1, 2, 1, 1, 3, 1 | 1, 1, 2, 1, 3, 1 | |||
3, 1, 2, 1, 1, 1 | 1, 3, 2, 1, 1, 1 | 3, 1, 1, 1, 2, 1 | 1, 3, 1, 1, 1, 2 | 1, 1, 1, 3, 2, 1 | |
1, 1, 1, 3, 1, 2 | |||||
3, 1, 1, 2, 1, 1 | 1, 1, 3, 2, 1, 1 | 1, 1, 3, 1, 1, 2 | |||
1, 3, 1, 2, 1, 1 | 1, 3, 1, 1, 2, 1 | 1, 1, 3, 1, 2, 1 |
Если же Вася ни разу не перепрыгнул через одну ступеньку, то таких вариантов несколько. Это число равно числу вариантов расставить шесть единиц рядом с одной тройкой, то есть имеется семь таких вариантов.
Число ступенек | 3, 1, 1, 1, 1, 1, 1 | 1, 3, 1, 1, 1, 1, 1 | 1, 1, 3, 1, 1, 1, 1 | 1, 1, 1, 3, 1, 1, 1 |
1, 1, 1, 1, 3, 1, 1 | 1, 1, 1, 1, 1, 3, 1 | 1, 1, 1, 1, 1, 1, 3 |
Таким образом, получаем вариант.
Наконец, Вася может ни одного раза не перепрыгнуть через две ступеньки. В этом случае он может несколько раз перепрыгнуть через одну ступеньку.
Если Вася перепрыгнул через одну ступеньку четыре раза, то таких вариантов несколько. Это число равно числу вариантов расставить одну единицу рядом с четырьмя Двойками, то есть имеется пять вариантов.
Число ступенек | 2, 2, 2, 2, 1 | 2, 2, 2, 1, 2 | 2, 2, 1, 2, 2 | 2, 1, 2, 2, 2 |
1, 2, 2, 2, 2 |
Если Вася перепрыгнул через одну ступеньку три раза, то таких вариантов несколько. Это число равно числу вариантов расставить три единицы рядом с тремя двойками.
При этом есть четыре варианта расставить единицы рядом.
Число ступенек | 2, 2, 2, 1, 1, 1 | 2, 2, 1, 1, 1, 2 | 2, 1, 1, 1, 2, 2 | 1, 1, 1, 2, 2, 2 |
И есть
Число ступенек | 2, 2, 1, 2, 1, 1 | 2, 1, 2, 2, 1, 1 | 1, 2, 2, 2, 1, 1 | |
2, 2, 1, 1, 2, 1 | 2, 1, 2, 1, 1, 2 | 1, 2, 2, 1, 1, 2 | ||
2, 1, 1, 2, 2, 1 | 2, 1, 1, 2, 1, 2 | 1, 2, 1, 1, 2, 2 | ||
1, 1, 2, 2, 2, 1 | 1, 1, 2, 2, 1, 2 | 1, 1, 2, 1, 2, 2 |
А также есть — четыре варианта расставить единички не рядом.
Число ступенек | 2, 1, 2, 1, 2, 1 | 1, 2, 2, 1, 2, 1 | 1, 2, 1, 2, 2, 1 | 1, 2, 1, 2, 1, 2 |
Если Вася перепрыгнул через одну ступеньку два раза, то таких вариантов несколько. Это число равно числу вариантов расставить две двойки рядом с пятью единицами.
При этом есть шесть вариантов расставить двойки рядом.
Число ступенек | 2, 2, 1, 1, 1, 1, 1 | 1, 2, 2, 1, 1, 1, 1 | 1, 1, 2, 2, 1, 1, 1 | 1, 1, 1, 2, 2, 1, 1 |
1, 1, 1, 1, 2, 2, 1 | 1, 1, 1, 1, 1, 2, 2 |
А также есть — пятнадцать вариантов расставить двойки не рядом.
Число ступенек | 2, 1, 2, 1, 1, 1, 1 | 2, 1, 1, 2, 1, 1, 1 | 2, 1, 1, 1, 2, 1, 1 | 2, 1, 1, 1, 1, 2, 1 |
2, 1, 1, 1, 1, 1, 2 | 1, 2, 1, 2, 1, 1, 1 | 1, 2, 1, 1, 2, 1, 1 | 1, 2, 1, 1, 1, 2, 1 | |
1, 2, 1, 1, 1, 1, 2 | 1, 1, 2, 1, 2, 1, 1 | 1, 1, 2, 1, 1, 2, 1 | 1, 1, 2, 1, 1, 1, 2 | |
1, 1, 1, 2, 1, 2, 1 | 1, 1, 1, 2, 1, 1, 2 | 1, 1, 1, 1, 2, 1, 2 |
Если Вася перепрыгнул через одну ступеньку один раз, то таких вариантов несколько. Это число равно числу вариантов расставить одну двойку рядом с семью единицами, то есть имеется восемь вариантов.
число ступенек | 2, 1, 1, 1, 1, 1, 1, 1 | 1, 2, 1, 1, 1, 1, 1, 1 | 1, 1, 2, 1, 1, 1, 1, 1 | 1, 1, 1, 2, 1, 1, 1, 1 |
1, 1, 1, 1, 2, 1, 1, 1 | 1, 1, 1, 1, 1, 2, 1, 1 | 1, 1, 1, 1, 1, 1, 2, 1 | 1, 1, 1, 1, 1, 1, 1, 2 |
Наконец, если Вася вообще не перепрыгивал через ступеньки, тогда имеется только один вариант: 0−1−2−3−4−5−6−7−8−9 с числом ступенек 1, 1, 1, 1, 1, 1, 1, 1, 1.
Поэтому если Вася не перепрыгивал через две ступеньки ни одного раза, то число вариантов равно
Таким образом, искомое число вариантов для пролета из 9 ступенек равно
Наконец, искомое число вариантов равно произведению