E. Lucas 在 1883 年創造的"Towers of Hanoi"難題背後的古老民間傳說是很有名的。一個最近的傳說告訴我們在 Benares 的 Brahmin 和尚們絕不相信，在他們把 64 片盤子從一個柱子全部搬到另外一個的那一刻，世界就會毀滅，所以他們決定要儘快完成這個工作。

圖片：四根柱子的 Tower of Hanoi

一個在 Benares 神殿的的祭司（他喜歡數學）跟他的同事保證，如果用一個額外的柱子，就可以在下午完成搬運（他們認為每秒可以搬一個盤子）。他們不相信他，但是他向他們提出以下策略：

-- 把最上面的 k 個盤子搬到備用的柱子。
-- 然後用原本的三個柱子的策略去把剩下的 n-k 的盤子搬到他們的目標。
-- 最後用四個柱子把最上面的 k 個盤子搬到目標。

他計算 k 的值使得移動的次數最少，結果是總共 18433 次，所以他們只要花 5 個小時 7 分 13 秒，比不用一個額外柱子的 5000 億年（他們要搬 2^64-1 次盤子，你相信嗎？）好多了。

試著照這個聰明的祭司的策略計算用四個柱子要搬幾次。根據 Brahma 固定不變的法律，一次只能移動一個盤子，而且不能放在比較小的盤子上面。當然，主要的目標是計算 使搬移次數（就算不確定這是不是最佳的移動次數）最少的 k。