ハノイの塔





ハノイの塔

一方にたまったディスクを一枚ずつ柱から柱に移し、最終的には、他の柱に移すことです。
小さなディスク上に大きなディスクを積むことができません。

ハノイの塔の話

インドで梵天の塔と呼ばれるものがあるとします。
インドの神である、梵天が宇宙創造時に作ったという言葉が伝えられてきます。

そこには、3つのダイヤ柱と中心に穴がある64枚の純金ディスクがあります。
ディスクは、すべてのサイズが異なり、小さい方が上になるように柱に通しております。初めてディスクはすべて一柱に通しております。

ここでは、僧侶たちの仕事は、このディスクを一度に一枚ずつ柱で柱に移し、最終的には、すべての三本柱に移すことです。ただし、小さなディスク上に大きなディスクを積むことができません。
僧侶たちは、昼と夜の継続動いたが、まだ完成していませんでした。完成したとき、塔は崩壊され、世界は終末が来る話です。

以上は、フランスの数学者Edouard Lucasが作った話です。

ディスクの最小移動回数

n枚のディスクを移動するための最小限の移動回数anは、次のとおりです。

an = 2n – 1

64枚の梵天の塔である場合には、

264 -1 = 18446744073709551615

回の移動が必要です。1秒たび一つずつ動くとき、梵天の塔が完成されて、宇宙の終わりが来るまでに、約580億年ほどかかります。