Sposoby podania piłki

Question

Pięć osób podaje między sobą piłkę. Piłka zaczyna się od Alonzo. Każda osoba, która ma piłkę, podaje ją komuś innemu. Po ósmym podaniu piłka wraca do Alonza. Znajdź liczbę możliwych sekwencji przejść.

Wiem, że skoro jest 8 przejść, to są $4^8$ sposoby podania piłki, gdy nie ma ograniczeń i po tym $7$ przepustki tam były $4^6$sposoby podania piłki z powrotem do Alonzo. Jak mam kontynuować?

Answer 1

Pracujmy rekurencyjnie, ograniczając się do tych ścieżek, które zaczynają się od $A$ (my położyliśmy $A$ w $0^{th}$ szczelina struny).

Pozwolić $a_n$ być liczbą ścieżek o długości $n$ kończy się w $A$. Aby naprawić zapis, powiedzmy, że inicjał$A$nie jest wliczany do długości. Więc mamy$a_1=0$ na przykład, ponieważ nie możemy umieścić $A$ w gnieździe $1$.

Pozwolić $b_n$ być liczbą ścieżek o długości $n$ które nie kończą się na $A$. Następnie,$b_1=4$ na przykład.

Jak zauważyłeś, mamy $$a_n+b_n=4^n$$

Mamy rekursywnie $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$

To już wystarczy, aby rozwiązać Twój problem i otrzymujemy $$\boxed{a_8=13108}$$ Trochę dodatkowej pracy to pokazuje $$a_n=\frac {4^n+4\times (-1)^n}5$$

Answer 2

Wskazówka:

Pozwolić $a_n$ być liczbą możliwych sekwencji $n$ podania, gdzie Alonzo zaczyna z piłką, a Alonzo odzyskuje ją po $n$th pass. Następnie$a_1 = 0$ i $a_2 = 4$.

Załóżmy, że mamy sekwencje $n$podania, gdzie Alonzo zaczyna od piłki, a każda osoba, która ma piłkę, podaje ją komuś innemu, ale ostatnie podanie nie musi być do Alonzo. Istnieją 4 opcje dla każdego przejścia, więc są$4^n$możliwe sekwencje. W$a_n$ z tych sekwencji Alonzo jest ostatnią osobą, która ma piłkę, co oznacza, że ​​tak $4^n - a_n$ sekwencje, w których Alonzo nie jest ostatnią osobą.

Teraz użyj rekurencji. Zauważ, że Alonzo nie może mieć piłki na$n-1$th pass.