ハノイの塔(1883) — 数学者が偽名で売り出した、六十四枚の円盤の伝説

はじめに — 三本の棒と、大きさの違う円盤

これは1883年にフランスで売り出された、木の円盤を三本の棒の間で移す遊びである。円盤は大きさがすべて違い、最初は一本の棒に、大きい順に積まれている。目標は、これを別の棒へそっくり移すことだ。

規則は二つだけ。一度に動かせるのは一枚。そして、小さい円盤の上に大きい円盤を載せてはならない。三枚なら七手で終わる。五枚なら三十一手かかる。枚数を増やすと、手数は急に膨らむ。

考えたのはフランスの数学者エドゥアール・リュカである。ただし売り出したときの名義は、リュカ本人ではなかった。「シャムのN・クロース教授」という架空の人物が作者として載っていた。

大きい順に積まれた五枚の円盤のイメージ（イメージ・AI生成）

その時代の文脈 — 偽名の教授と、ブラフマーの塔の伝説

リュカの偽名「N. Claus (de Siam)」は、「Lucas d'Amiens(アミアンのリュカ)」の文字を並べ替えたものだとされる。日本語版 Wikipedia も、勤務先の学校名と本人の名前のアナグラムだと説明している。

遊びには、説明書の形で伝説が付いていた。インドのベナレスの寺院に、純金の円盤が六十四枚ある。僧たちが、同じ規則で昼も夜も塔を移し替えている。全部移し終えたとき、世界は終わる、という話だ。

箱の名前は「ハノイの塔」、説明書の塔は「ブラフマーの塔」だった。ハノイはベトナム北部の都市である。東洋の神秘を匂わせる名前を並べて、数学の遊びに物語を着せたのだ。

リュカの解説は、のちに遺作『数学遊戯(Récréations mathématiques)』にも載った。小冊子としての刊行は1889年である。数学者が自分の名を伏せ、遊びとして売る。十九世紀の数学ブームらしい工夫だった。

伝説の「塔」を連想させる夜景のイメージ（イメージ・AI生成）

メカニクス — 小さな問題に分けると、手数が数式になる

解き方の核は、問題を小さくすることだ。n枚を移すには、まず上のn−1枚を空いた棒へ避ける。次に一番大きい円盤を目的の棒へ置く。最後に避けておいたn−1枚を、その上へ戻す。

これを繰り返すと、最短の手数は 2のn乗−1 になる。3枚なら7、5枚なら31。この式は英語版 Wikipedia にも載る基本事項である。1枚増えるごとに、手数はほぼ倍になる。

六十四枚なら、2の64乗−1 手、つまり18,446,744,073,709,551,615 手である。一秒に一手動かしても、約5850億年かかる。伝説の「世界の終わり」は、宇宙の今の年齢よりはるかに先にあることになる。

この計算で、遊びは手でやる遊戯から、数え方の練習に変わった。どれだけ速く動かしても足りない。だから「規則を見つければ、考えなくても全部わかる」という体験が生まれる。

三枚の円盤を七手で移す、八つの局面（図解・イメージ・AI生成）

現代への系譜 — 棒が四本になると、百年以上の宿題になった

棒を四本に増やした場合も、よく研究されてきた。英語版 Wikipedia によると、四本以上の棒での手順は、1941年のフレーム–スチュワートの方法として知られる。最短かどうかの証明は、長く残された。

2014年6月、ティエリー・ブーシュが、四本の場合にこの手数が確かに最小だと示す論文(プレプリント)を公開した。ブーシュ自身が書くとおり、この予想は計算機で N=30 まで確かめられていたが、証明はなかった。

遊びの形は、心理学にも渡った。1982年に心理学者ティム・シャリスが作った「ロンドン塔課題」は、ハノイの塔に関連する検査として知られ、計画を立てる力を調べるのに使われる。

当サイトの別記事にも、ハノイの塔が登場する。同じ「手順を読む」遊びという点では、[九連環(1872)](/articles/baguenaudier-1872)が近い親戚だ。AIの推論力を測る話は、[Pereira らの論文紹介](/articles/paper-pereira-hanoi-world-model)で読める。

小さな問題が大きな問題を作る入れ子構造のイメージ（イメージ・AI生成）

参考文献

本記事で参照した情報源:

・Wikipedia(英): Tower of Hanoi

・Wikipedia(日): ハノイの塔

・Thierry Bousch: The Fourth Tower of Hanoi(2014年6月15日付プレプリント)

・Wikipedia(英): Tower of London test

※「シャムのN・クロース教授」の偽名と64枚の伝説は上記 Wikipedia の記述による。1889年の小冊子刊行も同様。一次の説明書は確認していない。

おわりに — 数学者が、物語で遊びを売った年

1883年のハノイの塔が示したのは、規則が二つで済む遊びでも、深い構造を隠せるという事実である。円盤を動かすたびに、私たちは再帰の形をなぞっている。

伝説は作り話だ。しかし作り話があったから、「六十四枚」という数字が人の記憶に残った。数学と物語を一緒に売る手は、百四十年たった今も古くない。

あなたの手元に、三本の棒はあるだろうか。なければ、コイン三枚と紙に引いた三本の線でも十分だ。まず三枚で、七手を確かめてほしい。

三本の棒と一枚の円盤だけが残る、静かな情景のイメージ（イメージ・AI生成）