問題24-4　（boojam　さん）　　

　【ハノイの塔】

大きさの異なる８枚の円盤と垂直に立った３本の棒、Ａ、Ｂ、Ｃがある。各円盤の中心には棒の太さと同じ大きさの穴が
空いていて、それぞれの棒に突き刺すようにして積みあげることができるようになっている。

最初、８枚の円盤は、一番大きい円盤が一番下、一番小さな円盤が一番上になるように、大きさの順に棒Ａに積まれている。

この時、すべての円盤を棒Ａから棒Ｂに移すことを考える。ただし、円盤の移動は、次の規則にしたがうこと。
　　　　　　　　規則１　円盤は１度に１枚ずつしか移動できない。
　　　　　　　　規則２　大きな円盤は小さな円盤の上には積むことができない。
　　　　　　　　規則３　円盤は任意の棒から棒へ移動できるだけで、その他の場所には移動できない。

《問題４》
　　大きさが異なる８枚の円盤に、同じ大きさのものを１枚ずつ加える。つまり、同じ大きさの円盤が２枚ずつ計１６枚ある。
　　この１６枚の円盤が、大きさの順に棒Ａに積まれている。

　　最初に示した３つの移動規則を使って、棒Ａに大きさの順に積まれたすべての円盤を棒Ｂに移すことを考える。
　　なお、円盤の移動は１枚ずつ。同じ大きさの円盤は重ねることができる。
　　この時、大きさが同じ円盤の積まれ方の順序を区別しなくても良いとすれば、最低でも何回の円盤の移動が必要か？

《詳細解答４》　５１０回。

基本的に、《問題１》と同じ。まず、（ｎ−１）の２倍の数の円盤を棒Ｃに移す。残りの２枚を棒Ｂに移した後、棒Ｃにあるすべての円盤を
棒Ｂに移せば良い。この手順は、一番下にある円盤を動かすための最少手順をとっているので、結果として順序を保存しないで移動
するための最少手順であることが判る。

ここで、ｎ種類の円盤（計ｎ×２枚）を移す最少手順数を A4(n) と表わせば、以下のようになる。

A4(1) = 2
A4(n) = A4(n-1) + 2 + A4(n-1)
= 2 * A4(n-1) + 2 [n > 1]

∴ A4(n) = 2^(n+1) - 2 [n > 0]
= 2 * (2^n - 1)
= 2 * A1(n)

解き方は省略。