ハノイの塔
一方にたまったディスクを一枚ずつ柱から柱に移し、最終的には、他の柱に移すことです。
小さなディスク上に大きなディスクを積むことができません。
ハノイの塔の話
インドで梵天の塔と呼ばれるものがあるとします。
インドの神である、梵天が宇宙創造時に作ったという言葉が伝えられてきます。
そこには、3つのダイヤ柱と中心に穴がある64枚の純金ディスクがあります。
ディスクは、すべてのサイズが異なり、小さい方が上になるように柱に通しております。初めてディスクはすべて一柱に通しております。
ここでは、僧侶たちの仕事は、このディスクを一度に一枚ずつ柱で柱に移し、最終的には、すべての三本柱に移すことです。ただし、小さなディスク上に大きなディスクを積むことができません。
僧侶たちは、昼と夜の継続動いたが、まだ完成していませんでした。完成したとき、塔は崩壊され、世界は終末が来る話です。
以上は、フランスの数学者Edouard Lucasが作った話です。
ディスクの最小移動回数
n枚のディスクを移動するための最小限の移動回数anは、次のとおりです。
64枚の梵天の塔である場合には、
回の移動が必要です。1秒たび一つずつ動くとき、梵天の塔が完成されて、宇宙の終わりが来るまでに、約580億年ほどかかります。