Тренировочный вариант №85

Варианты публикуются еженедельно в воскресенье, ответы - в пятницу.

Таблица соответствия первичного и тестового баллов 2014 г.

                 Ответы:                                  Обсуждение задач...                            Решения от egetrener...                                      

21. а) Ясно, что после четного числа прыжков лягушка может находиться только в вершинах 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)/3     (это нетрудно доказать по индукции).

б) Сохраним обозначение 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.