ハノイの塔をいちばん少ない手数で解くと、その手順にはおどろくほどきれいな規則性があります。ここでは、円盤がn枚の塔を左から右へ移す最少手順(2ⁿ−1手)について、見つかる決まりを順に紹介します。円盤には小さい順に1、2、3…と番号を付けます。
円盤ごとの動く回数は2のべき乗
最少手順の中で、それぞれの円盤が動く回数は決まっています。n枚のとき、k番の円盤は 2ⁿ⁻ᵏ回 動きます。
| 円盤(4枚のとき) | 動く回数 |
|---|---|
| 1 | 8回 |
| 2 | 4回 |
| 3 | 2回 |
| 4 | 1回 |
| 合計 | 15回 |
いちばん大きい円盤は1回、その次は2回、その次は4回…と、小さくなるごとに2倍になります。合計すると 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1 で、最少手数にぴったり一致します。
理由は、最少手数の公式と同じ考え方で分かります。n枚を移すには、n−1枚の塔を2回移します。だから、n番より小さい円盤は、n−1枚を移すときの2倍ずつ動くことになるのです。
何手目にどの円盤が動くか
4枚の最少手順で、1手目から順に動く円盤の番号を並べると、次のようになります。
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1
1が1手おきに出てきて、そのあいだに2が1つおきに、さらにそのあいだに3が…と入っています。ものさしの目盛りの長さの並び(短い・中くらい・短い・長い…)と同じ形です。
この並びは、手目を2進数で書くと、すぐに求められます。
| 手目 | 2進数 | 末尾の0の個数 | 動く円盤 |
|---|---|---|---|
| 1 | 1 | 0個 | 1 |
| 2 | 10 | 1個 | 2 |
| 3 | 11 | 0個 | 1 |
| 4 | 100 | 2個 | 3 |
| 5 | 101 | 0個 | 1 |
| 6 | 110 | 1個 | 2 |
| 7 | 111 | 0個 | 1 |
| 8 | 1000 | 3個 | 4 |
m手目に動くのは、mを2進数で書いたときの「末尾に並ぶ0の個数+1」番の円盤です。奇数の手目は2進数の末尾が1なので、いつも1が動きます。これが、解き方の記事の「奇数回目は1を動かす」の理由です。
さらに、動かす元と先の棒も2進数の計算だけで求められます(アルゴリズムの記事)。
グレイコードとのつながり
2進数を0から順に数えるとき、1つ増やすたびに変わる桁の数はまちまちです(0111から1000では4桁が変わります)。そこで、1つ進むごとに1桁だけが変わるように並べた数の表し方を「グレイコード」といいます。
| 順番 | グレイコード | 変わる桁(右から) |
|---|---|---|
| 0 | 000 | ― |
| 1 | 001 | 1 |
| 2 | 011 | 2 |
| 3 | 010 | 1 |
| 4 | 110 | 3 |
| 5 | 111 | 1 |
| 6 | 101 | 2 |
| 7 | 100 | 1 |
変わる桁の並び「1 2 1 3 1 2 1」は、ハノイの塔で動く円盤の並びとまったく同じです。円盤1枚を2進数の1桁と見て、「その桁が変わる=その円盤が動く」と考えると、ハノイの塔の最少手順は、グレイコードを順にたどることと同じになります。
円盤の回る向き
解き方の記事で、1はいつも同じ向きに回ると紹介しました。実は、ほかの円盤にも同じ決まりがあります。
- 奇数番の円盤(1・3・5…)は、すべて1と同じ向きに回る。
- 偶数番の円盤(2・4・6…)は、すべて1と逆の向きに回る。
左の塔を右へ移すとき、奇数枚なら1は「左 → 右 → 中央」の向き、偶数枚なら「左 → 中央 → 右」の向きです。どの円盤も、最後まで一度も向きを変えません。
もう1つ、10段の解き方で紹介した決まりもあります。最少手順では、奇数番の円盤の上に奇数番を、偶数番の上に偶数番を直接置くことがありません。
置き方は全部で3ⁿ通り
ルールを守った円盤の置き方は、全部で何通りあるでしょうか。どの円盤も3本のどれかに置け、同じ棒に載った円盤の順番は大きい順に決まってしまうので、置き方は 3ⁿ通り です。
| 円盤の枚数 | 置き方 |
|---|---|
| 3枚 | 27通り |
| 5枚 | 243通り |
| 7枚 | 2,187通り |
| 9枚 | 19,683通り |
しかも、どの置き方からどの置き方へも、ルールを守って必ず移れます。すべての置き方を点で表し、1手で移れる点どうしを線でつなぐと、大きな三角形の中に小さな三角形が入れ子になった「シェルピンスキーの三角形」とよく似た図形になることも知られています。
アプリ「ハノイの塔」の「問題」モードは、この全部の置き方の中から、見本の形にそろえる問題を作っています。9枚の★5でも、19,683通りの置き方すべてについて最短の手数を調べたうえで出題しています。
