第五題
我認為這題怪怪的
n=1 時 明顯
a1=2
考慮下列過程
設將 n+1 個圓盤由 A 移至 B 的步驟數為
an+1
可拆成五個步驟如下:
(STEP-1) 將 n 個圓盤由 A 移至 B 步驟數為
an
(STEP-2) 將第 n+1 個圓盤由 A 移至 C 步驟數為 1
(STEP-3) 將 n 個圓盤由 B 移至 A 步驟數為
an
(STEP-4) 將第 n+1 個圓盤由 C 移至 B 步驟數為 1
(STEP-5) 將 n 個圓盤由 A 移至 B 步驟數為
an
以上步驟累加 得
an+1=3
an +2
而這正是參考答案的數據.
疑問是
題目敘述: 每次只能搬動一圓盤,且每次都必須先經中間柱(不可由A直接放入B)
(討論 1)
如果此限制 恰只適用 A柱 至 B柱
那 STEP-3 就不該是
an
(討論 2)
如果此限制 不只適用 A柱 至 B柱, 而是適用所有 柱 與 柱 之間的移動
那 STEP-2 與 STEP-4 就無法成立
由上述 討論 1 與 討論 2
故知 我的推論有誤.
錯在哪? 請教 大家