Рекурренты в комбинаторике и числа Фибоначчи f(n)
Ошибка.
Попробуйте повторить позже
Блоха Кузя может совершать прыжки из каждой вершины правильного тетраэдра 
в три соседние вершины, причем выбор этих
вершин случайный и равновозможный. Прыгать Кузя начала из вершины A и, совершив 2020 прыжков, опять оказалась в той же вершине.
С какой вероятностью это могло произойти?
Подсказка 1
2020 прыжков довольно много, давайте рассмотрим конкретный прыжок на каком-то k-ом шаге, с какой вероятностью она сможет попасть в A?
Подсказка 2
Верно, есть 2 случая: она в самой вершине A, тогда за 1 шаг ничего не получится или не в A, тогда вероятность равна 1/3, а можем ли мы как-то обобщить наш результат, получить такую формулу, чтобы по кол-ву шагов знать вероятность попадания в A на следующем шаге?
Подсказка 3
Давайте начнём строить нашу последовательность p_n, где p_n - вероятность попасть в A на n-ом шаге. Очевидно, что p_0 = 1 (мы стартуем из A), p_1 = 0 (мы точно ушли из A), p_2 = 1/3 (пойти в обратном направлении), p_3 = (1-p_2)*1/3 = 1/3 - 1/9 (не пойти в обратном направлении на шаге 2, но вернуться в точку A на шаге 3). Аналогично, выписывая последующие члены последовательности получите предположение об общей формуле
Подсказка 4
pₙ = 1/3 - 1/9 + 1/27 + ... + (-1)ⁿ/(3ⁿ⁻¹), давайте докажем её по индукции! (тут нужно брать n = 2 для базы)
Рассмотрим некоторый промежуточный шаг в движении Кузи. Если она на этом шаге находится в точке 
, то вероятность
попасть в 
на следующем шаге равна нулю. Если же она находится в любой из оставшихся точек 
или 
,то
вероятность попасть в 
на следующем шаге равна 
, так как из каждой такой точки есть три равновозможных пути,
только один из которых приводит в 
. Пусть 
— вероятность того, что на 
ом шаге блоха находится в точке 
.
Соответственно не в точке 
она находится с вероятностью 
. Тогда на следующем шаге она окажется в 
с
вероятностью
Таким образом, 
(так как изначально блоха в точке 
), 
Можно заметить закономерность и заключить при 
Видим, что 
представляет собой сумму членов геометрической прогрессии со знаменателем равным 
Следовательно,
Замечание. Чтобы решение было более обоснованным, формулу для 
при 
можно доказать методом математической
индукции.
База:
Шаг: пусть формула верна для 
, то есть
Тогда
то есть формула верна и для 
. А значит, верна и при любых 
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
