Maneiras de passar a bola

Question

Cinco pessoas estão passando uma bola entre si. A bola começa com Alonzo. Cada pessoa que está com a bola passa para outra pessoa. Após o oitavo passe, a bola retorna para Alonzo. Encontre o número de possíveis sequências de passes.

Eu sei que como existem 8 passes, existem $4^8$ formas de passar a bola quando não há restrições e depois $7$ passes haveria $4^6$maneiras de passar a bola de volta para Alonzo. Como faço para continuar?

Answer 1

Vamos trabalhar recursivamente, restringindo os caminhos que começam com $A$ (nós colocamos $A$ no $0^{th}$ ranhura da corda).

Deixei $a_n$ seja o número de caminhos de comprimento $n$ que termina em $A$. Para corrigir a notação, digamos que a inicial$A$não é contado no comprimento. Então nós temos$a_1=0$ por exemplo, já que não podemos colocar $A$ no slot $1$.

Deixei $b_n$ seja o número de caminhos de comprimento $n$ que não termina em $A$. Então,$b_1=4$ por exemplo.

Como você observa, nós temos $$a_n+b_n=4^n$$

Recursivamente, temos $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$

Isso já é o suficiente para resolver seu problema, e nós temos $$\boxed{a_8=13108}$$ Um pouco de trabalho extra mostra que $$a_n=\frac {4^n+4\times (-1)^n}5$$

Answer 2

Dica:

Deixei $a_n$ ser o número de possíveis sequências de $n$ passa, onde Alonzo começa com a bola, e Alonzo a recebe de volta após o $n$ª passagem. Então$a_1 = 0$ e $a_2 = 4$.

Suponha que temos sequências de $n$passa, onde Alonzo começa com a bola, e cada pessoa que está com a bola passa para outra pessoa, mas o último passe não precisa ser para Alonzo. Existem 4 opções para cada passe, então há$4^n$possíveis sequências. Dentro$a_n$ dessas sequências, Alonzo é a última pessoa a ter a bola, o que significa que há $4^n - a_n$ sequências em que Alonzo não é a última pessoa.

Agora use recursão. Observe que Alonzo não pode ter a bola no$n-1$ª passagem.