ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65275
Темы:    [ Дискретное распределение ]
[ Числа Фибоначчи ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

На рисунке изображена схема трассы для картинга. Старт и финиш в точке 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 маршрута.

Источники и прецеденты использования

олимпиада
Название Заочная олимпиада по теории вероятностей и статистике
год
Дата 2008
задача
Номер 18

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .