私たち数学者は，白黒がはっきりしないときの対処の方法を持っている． それは，真偽のわからない内容をとりあえず仮定して， それからわかることを列挙していくというやり方だ． そして，その列挙された事柄どうしの中に，矛盾がないかどうかをチェックする． 矛盾が発見されなければ，さらに議論を続ける必要があるが， もし矛盾があれば，初めに仮定した内容がおかしいと断定できるのである． なぜなら，その仮定以外には，何もおかしなことをしていないからである． 数学では，こういう論証の仕方を背理法 という．

　 「じゃあ，ハノイの塔が実在して，ドイモイ君が言っていたような 儀式が毎日繰り返されていたとすると，何がわかるのだろうか？」

　この問いに対して，珍しく田沼君が即答した．

　 「そうですねぇ．その儀式をやっている坊さんたちは， えらく頭がいいですね．」

　私も中本君も，この予期せぬ彼の反応に大笑いした．

　 「そんなぁ．笑わなくたっていいじゃないですか． だって， 64 段のハノイの塔でしょう． その答えを知っているなんて，よっぽど頭がよくないとできませんよ． ぼくなんか， 4 段のハノイの塔にだって，手を焼いているのですから…．」

　なるほど． 確かにそのとおりだ． 毎日 1 つずつ板を動かしている坊さんたちは， 少なくとも 64 段のハノイの塔の解法を知っていることになるのではないか．

　 「でも，待ってくださいよ．」

　と中本君が切り出した．

　 「確かに，ハノイの塔の坊さんたちが頭がよいことは否定できないにしても， 坊さんたちの寿命はせいぜい 100 才でしょう． となると， 彼らは，世代交代をして，その儀式を続けていることになりますよ．」

　 「なるほど．」

　 「だったら，世代が交代するたびに， その知識を伝授していかなければならないでしょう． それは可能なのでしょか？」

　 「確かにそうだね．田沼，どう思う．」

　 「えー．そう急に振られても，ぼくにはわかりませんよ． でも，ハノイの塔の答えを出すのって，そんなに難しいんですか？ だって，確か先生は…．」

　田沼君は何かを必死に思い出そうと， 目で中空を探していた． その視線の先を捕まえるように，彼の目の前に私の手を差し伸ばすと， 彼はやっと答えを見つけた．

　 「そうそう．“情報科学概論”ですよ． 先生がやってた情報科学概論っていう授業で， ハノイの塔の話をしたじゃないですか．」

　 「確かにやった．よく覚えていたね．」

　 「そうですよ．うろ覚えですけど， 先生はハノイの塔の解答を出力するプログラムだといって， ずいぶん簡単なプログラムを OHP で見せてくれましたよ．」

　 「そうだね．あれは再帰的プログラミングの説明をするための例として， ハノイの塔を説明したのだった．」

　 「そうそう．人間が答えを知らなくたって， その問題の構造をちゃんと理解してプログラミングすると， コンピュータが答えを出してくれるんだって言ってましたよね．」

　 「これはたまげた．よくそこまで覚えているねぇ」

　 「てへへ．けっこう印象的だったので…．」

　誉められることに不慣れな田沼君は少々照れくさそうだった．

　確かに，その「情報科学概論」 という講義の中で， 再帰呼び出し のできるプログラミング言語 とそれができないプログラミング言語では， 記述できる世界が大きく違うという話をしたことがあった． そのとき，ありきたりな n の階乗 n! の計算に加えて， ハノイの塔の問題の再帰的な構造について解説した．

