１９世紀の数学者リュカの考案したゲームに「ハノイの塔」があります．ハノイの塔とは３本の柱Ａ，Ｂ，Ｃがあり，柱Ａにある何枚かの円盤を１枚ずつ柱Ｂを中継点にして柱Ｃに移動させるものです．ただし，どの柱でも上の円盤の方が小さくなければなりません．

（問）６４枚の円盤があるとき，移し替えが完了するには何回移動しなければならないのか？

　円盤が３枚であるとします．Ａにある３枚をＢに移すにはＣを中継点にしてＢに移動させる．このためには上の２枚をＣに移し，３枚目をＢにもってきた後，Ｃの２枚をＢに移動させる．次に円盤が４枚であるとします．上の三枚がくっついているとして，この３枚をＢに移し，一番下の円盤をＣにもってきて，Ｂの３枚をＣに移せばよい．

　このような再帰的な方法を用いれば円盤が何枚あってもＡからＣに移動させることができるのですが，ｎ枚の円盤を移動させるのに必要な最小回数をａnと書くことにすれば，漸化式

　　ａn＝２ａn-1＋１

で表せることがわかります．いま述べたｎ−１枚がくっついているとして・・・という考え方を小学５年生の息子に説明したところ，彼にも意味が理解できた様子でありました．

　ａnの具体的な値は

　　ａn＋１＝２（ａn-1＋１）

　　ａn-1＋１＝２（ａn-2＋１）

　　・・・・・・・・・・・・・

　　ａ2＋１＝２（ａ1＋１）

より，容易に

　　ａn＝２^n−１

で与えられることがわかりますが，こうして円盤が３枚のとき→４枚のとき→ｎ枚のときに一般化することができます．

（答）６４枚の円盤があるとき，２^64−１回の移動をしなければならない．１秒に１回移動をさせるにしても完了までには５８２０億年かかることになる．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

　形は似ていますが，柱が３本のとき→４本のとき→ｎ本のときに一般化するのはもっと難しい問題になります．４本のときのハノイの塔について

　　一松信「整数と遊ぼう」日本評論社

の面白い記事がでていたので紹介します．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】柱を４本にしたときの手間

　あるとき，一松先生が熱心な中学生のグループから４本のときのハノイの塔について質問を受けたそうです．彼等が実験したところによると，その手間は

　　ｎ　　１　　２　　３　　４　　５　　６　　７　　８　　９　　10

　　ｂ　　１　　３　　５　　９　　13　　17　　25　　33　　41　　49

もちろん２^n−１に比べると桁違いに少ない回数です．

　差分をとってみると

　　２　　２　　４　　４　　４　　８　　８　　８　　８・・・

となって，その先は

　　１６　１６　１６　１６　１６　　３２　３２　３２　３２　３２　３２・・・（２^nがｎ＋１個続く）

　このことから，４本のときのハノイの塔でもやはり枚数ｎの増加とともなって指数関数的に手間が増加することがわかります．ただしその増加が３本のときのハノイの塔（２^n−１）と比べ，桁違いに遅いというわけです．柱をいくら増やしても板の枚数の増加とともに指数関数的に増加します．

　そして，記事の最後に一松先生は「ハノイの塔の柱を１本増やす」という発展問題を考えた中学生に改めて敬意を表していますが，確かにこうした発想をつまらないものとして芽を摘むのは最悪の教育でしょう．私も大学院生のとき，微量元素の分析に現れる曲線は何かと考えて，当時の教授から「つまらないことを考えるな」とどやしつけられたことがあり，そのことを思い出しました．その曲線とはいまにして思えばフォークト関数です．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】ｋ本ハノイの塔問題

　驚くべきことに，ｋ≧４のときのｋ本ハノイの塔問題はいまだ解明されていません．

　　［参］ハノイの塔，「離散数学のすすめ」第１０章，現代数学社

に詳細がありますが，フレイム・スチュワートのアルゴリズムの移動回数Ｍ（ｎ，ｋ）は実験的にｎ＝３０程度まで調べられており，その範囲では実際に最小となることが確認されています．そのため，ＦＳアルゴリズムが最小解を与えると信じられていますが，厳密な証明はされていないのです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