|
|
 |
Условие
На рисунке изображена схема трассы для картинга. Старт и финиш в точке A, причём картингист по дороге может сколько угодно раз заезжать в точку A и возвращаться на круг.
На путь от A до B или обратно юный гонщик Юра тратит минуту. На путь по кольцу Юра также тратит минуту. По кольцу можно ездить только против часовой стрелки (стрелки показывают возможные направление движения). Юра не поворачивает назад на полпути и не останавливается. Длительность заезда 10 минут. Найдите число возможных различных маршрутов (последовательностей прохождения участков).
Решение
Обозначим через 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 маршрута.
Замечания
Предполагается, что Юра может проехать из пункта A в пункт B и сразу же повернуть обратно в пункт A.Если же считать, что по прибытии из A в B Юра обязан сделать круг, прежде чем возвращаться в пункт A, то число возможных маршрутов равно 9 (1 маршрут, в котором Юра оказывается в пункте A только 2 раза – на старте и финише, 5 маршрутов, в которых Юра заезжал в пункт А между стартом и финишем 1 раз и 3 маршрута, в которых он побывал в пункте А между стартом и финишем 2 раза).
