Question

(有趣的漢諾塔問題)一塊黃銅平板上裝著三根金剛石細柱，其中一根細柱上套著64個大小不等的環(huán)形金盤，大的在下，小的在上，如圖所示．這些盤子可每次一個地從一根柱子轉移到另一根柱子，但不允許較大盤子放在較小的盤子的上面，若把這64個金盤從一根柱子全部移到另一根柱子上，至少須移動多少次？

Answer 1

答案：
解析：

用an表示將n個盤子從一根柱子移到另一根柱子上至少須移動的次數．顯然a0＝0，a1＝1，a2＝3． 　　對于n個盤子，可看成先把柱子A的n－1個盤子看成一個整體，套到柱子C上，此時．需要a次，再把A中底下的大盤移到B柱，然后再把C中的n－1個盤子移到B柱，此時需要1＋a次．所以有an＝2a＋1． 　　由數列知識可得an＝2n－1． 　　回到原問題上來，則至少移動264－1次．如果是一個人用手工移動，幾輩子也不可能完成這個任務，也就大可不必擔心世界末日的來臨．