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

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

【１】４本ハノイの塔不等式

　３本ハノイの塔の場合，ｎ枚の円盤を移動する手数をＴnとすると，等式

　　Ｔn＝２Ｔn-1＋１</P>

より

　　Ｔn＝２^n−１

を得ることができます．

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

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

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

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

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

が成り立ちます．

［証］Ｙn＝（Ｗn(n+1)/2−１）／２^nとおけば，

　　Ｙn≦Ｙn-1＋１

より

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

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

　一般には

　　Ｗm≦２Ｗm-k＋Ｔk

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

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

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

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

が成り立ちます．

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

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

　驚くべきことに，ｋ≧４のときのｋ本ハノイの塔問題は組み合わせ論的爆発のため，いまだ解明されていません．

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

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