計算題1.
如下圖,
O為正方形
ABCD的中心。程式設定讓機器跳蚤在圖中諸點之間跳動﹐每次都可以跳到相鄰的任何一點﹐例如:由
A點可跳到
O﹑
B﹑
D中的任何一點﹐由
O 點可跳到
A﹑
B﹑
C﹑
D中的任何一點。設從
O點開始﹐經
n次跳動返回
O點的路線有
an種﹐而經
n次跳動到達
A 點的路線有
bn種 ,試求
a6+b6 。 答: 320+256=576種
A-----------------D
| |
| O |
| |
B-----------------C
參考解法: 考慮經 n 次跳動,落在角落(A,B,C,D)的方法數
kn
首先,
k1=4
k2=4
2=8
k3=2k2+4k1=32
這是因為第 3 次跳到角落的方法數
k3有 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