ふつうのハノイの塔は、棒が3本です。では、棒を1本増やして4本にしたら、どうなるでしょうか。ルールは同じで、1回に1枚ずつ、小さい円盤の上に大きい円盤を置かずに、塔を別の棒へ移します。
1本増えるだけで、手数は大きく減る
使える置き場所が1つ増えるので、円盤をどかすのがずっと楽になります。最少手数を比べると、その差は枚数が増えるほど大きくなります。
| 円盤の枚数 | 棒が3本 | 棒が4本 |
|---|---|---|
| 3枚 | 7手 | 5手 |
| 4枚 | 15手 | 9手 |
| 5枚 | 31手 | 13手 |
| 6枚 | 63手 | 17手 |
| 7枚 | 127手 | 25手 |
| 8枚 | 255手 | 33手 |
| 10枚 | 1,023手 | 49手 |
| 64枚 | 約1845京手 | 18,433手 |
3本の棒では、64枚を移すのに1秒に1手でも約5845億年かかります(円盤64枚だと何年かかる?)。ところが4本なら18,433手、1秒に1手で約5時間です。伝説の僧たちが棒を1本増やしていたら、世界はその日のうちに終わっていたことになります。
デュードニーの「チーズのパズル」
4本の棒のハノイの塔を広く紹介したのは、イギリスのパズル作家ヘンリー・デュードニーです。1907年の本『カンタベリー・パズル』の中で、「レーヴのパズル」として出題しました。レーヴ(リーヴ)は、荘園の管理人のことです。
デュードニーの問題では、円盤の代わりに大きさの違う8つのチーズを、4つの腰かけのあいだで移します。小さいチーズの上に大きいチーズを載せてはいけません。答えは33手で、上の表の8枚と同じです。
フレーム・スチュワートの解き方
4本の棒で少ない手数で移す方法は、1941年にJ・S・フレームとB・M・スチュワートが、それぞれ同じ考え方を発表しました。n枚の塔を移すとき、
- 上のk枚を、4本の棒を全部使って、移したい棒以外の棒へ移す。
- 残りのn−k枚を、上のk枚がいる棒を使わずに、3本の棒だけで移したい棒へ移す(2ⁿ⁻ᵏ−1手)。
- 1でどかしたk枚を、4本の棒を全部使って、移したい棒へ移す。
という3つに分けます。1と3は同じ問題の小さい版なので、再帰の考え方が使えます(アルゴリズムの記事)。あとは、上に何枚(k枚)残すといちばん少なくなるかを選ぶだけです。8枚なら、上の4枚か5枚を先にどかすのがいちばん少なく、33手になります。
100年近く証明されなかった「いちばん少ない」
フレーム・スチュワートの方法で少ない手数で移せることは分かりました。ところが、これより少ない方法が本当にないのかは、長いあいだ誰にも証明できませんでした。
3本の棒なら、「いちばん大きい円盤を動かす瞬間、ほかの円盤は全部1本に集まっていなければならない」という1つの事実から、最少手数がすぐに証明できます(最少手数の公式)。4本になると、大きい円盤を動かす瞬間に、ほかの円盤が残りの2本へどう分かれていてもよいので、考えられる手順が一気に増えてしまうのです。
コンピューターで全部の置き方を調べて、30枚ほどまではこの方法が最少だと確かめられていました。そしてデュードニーの出題からおよそ100年後の2014年、フランスの数学者ティエリー・ブーシュが、何枚であってもフレーム・スチュワートの方法が最少であることを証明しました。棒が5本以上の場合は、今も証明されていないとされています。
自分でも試せる
4本の棒のハノイの塔は、作り方の記事の厚紙の作り方で、置き場所の丸を4つにすれば作れます。3枚を5手、4枚を9手で移せるか、試してみてください。3本のときとの違いを体で感じられます。
