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

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

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

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

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

【３】ハノイの塔不等式

　ｎ枚の円盤を移動する手数をＴ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（ｎ−１，ｋ−１）

が成り立ちます．

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