かくして， 与えられた手数からそのときのハノイの塔の状態を復元する方法が明らかになった． n 段のハノイの塔なら，基本的には上で述べたプロセスを n 回繰り返せば， 大きい板から順にどの棒に刺していけばよいのかがわかっていく． たとえ 64 段のハノイの塔の移動が何億年掛かろうとも， その修復には 64 回の繰り返しで十分ではないか！

　しかし，その判断は勇み足だった． その手順を素朴に眺めてしまうと， それぞれの処理は単純なものだから， 64 回の繰り返しなど大したことはないと思い込んでしまう． しかし，それぞれのステップで， どの場合の処理を適用すればよいのかの判定が曲者なのである． m と 2^l-1 の大小を比較するのにどの程度の手間が掛かるのだろうか？

　 64 段のハノイの塔なら，最初に 2⁶³ と手数の大小を比較する必要がある． 式で書いてしまえばたったの 3 文字でしかないが， その値は途轍もなく大きなものになるのだ． ということは，単純に 64 回の繰り返しといっても， そう簡単には事が済まないかもしれない…．

　多少いやな感触が残ったが， すでに事は機械的な数学の世界に持ち込まれている． そうなってしまえば，専門家にとって大した仕事ではない． 冷静になろう．

　そこで思いつくのは 2 進法である． 田沼君と中本君とのコンピュータ実験から明らかになったように， ハノイの塔の解法は 2 進法と密接に関係していた． 2 のべき乗を通常の 10 進法の世界で計算しようとすると非常に手間が掛かるが， 2 進法の世界では極めて単純なことなのである．

　そもそも 2 進法というのは， 1 = 2⁰ , 2 = 2¹ , 4 = 2² , 8 = 2³ , 16 = 2⁴ という 2ⁿ の形をした数を組み合わせて任意の数を表現しようというものだ． つまり， 2ⁿ を使うか使わないかに対応して， 右から数えて n 番目の桁に 1 か 0 を置いて数を表現するのである． ただし，一番右側の桁は 0 番目と数える．

　ということは， 2ⁿ 自身を 2 進法で表せば， 先頭が 1 で，その後に 0 が n 個並んだものになる． 例えば， 1 から始めて 2 倍， 2 倍を繰り返していくと， 10 進法ならば手間の掛かる作業だが， 2 進法ならば， 1 を左に 1 つずつずらしてその右側に 0 を補っていくだけでよい． つまり， 2 進法の世界で 2ⁿ を求めることなど極めて簡単なことなのである． それは， 10 進法で 10ⁿ を計算するのが簡単なのと同じことである．

　こう考えていけば， 与えられた手数の m が 2ⁿ より大きいかどうかも簡単に判定できる． 例えば，すでに示したことだが， 1 + 2 + 2² + … + 2^n-1 = 2ⁿ - 1 となることを思い起こそう． これは， 2ⁿ を使わないかぎり， それよりも小さい 2 のべき乗を全部足しても 2ⁿ には及ばないことを意味している． 逆に言うと， 2ⁿ 以上の数を作るには， n 以上の指数の 2 のべき乗を少なくとも 1 つは 使う必要があるということになる． つまり， 2 進法で m を表したときに， n 番目よりも左（ n 番目も含む）に 1 がなければ， m は 2ⁿ よりも小さいのである．

　ここまでわかれば， m の 2 進数表現を利用して， 上で述べたプロセスを次のように書き換えることができる．

　 n 段のハノイの塔を棒 1 から棒 2 へ移動する場合， 移動元，移動先，待避場所に対応して， i = 1 , j = 2 , k = 3 とおく． ドイモイ君の言葉を思い出せば， i が物の理， j が人の理， k が第三の理に対応することになる． さらに，注目する板の番号を表す変数を l とする． 一番大きな板 n から小さい板へと位置を確定していくので， 初めは l = n としておく．

　このような設定のもとで， m の 2 進数表現の l 桁目を見て， そのビット（ 0 または 1 ）に応じて次のように板 l の位置を判定する． それが済んだら， l の値を 1 つ小さくして，次のビットに進む． これを末尾の桁まで繰り返せば，すべての板の位置がわかるのである．

• ビットが 0 の場合．　 板 l は棒 i にある． j と k の値を入れ替える．

• ビットが 1 の場合．　 板 l は棒 j にある． i と k の値を入れ替える．

　ここでは， m = 2^l-1 の場合は m > 2^l-1 の場合と統合されて， ビットが 1 の場合として処理されている． そのため，以前に示したものよりも，さっぱりしたものになっている． なぜこうなるのかは読者自身で考えてほしい．

　こういう言語的な表現はコンピュータでプログラム を作る上では重要だが， 人間の直観力を活かして実行するためには， もう少しビジュアルな表現の方がわかりやすいだろう． そこで，図 7 のような絵を考えよう．

図7. ハノイの塔の解明図 3

　最初に， i , j , k の丸の中に 1 , 2 , 3 と書いて， m の 2 進数表現の左端の桁（ n 桁目）から作業を開始する． そのビットが 0 ならば，板 l は i の丸に書かれている番号の棒にある． この場合は， i の丸を通る軸に関して反転するように， j と k の丸に書かれている数字を入れ替える． 逆に，ビットが 1 ならば，板 l は j の丸に書かれている番号の棒にある． この場合は， i と k の丸に書かれている数字を入れ替える． さらに，注目しているビットを右にずらして，同じことを繰り返す．

　再びドイモイ君の言葉を思い出そう．

「ハノイの塔は物の理から人の理への移行を象徴している． その移行を助けるのが第三の理である．」

「第三の理は時には物の理と交わり， またある時には人の理と交わる．」

　これはこのアルゴリズムの進み方と見事に符合しているではないか． 図の中の i , j , k を物の理，人の理，第三の理に置き換えれば， この符合はさらに明確になるだろう．

図8. ハノイの塔の解明図 4

　これで完璧だ． 手数の 2 進数表現がわかれば， 単純な手順の繰り返しだけで， ハノイの塔の状態を復元できる． これでハノイ氏の問題が完全解決した！

　しかし，どうやってハノイ氏にこの解法を伝えればよいのか？ 今となっては，ハノイ氏の電子メール・アドレスを調べる術はない． それは他のデータで上書きされて，もはや修復不可能である． 残念だが，この完全解決の喜びはハノイ氏には伝えられないのだろうか？

　仮にそうなら仕方があるまい． では，ハノイの塔の実在をほのめかすドイモイ君の手紙には どう対応すべきなのだろうか？ もちろん， 数学者流にハノイの塔修復の問題を定式化して， その解法を解説した手紙を書いてあげればよいではないか．

　しかし，それだけでは何かが足りない気がした． それだけでは，その手紙に込めたドイモイ君の思いに 少しも応えていない． 私はそう直感したが， それ以上の対応の仕方が思い浮かばなかった．

　それにしても，明日は名古屋に出張だった． ノート・パソコンを買うという計画も未遂に終わってしまった． その会合の席上で発表をするための資料もまだ作っていない． さあ，どうする． 当面の問題はその資料作りだ…．

　やむを得ず，私は大学に戻って資料作りをすることにした． そして，その日も施錠された正門を乗り越えて， タクシーを捕まえて家に帰る羽目になってしまった．