Способы передачи мяча

Aug 19 2020

Пять человек передают между собой мяч. Мяч начинается с Алонзо. Каждый, у кого есть мяч, передает его другому. После восьмой передачи мяч возвращается Алонзо. Найдите количество возможных последовательностей проходов.

Я знаю, что, поскольку есть 8 проходов, есть $4^8$ способы передачи мяча при отсутствии ограничений и после $7$ проходит там будет $4^6$способы передать мяч обратно Алонзо. Как мне продолжить?

Ответы

3 lulu Aug 19 2020 at 17:35

Давайте работать рекурсивно, ограничиваясь теми путями, которые начинаются с $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$$

FruDe Aug 20 2020 at 20:20

Подсказка:

Позволять $a_n$ быть количеством возможных последовательностей $n$ пасы, где Алонзо начинает с мячом, а Алонзо возвращает его после $n$й перевал. потом$a_1 = 0$ и $a_2 = 4$.

Предположим, у нас есть последовательность $n$пасы, где Алонзо начинает с мячом, и каждый, кто владеет мячом, передает его кому-то другому, но последний пас не обязательно должен быть отдан Алонзо. Для каждого прохода есть 4 варианта, так что есть$4^n$возможные последовательности. В$a_n$ из этих эпизодов Алонзо - последний человек, у которого есть мяч, а это значит, что $4^n - a_n$ эпизоды, где Алонзо не последний человек.

Теперь воспользуйтесь рекурсией. Обратите внимание, что Алонзо не может держать мяч на$n-1$й перевал.