Задача
На рисунке изображена схема трассы для картинга. Старт и финиш в точке A, причём картингист по дороге может сколько угодно раз заезжать в точку A и возвращаться на круг.
Решение
Обозначим через Mn число всевозможных маршрутов длительностью n минут. Каждый такой маршрут состоит ровно из n участков (участок – это отрезок AB, BA или кольцо BB). Пусть Mn,A – число таких маршрутов, оканчивающихся в A, а Mn,B – число маршрутов с конечной точкой B.
В точку B за минуту можно попасть как из точки A, так и из точки B, поэтому Mn,B = Mn–1.
В точку A за минуту можно попасть только из точки B, поэтому Mn,A = Mn–1,B = Mn–2 = Mn–2, A + Mn–2,B = Mn–2,A + Mn–3 = Mn–2,A + Mn–1,A.
Дополнительно заметим, что M1,A = 0, M2,A = 1. Таким образом, числа Mn,A образуют последовательность 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Число M10,A равно 34 – девятому числу Фибоначчи.
Ответ
34 маршрута.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь