回復 9# milkie1013 的帖子
計算題1.
如下圖, \(O\)為正方形\(ABCD\)的中心。程式設定讓機器跳蚤在圖中諸點之間跳動﹐每次都可以跳到相鄰的任何一點﹐例如:由\(A\)點可跳到\(O\)﹑\(B\)﹑\(D\)中的任何一點﹐由\(O\) 點可跳到\(A\)﹑\(B\)﹑\(C\)﹑\(D\)中的任何一點。設從\(O\)點開始﹐經\(n\)次跳動返回 \(O\)點的路線有 \(\displaystyle a_n \)種﹐而經\(n\)次跳動到達\(A\) 點的路線有 \(\displaystyle b_n \)種 ,試求 \(\displaystyle a_6+b_6\) 。 答: 320+256=576種
A-----------------D
| |
| O |
| |
B-----------------C
參考解法: 考慮經 n 次跳動,落在角落(A,B,C,D)的方法數 \(\displaystyle k_n \)
首先, \(\displaystyle k_1=4, k_2=4*2=8 \)
\(\displaystyle k_3=2k_2+4k_1=32 \)
這是因為第 3 次跳到角落的方法數 \(\displaystyle k_3 \)有 2 個來源 :
1. 第 2 次就在角落,又跳到角落,有 \(\displaystyle 2k_2 \)種
2. 第 2 次在中心(即 O 點),再跳到角落,有 \(\displaystyle k_1*1*4=4k_1 \) 種,
其中 \(\displaystyle k_1*1 \) 表示第 2 次在中心的方法數,由第 1 次在角落的方法數乘以1而來 !
因此, \(\displaystyle k_n=2k_{n-1}+4k_{n-2},n=3,4,5,6,... \)
而且滿足 \(\displaystyle \frac{k_n}{4}=b_n \) (4個角落為對稱情形), \(\displaystyle k_{n-1}=a_n \)
因為 \(\displaystyle <k_n>=4,8,32,96,320,1024,... \)
故 \(\displaystyle a_6+b_6=k_5+\frac{k_6}{4}=320+\frac{1024}{4}=320+256=576 \)