Cara Mengoper bola

Question

Lima orang mengoper bola di antara mereka sendiri. Bola dimulai dengan Alonzo. Setiap orang yang menguasai bola akan mengopernya ke orang lain. Usai umpan kedelapan, bola kembali ke Alonzo. Temukan jumlah kemungkinan urutan lintasan.

Saya tahu karena ada 8 lintasan, jadi ada $4^8$ cara mengoper bola saat tidak ada batasan dan setelahnya $7$ lulus akan ada $4^6$cara untuk mengoper bola kembali ke Alonzo. Bagaimana saya melanjutkan?

Answer 1

Mari bekerja secara rekursif, membatasi pada jalur yang dimulai dengan $A$ (kami meletakkan $A$ dalam $0^{th}$ slot dari string).

Membiarkan $a_n$ menjadi jumlah jalur panjang $n$ itu berakhir $A$. Untuk memperbaiki notasi, katakanlah itu inisial$A$tidak dihitung panjangnya. Jadi kita punya$a_1=0$ Misalnya, karena kita tidak bisa memasukkan $A$ di slot $1$.

Membiarkan $b_n$ menjadi jumlah jalur panjang $n$ yang tidak berakhir $A$. Kemudian,$b_1=4$ sebagai contoh.

Seperti yang Anda katakan, kami punya $$a_n+b_n=4^n$$

Secara rekursif, kami punya $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$

Itu sudah cukup untuk menyelesaikan masalah Anda, dan kami mengerti $$\boxed{a_8=13108}$$ Sedikit kerja ekstra menunjukkan itu $$a_n=\frac {4^n+4\times (-1)^n}5$$

Answer 2

Petunjuk:

Membiarkan $a_n$ menjadi jumlah kemungkinan urutan $n$ operan, di mana Alonzo memulai dengan bola, dan Alonzo mendapatkannya kembali setelah itu $n$lulus th. Kemudian$a_1 = 0$ dan $a_2 = 4$.

Misalkan kita memiliki urutan $n$operan, di mana Alonzo memulai dengan bola, dan setiap orang yang menguasai bola mengoper ke orang lain, tetapi operan terakhir tidak harus ke Alonzo. Ada 4 pilihan untuk setiap pass, jadi ada$4^n$kemungkinan urutan. Di$a_n$ Dari urutan ini, Alonzo adalah orang terakhir yang memiliki bola, yang artinya ada $4^n - a_n$ urutan di mana Alonzo bukan orang terakhir.

Sekarang gunakan rekursi. Perhatikan bahwa Alonzo tidak boleh menguasai bola$n-1$lulus th.