問題24-5　（boojam　さん）　　

　【ハノイの塔】

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

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

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

《問題５》
　　問題４と同様に、棒Ａに大きさの順に積まれた大きさの異なる８枚の円盤２組計１６枚の円盤すべてを、最初の３つの移動規則を使って、
　　棒Ｂに移すことを考える。
　　この時、棒Ｂにすべての円盤が移動できた際に、大きさの同じ円盤の順序が最初棒Ａに積まれていた順序となるようにするには、
　　最低でも何回の円盤の移動が必要か？
　　なお、順序を保証するのはすべての円盤が棒Ｂに移動し終わった時で良く、移動の手順の途中で順序を保証する必要はない。

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

まず、《問題４》を振り返って、棒Ｂに円盤をすべて移動し終わった時の円盤の重なる順序を考えてみる。まず、一番下にある２枚の円盤の
順番が入れ替わっていることは直ぐに判る。それ以外の円盤については、必ず偶数回移動したことになるので、順番が保存されていることが判る。
つまり、一番下にある２枚の円盤の順序は入れ替わっているが、残りの円盤の重なる順序は保存されている。

この結果から、単純に考えてみる。まず、すべての円盤を一旦棒Ｃに移する。その後、それらを棒Ｂに移動する。すると、すべての円盤の
重なる順序は保存されることになる。

この手順だと、円盤が２枚、つまり、同じ大きさの円盤が２枚の時、上の手順だと計４回の移動が必要になる。しかしながら、実際には、３回の移動で済む。

２枚の円盤を、円盤ｕと円盤ｖとする。最初、円盤ｕが上にあるものとする。まず、円盤ｕを棒Ｃに移す。次に、円盤ｖを棒Ｂに移す。最後に、棒Ｃにある
円盤ｕを棒Ｂに移す。重なる順番を保存したまま、３回の移動できたことになる。

そこで、本当の最少手順を考える。

まず、（ｎ−１）の２倍の数の円盤を順番を関係なく棒Ｂに移す。次に、棒Ａに残っている２枚を、順番に関係なく棒Ｃに移す。さらに、棒Ｂにあるすべて
の円盤を順番に関係なく棒Ａに移す。この時、棒Ａでは元の順番が保存されているはず。そして、棒Ｃにある２枚の円盤を順番に関係なく棒Ｂに移す。
この時、棒Ｂでは元の順番が保存されているはず。そこで、棒Ａにある円盤すべてを、順番を保存して棒Ｂに移す。

ここで、ｎ種類２組みの円盤を元の順番を保存して移動する手順の最少手順数を A5(n) として、問題４の結果を利用すれば、この手順は次のように表わせる。

A5(n) = A4(n-1) + 2 + A4(n-1) + 2 + A5(n-1)
= A5(n-1) + 2 * A4(n-1) + 4
= A5(n-1) + 2 * (2^n - 2) + 4
= A5(n-1) + 2^(n+1)

これを、

A5(1) = 3

として一般項を求めると（解き方省略）、

A5(n) = 2^(n+2) - 5

となる。

念のため、もう１つ別の手順を考えてみる。

最初の手順は同じく、（ｎ−１）の２倍の数の円盤を順番を関係なく棒Ｂに移す。次に、棒Ａの残り２枚のうち１枚を棒Ｃに移す。さらに、棒Ｂにあるすべての
円盤を順番に関係なく棒Ｃに移す。この時、棒Ｃでは元の順序が保存されいるはず。その後、棒Ａに残っている最後の１枚の円盤を棒Ｂに移す。
そして、棒Ｃにある（ｎ−１）の２倍の数の円盤を順番を関係なく棒Ａに移す。その後、棒Ｃに残った最大の円盤の残りの１枚を棒Ｂに移す。
最後に、棒Ａにあるすべての円盤を棒Ｂに移す。これで順番を保存したまま、すべての円盤を移せたことになる。

この手順を、B5(n) とすると、

B5(n) = A4(n-1) + 1 + A4(n-1) + 1 + A4(n-1) + 1 + A4(n-1)
= 4 * A4(n-1) + 3
= 4 * (2^n - 2) + 3
= 4 * 2^n - 4 * 2 + 3
= 2^(n+2) - 8 + 3
= 2^(n+2) - 5 [n > 0]

となり、先に求めた A5(n) と同じ。

ちなみに、この B5(n) の手順で、順序を保存して移動を行なうと、手順が増えることは明らか。また、これらの手順 A5(n) と B5(n) も、一番下にある
円盤を動かすための最少手順をとっているので、これらが順序を保存して移動するための最小手順であることが判る。

蛇足ながら、

A5(n) = 2^(n+2) - 5
= 2^(n+2) - 4 - 1
= 2 * 2^(n+1) - 2 * 2 - 1
= 2 * (2^(n+1) - 2) - 1
= 2 * A4(n) - 1

となっている。