|
|
 |
Условие
Лягушка прыгает по вершинам шестиугольника ABCDEF, каждый раз перемещаясь в одну из соседних вершин.
а) Сколькими способами она может попасть из A в C за n прыжков?
б) Тот же вопрос, но при условии, что ей нельзя прыгать в D?
Лягушка-сапер.
в) Пусть путь лягушки начинается в вершине A, а в вершине D находится мина. Каждую секунду она делает очередной прыжок. Какова вероятность того, что она еще будет жива через n секунд?
г)* Какова средняя продолжительность жизни таких лягушек?
Решение
а) Ясно, что после чётного числа прыжков лягушка может находиться только в вершинах A, C или E. Обозначим через ak, ck, ek число путей длины 2k, ведущих из A в A, C и E соответственно. В силу симметрии ck = ek. Легко видеть, что выполняются равенства ck+1 = ak + 3ck, ak+1 = 2ak + 2ck.
Отсюда ck+2 = ak+1 + 3ck+1 = 2ak + 2ck + 3ck+1 = 2(ck+1 – 3ck) + 2ck + 3ck+1 = 5ck+1 – 4ck.
Из начальных условий c0 = 0, c1 = 1, находим ck = 1/3 (4k – 1) (это нетрудно доказать по индукции).
б) Сохраним обозначение ck из п. а) (теперь это число будет другим). Обозначим через bk число путей длины 2k – 1, ведущих из A в B. Тогда bk+1 = 3bk (за два прыжка можно двумя способами вернуться из B в B и одним способом попасть из B в F). Но ck = bk, значит, ck+1 = 3ck при k > 0. По-прежнему,
c1 = 1, следовательно, ck = 3k–1.
в) Поскольку в D можно попасть только на нечётном прыжке, то вероятность того, что лягушка будет жива через 2k секунд, равна вероятности того, что она жива через 2k – 1 секунду. Обозначим последнюю вероятность через Pk. В этот момент она находится в B или F. Через два прыжка она с вероятностью ¼ попадёт в D, а с вероятностью ¾ останется жива. Следовательно, Pk+1 = ¾ Pk.
Поскольку P1 = 1, отсюда следует, что Pk = (¾)k–1 (k ≥ 1).
г) Как видно из п. в), вероятность попасть в ровно через 2k + 1 секунду равна ¼·(¾)k–1.
Поэтому средняя продолжительность жизни лягушки равна сумме ряда
Указанная сумма может быть вычислена при помощи производящей функции
Действительно, N = f ′(1) = 9.
Ответ
а) 1/3 (2n – 1) способами при чётном n; нельзя попасть при нечётном n.
б) 3n/2–1 способами при чётном n; нельзя попасть при нечётном n.
в) (¾)k–1 при n = 2k – 1 и при n = 2k (k ≥ 1).
г) 9 секунд.
Замечания
1. См. также задачу 61473.
2. Общий подход к решению рекуррентных уравнений см. в задаче 61458.
Источники и прецеденты использования
| книга | |
| Автор | Алфутова Н.Б., Устинов А.В. |
| Год издания | 2002 |
| Название | Алгебра и теория чисел |
| Издательство | МЦНМО |
| Издание | 1 |
| глава | |
| Номер | 11 |
| Название | Последовательности и ряды |
| Тема | Последовательности |
| параграф | |
| Номер | 2 |
| Название | Рекуррентные последовательности |
| Тема | Рекуррентные соотношения |
| задача | |
| Номер | 11.047 |
