ハノイの塔とは３本の柱Ａ，Ｂ，Ｃがあり，柱Ａにある何枚かの円盤を１枚ずつ柱Ｂを中継点にして柱Ｃに移動させるものですが，柱が３本のとき→４本のとき→ｎ本のときに一般化するのはもっと難しい問題になります．

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

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

　４本のときのハノイの塔について

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

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

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

　　ｎ　　１　　２　　３　　４　　５　　６　　７　　８　　９　　10

　　ｂ　　１　　３　　５　　９　　13　　17　　25　　33　　41　　49

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

　差分をとってみると

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

となって，その先は

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

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

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

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

【２】ハノイの塔不等式

　ｎ枚の円盤を移動する手数をＴnとすると，等式

　　Ｔn＝２Ｔn-1＋１

より，

　　Ｔn＝２^n−１

を得ることができます．

　ハノイの塔の棒が３本から４本の場合に拡張して，ｎ枚の円盤を移動する手数をＷnとすると，

　　Ｗn＝３^n−１　　　（これはＷn＝３Ｗn-1＋２の解）

になるのではなく，不等式

　　Ｗn(n+1)/2≦２Ｗn(n-1)/2＋Ｔn

　　Ｗn(n+1)/2≦２^n（ｎ−１）＋１

が成り立ちます．

　一般には

　　Ｗm≦２Ｗm-k＋Ｔk

が成り立ちますが，この不等式はまず頂上のｍ−ｋ枚を移動し，次に３本の棒だけで底のｋ枚を移動し，最後に再び頂上のｍ−ｋ枚を移動することに対応しています．問題の不等式はｍ＝ｎ（ｎ＋１）／２の場合に右辺を最小化する唯一のｋの値に依存しています．

　ｋ本の棒の場合の最小手数をＸkで表します（Ｘ3＝Ｔ，Ｘ4＝Ｗ）．このとき，不等式

　　Ｘk（（ｎ＋１，ｋ））≦２Ｘk（（ｎ，ｋ））＋Ｘk-1（（ｎ，ｋ−１））

　　Ｘk（（ｎ，ｋ））≦２^n+1-k（ｎ−１，ｋ−１）

が成り立ちます．

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

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

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

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

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

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