數學謎題：移動塔

法國數學家愛德華·盧卡斯於 1842 年出生於亞眠，49 年後在巴黎去世。他撰寫了四卷本著作《數學娛樂》，該書成為休閒數學的經典之作。1883 年，他以筆名“N. 克勞斯·德·暹羅”（“盧卡斯·德·亞眠”的 anagram）推銷了一種單人遊戲，他稱之為河內塔。

他聲稱這款遊戲是所謂梵天塔的簡化版。在這一假想的傳說中，僧侶們必須在一個宏偉的寺廟中移動一座由 64 個金盤組成的塔。然而，在他們完成這項任務之前，寺廟就會化為塵土，世界末日就會到來。

河內塔由一個小型木板組成，木板上安裝了三個相同的圓柱形杆。左杆上有五個大小不同的圓盤，中間有一個孔。它們按大小排列，最大的圓盤在底部。遊戲的目標是以儘可能少的步數將所有圓盤從左杆移動到右杆。在每一步中，只能從一根杆上取出一個圓盤並將其放置在另一根杆上，並且永遠不能將較大的圓盤放在較小的圓盤上。運輸這些圓盤需要多少步，以及哪些步驟是必要的？

顯示謎題答案

我們根據大小用數字替換圓盤。現在我們系統地構建解決方案，從只有一個圓盤的塔開始。解決方案很簡單。只需一步，您就可以將單個圓盤從左邊移動到右邊。

對於有兩個圓盤的塔，您首先將圓盤 1 從左邊移動到中間，然後將圓盤 2 從左邊移動到右邊，最後將圓盤 1 從中間移動到右邊。因此，您需要 3 = 2² – 1 步。

對於有三個圓盤的塔，我們首先在腦海中忽略圓盤 3。這會將問題簡化為只有兩個圓盤的任務，我們現在用三步將其從左邊移動到中間。在第四步中，我們將圓盤 3 從左邊移動到右邊。現在我們再次在腦海中忽略圓盤 3，再次用三步將兩個圓盤從中間移動到右邊。總共需要 3 + 1 + 3 = 7 = 2³ – 1 步。

對於四個圓盤的塔的問題，可以用非常類似的方式簡化為三個圓盤的塔的問題。因此，您需要 7 + 1 + 7 = 15 = 2⁴ – 1 步。最後，對於五個圓盤的塔，您需要 15 + 1 + 15 = 31 = 2⁵ – 1 步。一般來說，對於有 n 個圓盤的塔，您需要 2ⁿ – 1 步。愛德華·盧卡斯最初的遊戲有八個圓盤。

我們很樂意聽到您的來信！請傳送電子郵件至 games@sciam.com 分享您的體驗。

這個謎題最初出現在《Spektrum der Wissenschaft》中，並經許可轉載。