Formas de pasar una pelota

Question

Cinco personas pasan una pelota entre ellos. El balón empieza con Alonzo. Cada persona que tiene la pelota se la pasa a otra persona. Tras el octavo pase, el balón vuelve a Alonzo. Encuentra el número de posibles secuencias de pases.

Sé que como hay 8 pases, hay $4^8$ formas de pasar el balón cuando no hay restricciones y después $7$ pasa habría $4^6$formas de pasar el balón a Alonzo. ¿Cómo continúo?

Answer 1

Trabajemos de forma recursiva, restringiéndonos a aquellos caminos que comienzan con $A$ (nosotros ponemos $A$ en el $0^{th}$ ranura de la cuerda).

Dejar $a_n$ ser el número de caminos de longitud $n$ que terminan en $A$. Para corregir la notación, digamos que la inicial$A$no se cuenta en la longitud. Entonces tenemos$a_1=0$ por ejemplo, ya que no podemos poner $A$ en la ranura $1$.

Dejar $b_n$ ser el número de caminos de longitud $n$ que no terminan en $A$. Luego,$b_1=4$ por ejemplo.

Como comenta, tenemos $$a_n+b_n=4^n$$

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

Eso ya es suficiente para resolver su problema, y ​​obtenemos $$\boxed{a_8=13108}$$ Un poco de trabajo extra demuestra que $$a_n=\frac {4^n+4\times (-1)^n}5$$

Answer 2

Insinuación:

Dejar $a_n$ ser el número de posibles secuencias de $n$ pasa, donde Alonzo comienza con el balón, y Alonzo lo recupera después de la $n$th pase. Luego$a_1 = 0$ y $a_2 = 4$.

Supongamos que tenemos una secuencia de $n$pases, donde Alonzo comienza con el balón, y cada persona que tiene el balón se lo pasa a otro, pero el último pase no tiene por qué ser para Alonzo. Hay 4 opciones para cada pase, por lo que hay$4^n$posibles secuencias. En$a_n$ De estas secuencias, Alonzo es la última persona en tener el balón, lo que significa que hay $4^n - a_n$ secuencias donde Alonzo no es la última persona.

Ahora usa la recursividad. Tenga en cuenta que Alonzo no puede tener la pelota en el$n-1$th pase.