計算題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 次就在角落,又跳到角落,有
2k2種
2. 第 2 次在中心(即 O 點),再跳到角落,有
k1
1
4=4k1 種,
其中
k1
1 表示第 2 次在中心的方法數,由第 1 次在角落的方法數乘以1而來 !
因此,
kn=2kn−1+4kn−2
n=3
4
5
6



而且滿足
4kn=bn (4個角落為對稱情形),
kn−1=an
因為
kn
=4
8
32
96
320
1024



故
a6+b6=k5+4k6=320+41024=320+256=576