¿De cuántas maneras puede la bola volver a $A$ siete pasadas?

Question

Hay 4% de los jugadores de baloncesto $A,B,C,D$. Inicialmente la pelota está con $A$. La pelota siempre se pasa de una persona a otra persona. ¿De cuántas maneras puede la bola volver a $A$ siete pasadas?

De alguna manera podría conseguir la solución como pases de $2.3^5=486$ pero no estoy seguro acerca de mi respuesta. Una respuesta con explicación completa sería útil. Gracias.

Answer 1

Para cada número de pases $n$, vamos a $u_n$ el número de pase de secuencias que terminan en $A$ $v_n$ el número de pase de secuencias que no termina en $A$. Entonces tenemos:

$$u_{n+1} = v_n$$ $$v_{n+1} = 3u_n + 2v_n$$

Sustituyendo $u_n = v_{n-1}$ en la segunda ecuación nos da

$$v_{n+1} = 3v_{n-1} + 2v_n$$

Este es un estándar de recurrencia lineal (ver por ejemplo este artículo de la Wikipedia). El polinomio $x^2-2x-3$ tiene raíces $3$$-1$, lo $v_n=A\cdot3^n+B\cdot(-1)^n$ para algunas constantes $A$$B$. Utilizando los valores iniciales $v_0=0$$v_1=3$, obtenemos $A+B=0$$3A-B=3$, lo que da $A=\frac34, B=-\frac34$.

Por lo tanto $v_n = \frac34(3^n-(-1)^n)$, e $u_n$ (que es lo que queremos aquí) es igual a $v_{n-1} = \frac34(3^{n-1}-(-1)^{n-1}) =\frac143^n + \frac34(-1)^n$.

La respuesta final es, por tanto,$u_7 = \frac14(3^7-3) = 546$.

Answer 2

Deje $A(n)$ el número de maneras de final en $A$ después $n$ pasa. Deje $B(n)$ el número de maneras de final en $B$ después $n$ pasa. Claramente $C(n)=B(n)=D(n)$.
$A(1)=0,B(1)=1$
$A(n+1)=3B(n)$
$B(n+1)=2B(n)+A(n)$
Es ahora sencillo para calcular el $A(7)$.
Al $A$ recibe el $n+1^{th}$ pase, el jugador anterior se $B,C or D$ después $n$ pasa, por lo $A(n+1)=B(n)+C(n)+D(n).$
Al $B$ recibe el $n+1^{th}$ pasar, $A,C or D$ recibió el enésimo pase, por lo $B(n+1)=A(n)+C(n)+D(n)$.
Desde $B(n)=C(n)=D(n)$, lo que significa $A(n+1)=3B(n)$.
Para calcular el $A(7)$, calcular primero $A(2)$$B(2)$,$A(3)$$B(3)$, y así sucesivamente.

Answer 3

Deje que el número de circuitos que volver a $A$ después $n$ pasa a ser $f(n)$

Tenemos dos casos. Pase la $n-2$ $A$ o no lo es.

Si $n-2$$A$, luego el pase de $n-1$ puede ser para cualquier otro jugador. Por lo tanto, el número de circuitos es $3f(n-2)$.

Si $n-2$ no $A$, y luego pasar a $n-1$ es una de las dos personas diferentes de $A$, y la persona que consiguió pasar a $n-2$. Por lo tanto, podemos sustituir el $A$ para el receptor de pase de $n-1$, y obtener un único $n-1$ circuito. Por lo tanto, el número de circuitos es $2f(n-1)$.

Por lo tanto, obtenemos la recursividad $$f(n)=2f(n-1)+3f(n-2)$$ con $f(0)=1$$f(1)=0$. Esta recurrencia lineal tiene la solución $$f(n)=\frac{3^n+3(-1)^n}4$$