Способы передачи мяча
Пять человек передают между собой мяч. Мяч начинается с Алонзо. Каждый, у кого есть мяч, передает его другому. После восьмой передачи мяч возвращается Алонзо. Найдите количество возможных последовательностей проходов.
Я знаю, что, поскольку есть 8 проходов, есть $4^8$ способы передачи мяча при отсутствии ограничений и после $7$ проходит там будет $4^6$способы передать мяч обратно Алонзо. Как мне продолжить?
Ответы
Давайте работать рекурсивно, ограничиваясь теми путями, которые начинаются с $A$ (ставим $A$ в $0^{th}$ прорезь струны).
Позволять $a_n$ быть количеством путей длины $n$ это конец в $A$. Чтобы исправить обозначения, скажем, что начальная$A$не учитывается в длине. Итак, у нас есть$a_1=0$ например, поскольку мы не можем поставить $A$ в слоте $1$.
Позволять $b_n$ быть количеством путей длины $n$ это не заканчивается $A$. Потом,$b_1=4$ например.
Как вы заметили, у нас есть $$a_n+b_n=4^n$$
Рекурсивно мы имеем $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$
Этого уже достаточно, чтобы решить вашу проблему, и мы получаем $$\boxed{a_8=13108}$$ Небольшая дополнительная работа показывает, что $$a_n=\frac {4^n+4\times (-1)^n}5$$
Подсказка:
Позволять $a_n$ быть количеством возможных последовательностей $n$ пасы, где Алонзо начинает с мячом, а Алонзо возвращает его после $n$й перевал. потом$a_1 = 0$ и $a_2 = 4$.
Предположим, у нас есть последовательность $n$пасы, где Алонзо начинает с мячом, и каждый, кто владеет мячом, передает его кому-то другому, но последний пас не обязательно должен быть отдан Алонзо. Для каждого прохода есть 4 варианта, так что есть$4^n$возможные последовательности. В$a_n$ из этих эпизодов Алонзо - последний человек, у которого есть мяч, а это значит, что $4^n - a_n$ эпизоды, где Алонзо не последний человек.
Теперь воспользуйтесь рекурсией. Обратите внимание, что Алонзо не может держать мяч на$n-1$й перевал.