Question

[Lê Chu Linh]

Cho hình lập phương ABCDA'B'C'D'. Một con ếch bắt đầu từ đỉnh A, mỗi bước con ếch nhảy sang các đỉnh kề bên. Hỏi có bao nhiêu cách để con ếch đến đỉnh C' sau 7 bước?

Answer 1

[Trần Thị Hoài An]

Vì số bước nhảy từ đỉnh A đến điểm E là một số chẵn nên a2n−1=0a2n−1=0
Muốn chứng minh công thức đối với a2na2n ta dùng phương pháp quy nạp .
Muốn thế ta tìm công thức truy toán với a2na2n.
Gọi bnbn là số đường đi từ đỉnh C đến đỉnh E ( số đường đi từ G đến E cũng = bnbn)
Ta nhận thấy a1=a2=a3=0,a4=2a1=a2=a3=0,a4=2. Với n>2n>2 ta lại có:
a2n=2a2n−2+2b2n−2a2n=2a2n−2+2b2n−2 (1)
Điều này ứng với: bằng 2 bước nhảy đầu tiên hoặc là ếch trở về đỉnh A ( 2 đường đi), hoặc là chuyển tới một trong 2 đỉnh C hoặc G.
Ngoài ra: b2n=2b2n−2+a2n−2b2n=2b2n−2+a2n−2 (2)
Điều này ứng với: từ điểm C (hoặc G) với 2 bước nhảy ếch có thể hoặc đến B hoặc đến D ( đến H hoặc đến F) rồi trở về C ( hoặc về G), hoặc là đến A.
Lấy (2) - (1) từng vế ta được:
b2n=a2n−a2n−2b2n=a2n−a2n−2
hay b2n−2=a2n−2−a2n−4b2n−2=a2n−2−a2n−4 (3)
Thay (3) vào (2) ta được: a2n=4a2n−2−2a2n−4a2n=4a2n−2−2a2n−4
Với công thức này và các giá trị a2=0,a4=2a2=0,a4=2 ta có thể xác định lần lượt tất cả các số a2ka2k
Vấn đề còn lại là kiểm tra bằng qui nạp công thức:
a2n=1√2.((2+√2)n−1−(2−√2)n−1)a2n=12.((2+2)n−1−(2−2)n−1)
Thật vậy, cho rằng a2n−2=1√2.(xn−2−yn−2a2n−2=12.(xn−2−yn−2 và a2n−4=1√2.(xn−3−yn−3)a2n−4=12.(xn−3−yn−3) ta được:
a2n=1√2(4xn−2−4yn−2−2xn−3+2yn−3)a2n=12(4xn−2−4yn−2−2xn−3+2yn−3)
=1√2(xn−3(4x−2)−yn−3(4y−2))=12(xn−3(4x−2)−yn−3(4y−2))
=1√2(xn−3(6+4√2)−yn−3(6−4√2))=12(xn−3(6+42)−yn−3(6−42))
Mà (2+√2)2=6+4√2,(2−2√2)2=6−4√2(2+2)2=6+42,(2−22)2=6−42 nên a2n=1√2.((2+√2)n−1−(2−√2)n−1)a2n=12.((2+2)n−1−(2−2)n−1)