Façons de passer autour d'une balle

Aug 19 2020

Cinq personnes se passent une balle entre elles. Le bal commence avec Alonzo. Chaque personne qui a le ballon le passe à quelqu'un d'autre. Après la huitième passe, le ballon revient à Alonzo. Trouvez le nombre de séquences de passes possibles.

Je sais que puisqu'il y a 8 passes, il y a $4^8$ moyens de passer le ballon lorsqu'il n'y a pas de restrictions et après $7$ il y aurait des passes $4^6$moyens de renvoyer le ballon à Alonzo. Comment continuer?

Réponses

3 lulu Aug 19 2020 at 17:35

Travaillons récursivement, en nous limitant aux chemins commençant par $A$ (nous mettons $A$ dans le $0^{th}$ slot de la chaîne).

Laisser $a_n$ être le nombre de chemins de longueur $n$ qui se terminent par $A$. Pour corriger la notation, disons que l'initiale$A$n'est pas compté dans la longueur. Nous avons donc$a_1=0$ par exemple, puisque nous ne pouvons pas mettre $A$ dans la fente $1$.

Laisser $b_n$ être le nombre de chemins de longueur $n$ qui ne finissent pas par $A$. Ensuite,$b_1=4$ par exemple.

Comme vous le remarquez, nous avons $$a_n+b_n=4^n$$

Récursivement, nous avons $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$

C'est déjà suffisant pour résoudre votre problème, et nous obtenons $$\boxed{a_8=13108}$$ Un petit travail supplémentaire montre que $$a_n=\frac {4^n+4\times (-1)^n}5$$

FruDe Aug 20 2020 at 20:20

Allusion:

Laisser $a_n$ être le nombre de séquences possibles de $n$ passe, où Alonzo commence avec le ballon, et Alonzo le récupère après le $n$e passe. ensuite$a_1 = 0$ et $a_2 = 4$.

Supposons que nous ayons une séquence de $n$passe, où Alonzo commence avec le ballon, et chaque personne qui a le ballon le passe à quelqu'un d'autre, mais la dernière passe ne doit pas nécessairement être à Alonzo. Il y a 4 choix pour chaque pass, donc il y a$4^n$séquences possibles. Dans$a_n$ de ces séquences, Alonzo est la dernière personne à avoir le ballon, ce qui signifie qu'il y a $4^n - a_n$ séquences où Alonzo n'est pas la dernière personne.

Maintenant, utilisez la récursivité. Notez qu'Alonzo ne peut pas avoir le ballon sur le$n-1$e passe.