回復 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