а) Ясно, что после чётного числа прыжков лягушка может находиться только в вершинах A, C или E. Обозначим через a_k, c_k, e_k число путей длины 2k, ведущих из A в A, C и E соответственно. В силу симметрии  c_k = e_k.  Легко видеть, что выполняются равенства   c_k+1 = a_k + 3c_k,   a_k+1 = 2a_k + 2c_k.

  Отсюда   c_k+2 = a_k+1 + 3c_k+1 = 2a_k + 2c_k + 3c_k+1 = 2(c_k+1 – 3c_k) + 2c_k + 3c_k+1 = 5c_k+1 – 4c_k.

  Из начальных условий   c₀ = 0,  c₁ = 1,  находим   c_k = ¹/₃ (4^k – 1)   (это нетрудно доказать по индукции).   б) Сохраним обозначение c_k из п. а) (теперь это число будет другим). Обозначим через b_k число путей длины  2k – 1,  ведущих из A в B. Тогда   b_k+1 = 3b_k  (за два прыжка можно двумя способами вернуться из B в B и одним способом попасть из B в F). Но   c_k = b_k,   значит,  c_k+1 = 3c_k  при  k > 0.  По-прежнему,

c₁ = 1,  следовательно,   c_k = 3^k–1.   в) Поскольку в D можно попасть только на нечётном прыжке, то вероятность того, что лягушка будет жива через 2k секунд, равна вероятности того, что она жива через  2k – 1  секунду. Обозначим последнюю вероятность через P_k. В этот момент она находится в B или F. Через два прыжка она с вероятностью ¼ попадёт в D, а с вероятностью ¾ останется жива. Следовательно,  P_k+1 = ¾ P_k. 

  Поскольку  P₁ = 1,  отсюда следует, что  P_k = (¾)^k–1  (k ≥ 1).   г) Как видно из п. в), вероятность попасть в ровно через  2k + 1  секунду равна   ¼·(¾)^k–1.

Поэтому средняя продолжительность жизни лягушки равна сумме ряда  

  Указанная сумма может быть вычислена при помощи производящей функции  

  Действительно,   N = f ′(1) = 9.

а)  ¹/₃ (2ⁿ – 1)  способами при чётном n; нельзя попасть при нечётном n.   б)  3^n/2–1  способами при чётном n; нельзя попасть при нечётном n.

в)  (¾)^k–1  при  n = 2k – 1  и при  n = 2k  (k ≥ 1).   г) 9 секунд.