Một màn chơi của một trò chơi điện tử được thiết kế như sau: có năm vị trí A, B, C, D, E được đặt ở năm đỉnh của một hình chóp tứ giác. Nhân vật sẽ được đặt ở một vị trí bất kỳ
20/22
Một màn chơi của một trò chơi điện tử được thiết kế như sau: có năm vị trí \[A\], \[B\], \[C\], \[D\], \[E\], được đặt ở năm đỉnh của một hình chóp tứ giác. Nhân vật sẽ được đặt ở một vị trí bất kỳ, và có thể di chuyển tự do giữa các đỉnh với nhau, mỗi lần di chuyển đều phải từ đỉnh này di chuyển đến đỉnh khác. Giả sử khi bắt đầu, nhân vật được đặt ở vị trí \[A\]. Số cách di chuyển để sau sáu bước nhảy, nhân vật quay lại vị trí \[A\] là bao nhiêu?
Lời giải
Đáp án: \[820\]
Vì mỗi bước có \[4\] cách đi nên tổng số cách đi sau \[n\] bước là \[{4^n}\].
Gọi \[{u_n}\] là số cách đi từ \[A\] để sau đúng \[n\] bước nhân vật ở vị trí \[A\].
Trong \[{4^n}\] bước, có \[2\] trường hợp:
- Nhân vật ở vị trí \[A\]: có \[{u_n}\] cách. Khi đó bước \[n + 1\] nhân vật không thể ở vị trí \[A\].
- Nhân vật không ở vị trí \[A\]: có \[{4^n} - {u_n}\] cách. Khi đó có đúng \[1\] cách để bước \[n + 1\] nhân vật ở vị trí \[A\].
Suy ra \[{u_{n + 1}} = 0 \cdot {u_n} + 1 \cdot \left( {{4^n} - {u_n}} \right) = {4^n} - {u_n}\].
Ta có:
\[{u_0} = 1\]
\[{u_1} = 0\]
\[{u_2} = {4^1} - {u_1} = 4\]
\[{u_3} = {4^2} - {u_2} = 12\]
\[{u_4} = {4^3} - {u_3} = 52\]
\[{u_5} = {4^4} - {u_4} = 204\]
\[{u_6} = {4^5} - {u_5} = 820\]