Cách chuyền bóng

Question

Năm người đang chuyền bóng với nhau. Quả bóng bắt đầu với Alonzo. Mỗi người có bóng sẽ chuyền cho người khác. Sau đường chuyền thứ tám, bóng trở lại Alonzo. Tìm số chuỗi các đường chuyền có thể có.

Tôi biết rằng vì có 8 đường chuyền, nên có $4^8$ cách chuyền bóng khi không có giới hạn và sau $7$ vượt qua sẽ có $4^6$những cách chuyền bóng lại cho Alonzo. Làm thế nào để tôi tiếp tục?

Answer 1

Hãy làm việc đệ quy, hạn chế những đường dẫn bắt đầu bằng $A$ (chúng tôi đặt $A$ bên trong $0^{th}$ khe của chuỗi).

Để cho $a_n$ là số con đường có chiều dài $n$ kết thúc bằng $A$. Để sửa ký hiệu, giả sử rằng$A$không được tính theo chiều dài. Vì vậy chúng tôi có$a_1=0$ ví dụ, vì chúng tôi không thể đặt $A$ trong khe $1$.

Để cho $b_n$ là số con đường có chiều dài $n$ điều đó không kết thúc ở $A$. Sau đó,$b_1=4$ ví dụ.

Như bạn nhận xét, chúng tôi có $$a_n+b_n=4^n$$

Đệ quy, chúng ta có $$a_n=b_{n-1}\quad \&\quad b_n=4a_{n-1}+3b_{n-1}=4^n-b_{n-1}$$

Như vậy đã đủ để giải quyết vấn đề của bạn và chúng tôi nhận được $$\boxed{a_8=13108}$$ Một chút việc làm thêm cho thấy rằng $$a_n=\frac {4^n+4\times (-1)^n}5$$

Answer 2

Dấu:

Để cho $a_n$ là số chuỗi có thể có của $n$ chuyền, nơi Alonzo bắt đầu với bóng, và Alonzo lấy lại sau $n$thứ vượt qua. Sau đó$a_1 = 0$ và $a_2 = 4$.

Giả sử chúng ta có một chuỗi $n$Các đường chuyền, nơi Alonzo bắt đầu với bóng, và mỗi người có bóng sẽ chuyền cho người khác, nhưng đường chuyền cuối cùng không nhất thiết phải thuộc về Alonzo. Có 4 lựa chọn cho mỗi lần vượt qua, vì vậy có$4^n$trình tự có thể. Trong$a_n$ trong số các chuỗi này, Alonzo là người cuối cùng có bóng, có nghĩa là có $4^n - a_n$ trình tự mà Alonzo không phải là người cuối cùng.

Bây giờ sử dụng đệ quy. Lưu ý rằng Alonzo không thể có bóng trên$n-1$thứ vượt qua.