Задачи на логику, головоломки, загадки, ребусы - Л О Г О - Р А Й

Задачи на логику, алгоритмы, комбинаторика, принцип Дирихле, вероятности, вычисления, математика, геометрия, физика, история, анаграммы, ребусы, шарады

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

Дорога к счастью

Чтобы вы знали: путь к счастью - это вовсе не дорога, а лестница. Лестница о тридцати ступенях. Но мало по ней просто прошагать. Для счастья нужно пройти все ступени только вперёд таким сочетанием разных шагов, как этого ещё никто не делал. А шаги получаются только трёх видов:

1. Через две ступеньки;

2. Через одну ступеньку;

3. На следующую ступеньку.

Сколько людей смогут обрести счастье, пройдя по этой лестнице?

Ответ:

Обозначим через S(n) число людей, которые могут пройти по лестнице в n ступенек. Тогда S(1)=1 (один одинарный шаг), S(2)=2 (два одинарных, либо один двойной), S(3)=4 (одинарный+двойной, двойной+одинарный, три одинарных, один тройной). Дальше. Свяжем последовательность S(n) рекуррентной формулой. Все последовательности шагов заканчиваются либо одинарным, либо двойным, либо тройным шагом. Тогда число разных людей, закончивших восхождение на n-ю ступеньку одинарным шагом равно S(n-1); число разных людей, закончивших восхождение на n-ю ступеньку двойным шагом равно S(n-2); число разных людей, закончивших восхождение на n-ю ступеньку тройным шагом равно S(n-3). Значит S(n)=S(n-1)+S(n-2)+S(n-3). Что-то похожее на числа Фибоначчи, только суммируются не предыдущие 2 члена, а предыдущие 3. Итого 53 798 080 счастливцев.


 


© 2020 Загадки, шарады, ребусы, головоломки, пословицы и поговорки - Лого-Рай.

Карта сайта

rieltorspb.ru