ハノイの塔は、古い言い伝えのある遊びのように見えますが、作られたのは19世紀の終わりです。考えたのは、フランスの数学者エドゥアール・リュカ(1842〜1891年)でした。
1883年、偽名で売り出されたパズル
ハノイの塔は1883年、フランスで売り出されました。箱に書かれた作者の名前は「N. クラウス・ド・シャム教授」。これはリュカの遊び心で、「Claus de Siam(クラウス・ド・シャム)」の文字を並べ替えると「Lucas d’Amiens(アミアンのリュカ)」になります。アミアンはリュカの生まれた町です。
リュカは、フィボナッチ数に似た「リュカ数」や、大きな数が素数かどうかを確かめる方法の研究で知られる数学者です。数学を楽しむための遊びにも熱心で、ハノイの塔のほかにもいくつものパズルや数の遊びを紹介しました。
64枚の金の円盤の伝説
ハノイの塔には、次のような伝説が添えられて広まりました。
インドのベナレスにある寺院には、ダイヤモンドの針が3本立ち、そのうち1本に64枚の金の円盤が積まれている。僧たちは昼も夜も休まず、決まりに従って円盤を移し続けている。すべての円盤を移し終えたとき、世界は終わる。
この伝説は、古くからの言い伝えではなく、パズルを売り出したころに作られたものと考えられています。それでも、64枚を移すのにかかる時間を計算すると、伝説が少しも大げさでないことが分かります(円盤64枚だと何年かかる?)。
なぜ「ハノイ」なのか
ハノイはベトナムの首都ですが、パズルそのものとベトナムとの関わりは知られていません。売り出された当時は、フランスがベトナム北部へ進出していた時期でした。遠い異国の響きのある名前として付けられたと考えられています。伝説の舞台がインドなので、「ブラフマーの塔」と呼ばれることもあります。
4本の棒の変わり種
棒を4本に増やすと、どうなるでしょうか。イギリスのパズル作家ヘンリー・デュードニーは、1907年の本でこの問題を「レーヴのパズル」として紹介しました。棒が1本増えるだけで、手数はぐっと少なくなります。
ところが、4本のときのいちばん少ない手数を求める方法は、長いあいだ証明されませんでした。よく使われる解き方(フレーム・スチュワートの方法)が本当に最少なのかは、2014年になってようやく示されました。3本なら式が1つで済むのに、4本になると100年以上の難問になったのです。くわしくは棒が4本のハノイの塔で紹介しています。
小さな棒と円盤だけの遊びに、数学の深い問題が隠れている。ハノイの塔が140年以上遊ばれ続けているのは、そんなところにも理由があるのかもしれません。
