Modi per passare intorno a una palla
Cinque persone si passano una palla tra di loro. La palla parte con Alonzo. Ogni persona che ha la palla la passa a qualcun altro. Dopo l'ottavo passaggio, la palla torna ad Alonzo. Trova il numero di possibili sequenze di passaggi.
So che poiché ci sono 8 passaggi, ci sono $4^8$ modi di passare la palla quando non ci sono restrizioni e dopo $7$ passa ci sarebbero $4^6$modi per restituire la palla ad Alonzo. Come continuo?
Risposte
Lavoriamo in modo ricorsivo, limitandoci a quei percorsi che iniziano con $A$ (abbiamo messo $A$ nel $0^{th}$ slot della corda).
Permettere $a_n$ essere il numero di percorsi di lunghezza $n$ che finiscono in $A$. Per correggere la notazione, diciamo che l'iniziale$A$non viene conteggiato nella lunghezza. Quindi, abbiamo$a_1=0$ per esempio, poiché non possiamo mettere $A$ nello slot $1$.
Permettere $b_n$ essere il numero di percorsi di lunghezza $n$ che non finiscono in $A$. Poi,$b_1=4$ per esempio.
Come fai notare, abbiamo $$a_n+b_n=4^n$$
Ricorsivamente, abbiamo $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$
È già abbastanza per risolvere il tuo problema e otteniamo $$\boxed{a_8=13108}$$ Un po 'di lavoro in più lo dimostra $$a_n=\frac {4^n+4\times (-1)^n}5$$
Suggerimento:
Permettere $a_n$ essere il numero di possibili sequenze di $n$ passa, dove Alonzo parte con la palla, e Alonzo la riprende dopo il $n$esimo passaggio. Poi$a_1 = 0$ e $a_2 = 4$.
Supponiamo di avere una sequenza di $n$passa, dove Alonzo inizia con la palla, e ogni persona che ha la palla la passa a qualcun altro, ma l'ultimo passaggio non deve essere per Alonzo. Ci sono 4 scelte per ogni passaggio, quindi ci sono$4^n$possibili sequenze. In$a_n$ di queste sequenze, Alonzo è l'ultima persona ad avere la palla, il che significa che ci sono $4^n - a_n$ sequenze in cui Alonzo non è l'ultima persona.
Ora usa la ricorsione. Nota che Alonzo non può avere la palla sul$n-1$esimo passaggio.