細長い枠を右手で扱うことにして、枠の取っ手が右に来るように 置きます。輪を枠からはずしたり、枠にはめたりするのは、左手で 扱います。（２進法との対応を考えると枠の取っ手が左の方が良い のですが、筆者は上のきを選びました。なるべく左手を使う機会を 多くしようという心理が働いているように思います。） ９つの輪には左から順に１、２、３、４、と９まで番号をつけま す。 いくつかの操作に記号をつけましょう。「操作に」であって「状 態に」ではないことに注意して下さい。 輪 n (のみ）を枠からはずす（おろす）ことを n_ で、輪 n (の み）を枠にはめる（あげる）ことを n^ で表します。 n の輪が上がっていて 1 から n-1 までの輪が下がっている状 態から、1 から n までの輪がすべて下がっている状態にする操作を dn で表します。（d は down のd）。 逆に、1 から n までの輪がすべて下がっている状態から、n の輪 が上がっていて 1 から n-1 までの輪が下がっている状態にする操 作を un で表します（u は up のu）。 このときどちらも、 n+1 以上の輪の状態は任意で構いません。 始めのいくつかの例を示します。 d1 = 1_ u1 = 1^ d2 = 1^ 2_ 1_ u2 = 1^ 2^ 1_ d3 = 1^ 2^ 1_ 3_ 1^ 2_ 1_ u3 = 1^ 2^ 1_ 3^ 1^ 2_ 1_ ここで次の事実に気づく事が肝要です。 すなわち、２の輪が上がっていて、１の輪が下がっているとき、 そしてそのときに限り、３の輪を自由に上げたり下げたりするこ とができます。
もっと一般に n-1 の輪が上がっていて、１から n-2 までの輪が 下がっているとき、そしてそのときに限り、 n の輪を自由に上げ たり下げたりすることができます。 このことから d2 = u1 2_ d1 u2 = u1 2^ d1 d3 = u2 3_ d2 u3 = u2 3^ d2 と書きなおせることに気づきます。 dn と un は互いに逆元の関係だから、これらはそれぞれ一つ 前の d(n-1) による共役の形です。 すなわち漸化式 dn = u(n-1) n_ d(n-1) un = u(n-1) n^ d(n-1) が得られて、ハノイの塔の漸化式と同じ形となりました。 したがって２進法との関係も明白です。 ４桁までの２進法、４段のハノイの塔、四連環の解法が「同型」 となる対応を とくとご覧下さい。 A B C D ハノイの塔 四連環 ------------------------------------------------------ 4321 6 6 6 9 1 1 1 1 432 1 9 6 6 9 2 10 10 2 43 1 2 9 9 6 9 3 11 1 1 43 21 6 9 6 9 4 100 100 3 4 3 21 6 9 9 9 5 101 1 1 41 3 2 9 9 9 9 6 110 10 2 41 32 9 6 9 9 7 111 1 1 4 321 6 6 9 9 8 1000 1000 4 321 4 6 6 9 6 9 1001 1 1 32 41 9 6 9 6 10 1010 10 2 2 3 41 9 9 9 6 11 1011 1 1 21 3 4 6 9 9 6 12 1100 100 3 21 43 6 9 6 6 13 1101 1 1 2 1 43 9 9 6 6 14 1110 10 2 1 432 9 6 6 6 15 1111 1 1 4321 6 6 6 6 四連環で 6 6 6 9 とは 1 から 3 までの輪が下がって、 4 の 輪だけが上がっている状態です。そこから 6 6 6 6 、すなわち、 すべての輪が下がっている、つまり枠がはずれた状態までの動きを 示しています。 ここで２進法の欄は 「操作」を表していて、ハノイの塔と四連 環の欄は 「状態」 を表していることにご留意下さい。 ちょうど「植木算」の植木と間隔の関係と同様です。植木が状態 に、間隔が操作に当たります。 ところで、九連環というゲームは、9 9 9 9 9 9 9 9 9 を 6 6 6 6 6 6 6 6 6 にするものですから、これを dn や un で表 そうとすると不自然になります。練習問題と思ってやってみて下さい。 そこで新しく、 9 9 9 9 を 6 6 6 6 にする操作を D4、その逆で 6 6 6 6 を 9 9 9 9 にする操作を U4 などと表すことにします。 すると D1 = 1_ U1 = 1^ D2 = 2_ 1_ U2 = 1^ 2^ D3 = D1 3_ U1 D2 U3 = U2 D1 3^ U1 D4 = D2 4_ U2 D3 U4 = U3 D2 4^ U2 などとなります。 漸化式は Dn = D(n-2) n_ U(n-2) D(n-1) Un = U(n-1) D(n-2) n^ U(n-2) となります。 九連環の解き方は、 D9 がその「答え」です。