申論題

13. 河內塔（Tower of Hanoi）是根據一個傳說形成的數學問題：
有三根杆子 A，B，C。A 杆上有 6 個穿孔圓盤，圓盤的尺寸由上到下依次變大。要求按下列規則將所有圓盤移至 C 杆：
(i) 每次只能移動一個圓盤；
(ii) 大圓盤不能疊在小圓盤上面。
此問題當「初始盤面為 6 個圓盤皆放在 A 杆上」時，最少步數為 63 步，我們將 63 步稱為該初始盤面的最佳解。若重新規定6 個圓盤不一定都要放在 A 杆上，只要符合「大圓盤的下方都沒有較小的圓盤」，都是可行的初始盤面。則在這些初始盤面中，
有__________種盤面的最佳解是 63 步。