　 n! の値は (n-1)! の値に n を掛ければ求められる． つまり， n! は n! = (n-1)! × n という等式で定義できるが， 階乗の定義の中に階乗自身が入っている． こういう自分自身を参照している定義の仕方を 再帰的定義というのである． しかし， n! の値は 1 × 2 × 3 × … × n と 順にかけ算を実行すれば計算できるから， 階乗の計算は本質的な再帰ではない． 一方， ハノイの塔の解法の再帰的定義は本質的なものであることを強調して， その C 言語によるプログラムの仕方を解説したのだった．

 1:   #include 
 2:   void move(i,j)
 3:   int  i,j;
 4:   {
 5:        printf("棒 %d から棒 %d へ
              板を１つ移動する．\n",i,j);
 6:   }
 7:
 8:   void hanoi(n,i,j)
 9:   int  n,i,j;
10:   {
11:        int  k;
12:        k = 6 - i - j;
13:        if(n == 1)
14:             move(i,j);
15:        else
16:        {
17:             hanoi(n-1,i,k);
18:             move(i,j);
19:             hanoi(n-1,k,j);
20:        }
21:   }
22:
23:   void main(argc, argv)
24:   int  argc;
25:   char *argv[];
26:   {
27:        if(argc < 1)
28:                exit(0);
29:        hanoi(atoi(argv[1]),1,2);
30:   }

リスト 1 : 　ハノイの塔の解法プログラム

　参考までに C 言語で書いたソース（リスト 1 ）を示しておく． これを打ち込んで， hanoi.c というファイル名で保存してコンパイルすれば， ハノイの塔の解法を標準出力（ディスプレー）に出力してくれる プログラムができ上がる． 例えば， 4 段のハノイの塔の解法を見たければ， コマンド・ラインから

hanoi 4

　そのプログラミングの仕方は， ハノイの塔の手数 a_n を求めたときの考え方と基本的には同じである． このプログラムのすべてを理解する必要はないが， 本質的な部分は， 8 行目から 21 行目である． そこでは， n 段のハノイの塔を棒 i から棒 j に移動する手順を 出力してくれる関数 hanoi(n,i,j) が定義されている． 12 行目の k = 6 - i - j は多少技巧的であるが， 1 , 2 , 3 のうちで， i でも j でもない値を求めて k に代入している． i + j + k = 1 + 2 + 3 = 6 となっていることを考えれば， その仕組みがわかるだろう．

　細かいところを無視すれば，基本的には英語で書いてあるようなものだから， hanoi(n,i,j) の定義は次のように読める． もし n = 1 ならば，板は 1 つしかないのだから， それを棒 i から棒 j に移動するだけでよい． そうでなければ，板 n を無視した n-1 段のハノイの塔を棒 i から棒 k に移動して， 棒 i にある板 n を棒 j に移動して， 棒 k にどけておいた n-1 段のハノイの塔を棒 j に乗せて終了．

　 「確かに，プログラミンは簡単だけれど， その再帰的な定義に対応して， 逐次実行してくれるコンピュータがあればこそ， 人間がその答えを明示的に知らなくても， その答えが出力できるんだぞ．」

　私が照れている田沼君をたしなめると， それに加えて，

　 「そうだそうだ．今ならともかく， 何千年か何万年かはわからないけれど， ハノイの塔の移動を始めたときに， コンピュータなんてあるわけないじゃないか！」

　と中本君が言った．

　 「うー．でも先生． その大昔に，コンピュータのように頭のいい大天才の聖者がいて， その人がその答えを解いちゃったりして…．」

　と田沼君が言うやいなや， 中本君は直ちに迎撃した．

　 「ばっかだなー． 64 段のハノイの塔が何手掛かるかわかっているのか！」

　 「そ，そりゃー，わかってますよ．えと， 2⁶⁴-1 手でしょう．」

　 「そうだよ．でもなぁ， 2⁶⁴-1 というのはとんでもなく大きい数なんだぞ． この前，先生と計算してみたら， 1/100 秒で 1 手動かしたって， 58 億年掛かるんだぞ！」

　 「ええー，そんなに時間が掛かるんですか！」

　 「そうだよ．田沼説が正しいとしても， その答えを書き出すだけだって，何十億年も掛かってしまうんだ． その大天才の聖者だって，生身の人間なんだから， そんなに生きていられないだろう．」

　 「そうだったんですかぁ． じゃあ，やっぱりハノイの塔は存在しないんでしょうか…．」

　こう考えていくと， ハノイの塔の存在を仮定すると， 実現不可能な事態に陥ってしまいそうである． ということは， 背理法によって，ハノイの塔の存在は否定されてしまうのだろうか？

　私は念のために 2 人に次の問いを発した．

　 「ハノイの塔の解法を意味のある時間内にすべて書き下す方法がないので， ハノイの塔の存在を否定してよいのか？」

　一同，しばらく沈黙． それぞれが思案する． そして，最初に口火を切ったのは，中本君だった．

　 「ハノイの塔の存在の是非に決着がつけられるわけではないのですが， その理由だけで，存在は否定できないと思います．」

　 「というと？」

　 「例えば，最初にすべての答えがわかっていなくても， だんだんパズルを解きつつ，塔を移動していくと考えたらどうでしょう．」

　 「うーん．ですねぇ．」

　田沼君は安易に同意した． 私は，少し間をおいて，

　 「しかし，そのパズルの答えを考えている坊さんだって， いずれ死んでしまうだろう．」

　と言った．

　 「パズルの解答者が世代交代していくとなると…．」

　慎重に議論を進めようとする中本君の言葉を遮って， 私は続けた．

　 「ハノイの塔の構造は“再帰的”というだけあって， 前にやったことを覚えておいて，そこに帰らないと処理ができない問題なんだぞ． 世代交代するにしたって， 子孫に伝えるべき内容がどんどん増えていって， いずれ破綻していまうはずだ．」

　 「うーん．ですねぇ」

　再び沈黙． しかし，ハノイの塔の存在を否定するよりも， それを肯定するアイディアを誰もが模索しているようだった． そして，やはり中本君が新たな観点を提供した．

　 「思いつきでしかありませんが，与えられたハノイの塔の状態を見たときに， どの板を動かせばよいのか判定できたりしないでしょうか？」

　 「うーん．なるほど」

　田沼君は，また安易に同意したと非難されるものと思ったらしく， そこで言葉を止めて，私たちの表情をうかがうように顔を動かした． その動きに強調されて，彼の耳は大きく左右に広がって見えた．

　 「でも，与えられた状態で着手可能な手は 3 つしか考えられないよ．」

　 「どうしてですか？」

　 「それは簡単さ． 動かせるのはそれぞれの棒に刺さっている一番上の板だけだろう． その板の大きさはすべて違うのだから， 一番小さい板は他の 2 枚の上に乗せられるし， 中くらいの板は一番大きい板の上だけに乗せられる． 大きいのはその状態では動かせないよね．」

　 「ですねぇ．」

　再び顔を振る田沼君． それを見て，中本君が笑いながら言った．

　 「確かにそうですね． そもそも，その一番小さい板というのは，実際に一番小さい板ですよね．」

　 「そうだよ． そいつは，最初の状態で一番天辺に乗っているやつさ． 中くらいのと大きいのがどの板になるかは状況によっていろいろだけれど， そいつだけはいつも同じものさ．」

　 「なるほど． 要するに，まず，これから動く板が中なのか，小なのかが問題になって， それが小ならば，さらに 2 つの可能性がある というわけですね．」

　 「そういうこと． その 3 つの可能性のうち， どれかが正解で，残りの 2 つが無駄な手というわけさ．」

　 「うーん． その正解を判定するうまい方法はないんでしょうか？」

　中本君はそういうと，計算用紙入れ箱から紙を 1 枚抜き出し， 幸いそこに転がっていた赤のボールペンを手に， いくつかの絵を書いた． 1 つは与えられた状態に対応した大中小の 3 つの円からなる絵で， その他はそれから着手可能な 3 手のどれかを実行した後の状態に対応していた．

　 「ううむ．この程度の情報だけだと， どれが正解なのか判断できない気がしますね． やはり，何手か前まで遡らないと難しいみたいです．」

　また，それぞれが独自に考えるモードに入ろうと私と中本君が構えていると， 田沼君がなかなかよいアイディアを出した．

　 「じゃあ，先生，先生． 授業のときにやったハノイの塔のプログラムを作って， 具体的に答えを出して，それを眺めて考えてみましょうよ．」

　 「おお，そうじゃ，そうじゃ． ついつい抽象的に考える癖が付いてしまっていて， そういう基本的なことを忘れていた．」

　 「ですね．」

　中本君は田沼君の口癖を真似して，私に同意した．

　 「じゃ，田沼．おまえがプログラムを作れよ．」

　 「えー．そんなぁ．ぼくなんか，作れませんよ． 先生がやってください．お願いします．」

　確かにプログラムは私がすべきだった． この 2 人には数学は仕込んだが， コンピュータは数式混じりの論文を書くために使う LaTeX のことしか教えていない． 就職のときに有利だからコンピュータの勉強をしておけと日頃口にしているものの， きちんと指導しておかなかったことが悔やまれる．

　この機会にプログラムを仕込んでもよかったのだが， 単にキーボードを打つのさえ，私の方が圧倒的に早いので， 私がパソコンの前に座った．

　そして，上で示したプログラムをサラサラと打ち込んで，コンパイル，実行． 画面に 3 段のハノイの塔の答えが流れた．

　 「さすが先生．」

　お調子者の田沼君が私を褒める． 続いて中本君．

　 「でも，先生．これだと何番の板が移動したのかわかりませんね． 動いた板の番号も画面に出せないんですか？」

　 「それは簡単さ．この move を改造すればいいんだ． ここをこう直して，これをこう変えればいいはず…．」

 2:   void move(n,i,j)
 3:   int  n,i,j;
 4:   {
 5:        printf("棒 %d から棒 %d へ
              板 %d を移動する．\n",i,j,n);
 6:   }

リスト 2 : 　moveの改造

　まず，{\tt move(i,j)} が定義されている 2 行目から 6 行目までをリスト 2 のように 改造して， 14 行目と 18 行目の {\tt move(i,j)} を それぞれ {\tt move(1,i,j)} と {\tt move(n,i,j)} に変えた． その詳細は示さないが， さらに何手目かわかるような工夫を施して，コンパイル． コマンド・ラインから hanoi 3 と打ち込むと， 次のような出力が画面に現れた． それを見て， 2 人から歓声が上がった．

1 : 棒 1 から棒 2 へ板 1 を移動する．
2 : 棒 1 から棒 3 へ板 2 を移動する．
3 : 棒 2 から棒 3 へ板 1 を移動する．
4 : 棒 1 から棒 2 へ板 3 を移動する．
5 : 棒 3 から棒 1 へ板 1 を移動する．
6 : 棒 3 から棒 2 へ板 2 を移動する．
7 : 棒 1 から棒 2 へ板 1 を移動する．

　 「ですねぇ」

　漠然と見ていても何も見えてこないので， 何か観点を設けるべきだと私が言うと， それに応えて，中本君が 2 のべき乗のところを注目したらどうかと言い出した．

　 「だって，ハノイの塔の議論って，いつも 2 のべき乗に関係してますもんね．」

　 「ですねぇ．ということは， 1 手目が板 1 で， 2 手目が板 2 で， 4 手目が板 3 で…．」

　と，自分でデータを読み上げているうちに， 田沼君はあることに気がついた．

　 「あれ？ 先生，これって，板 n は 2^n-1 手目で動いていませんか？」

　 「あ，本当だ．田沼さん，偉い！」

　 「うーん．」

　また照れる田沼君．

　 「じゃあ，田沼説が正しいかどうか， 4 段のハノイの塔でも確かめてみよう．」

　そういって，私はコマンド・ラインに

hanoi 4

　 「じゃあ， 2 のべき乗じゃない手数のときはどういう関係にあるんでしょうか？」

　と中本君が切り出すと， 田沼君が控えめに，

　 「先生．これって，ひょっとして 2 進法 と関係があるんじゃないですか？」

　 「へ？」

　田沼君のその発想に私は少し驚いた．

　 「どうして，そんなことに気づくわけ？」

　 「だって，先生，自分で『爽快！ 2¹⁰⁰ 三話』の中で， 2 のべき乗と 2 進数の関係を書いてたじゃないですか．」

　そう言われてみればそうだった． 確かにその本の中で， 2 進法やら 5 進法やらの話に触れ， 通常の 10 進法の世界でものを考えているだけではいけないと 訴えていたのだった． （詳細は拙著参照．）

　 「でかしたぞ，田沼さん．じゃあ，手数の部分を 2 進法で表現するように プログラムを改造してみよう．」

　そう言って，私はプログラムの改造に取り掛かった． 数を 2 進数で表示する関数を作るのに多少時間が掛かったが， めでたくプログラムの完成． そして， 4 段のハノイの塔の答えを出力させてみると， 次のとおりである． それを見て，あなたは何を見い出せるだろうか？

0001 : 棒 1 から棒 3 へ板 1 を移動する．
0010 : 棒 1 から棒 2 へ板 2 を移動する．
0011 : 棒 3 から棒 2 へ板 1 を移動する．
0100 : 棒 1 から棒 3 へ板 3 を移動する．
0101 : 棒 2 から棒 1 へ板 1 を移動する．
0110 : 棒 2 から棒 3 へ板 2 を移動する．
0111 : 棒 1 から棒 3 へ板 1 を移動する．
1000 : 棒 1 から棒 2 へ板 4 を移動する．
1001 : 棒 3 から棒 2 へ板 1 を移動する．
1010 : 棒 3 から棒 1 へ板 2 を移動する．
1011 : 棒 2 から棒 1 へ板 1 を移動する．
1100 : 棒 3 から棒 2 へ板 3 を移動する．
1101 : 棒 1 から棒 3 へ板 1 を移動する．
1110 : 棒 1 から棒 2 へ板 2 を移動する．
1111 : 棒 3 から棒 2 へ板 1 を移動する．

　私たち 3 人は同時に声を上げた．

　 「これって…」

　そうである． 手数を表す 2 進数を右から見ていって， 初めて 1 が現れるまで桁数を数えていくと， その数が移動する板の番号になっているのである． 例えば， 1 手目は右から 1 桁目が 1 だから，板 1 が動く． 2 手目は 2 桁目が 1 だから，板 2 が動く． 3 手目はまた 1 桁目が 1 になるので，板 1 が動く． 4 手目は 3 桁目が 1 なので，板 3 が動く． 以下も同様である．

　これは偶然の一致なのだろうか？ いや，そうではない． この法則は実際に成り立つことなのである．

　 「やりましたね，先生．すぐには証明は思いつきませんが， これって正解ですね．」

　 「そんな感じだね．」

　 「よーし．明日までに証明を考えてくるぞぉ」

　中本君はかなり興奮している様子だった． 数学的には証明が付けられるまで その現象を信じるわけにはいかないが， これは大きな前進である．

　つまり，与えられた手数のときに，動かす板を指定する方法がわかったのである． 現段階では， m 手目に板全体がどういう状態に なっているかまでは明らかではないから， ハノイ氏の問題が完全に解決したわけではない． しかし， これで，ドイモイ君の手紙がほのめかしているハノイの塔の存在が 完全には否定しきれないものになってきた．

　 「先生．でもですねぇ，まだ問題が残ってますよ．」

　田沼君がすまなそうに言った．

　 「そのぉ，動かす板はわかりましたけれど， その板をどこに動かせばいいかがわからないと…．」

　そう言い終わるか終わらないかのうちに， 田沼君自身がその疑問の答えを発見してくれた．

　 「あー！」

　 「どうしたんだ．」

　 「これこれ．板 1 の動きなんですけれど…．」

　そう言いながら， 田沼君はパソコンの画面に指をやった． そして，先ほどの 4 段のハノイの塔の出力をたどっていった．

　 「板 1 は 1 回おきに動きますよねぇ． その動きを追跡してみると，ほら，

棒 1 → 棒 3 → 棒 2 → 棒 1 → 棒 3 → 棒 2

　 「ほんとだ． 田沼は今日は冴えているなぁ．」

　 「てへへ．」

　 「なるほど． 田沼の言っているように， 板 1 の動きが 1 → 3 → 2 を繰り返すのだとすると， 問題はすべて解決するな．」

　 「そうですね．板 1 というは一番小さい板のことだから， 田沼の法則を使えば，さっき問題にしていた 正解と無駄な手が区別できますね．」

　 「ですねぇ．」

　私は念のため 5 段のハノイの塔の答えをパソコンの画面に表示させた． 田沼君はその 31 行の手順を見つめて少々がっかりした様子だった．

　 「あれぇ． 1 → 3 → 2 になってない…．」

　それを見て，中本君が励ますように言った．

　 「田沼，そうがっかりするなよ． よく見てみろ． 今度は 1 → 2 → 3 が繰り返しているじゃないか．」

　 「ですねぇ．」

　 「といことは，ハノイの塔の段数が偶数か奇数かで， 板 1 の動き方が逆になるじゃないでしょうか？」

　 「ですねぇ，ですねぇ．」

　田沼君がまたはしゃぎだす．

　 「それじゃ， 6 段のハノイの塔の答えも表示してみよう．」

　再び私がキーボードを叩いた． 画面には， 6 段のハノイの塔の答えが流れていく． 64 行の出力はパソコンの画面には納まらず， 一部が消えてしまったが， 見えている範囲では 「 1 → 3 → 2 」 の法則が成り立っていた．

　 「やりー！」

　私たち 3 人は口を揃えて叫んだ． この法則もまだ証明されてはいない． しかし，この実験的な事実はやはり偶然とは思えない．

　 「きっと田沼の法則も証明できますよね．」

　 「だろうね．」

　 「じゃ，田沼．おまえが明日までに証明してこいよ．」

　 「え，えー！」

　いずれにせよ， 今日の発見は大きな前進だ． 日数の 2 進数表現さえ子孫に伝えていけば， 世代交代をして 64 段のハノイの塔の移動を続けていけるのだ！

　 64 段のハノイの塔の移動の手数の 2⁶⁴-1 がどんなに大きな値であろうとも， それは高々 64 桁の 2 進数で表現できる数である． だから，例えば玉か何かを 64 個並べて 2 進数を表現することにすれば， コンピュータなどなくても， 今日が儀式を始めてから何日目なのかを記録しておくことができる． そして，その玉を右から数えていって， 1 を表す玉が現れるところを探す． そのときに数えた数と同じ番号の板が今日移動すべき板なのである． そして，その板が一番小さいものならば， 「 1 → 3 → 2 」 の法則に従って移動先を決定し， そうでなければ，それを動かせるところに動かせばよい．

　これで，ハノイの塔の儀式が何千年，何万年と継続されていたとしても， 何の不思議もなくなった．