問題24-6　（boojam　さん）　　

　【ハノイの塔】

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

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

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

《問題６》
　　移動の際に使用できる棒（これを棒Ｄとする）を、もう１本追加する。つまり、合計４本の棒がある。
　　この時、棒Ａに積まれた８枚の円盤すべてを最初の３つの移動規則を使用して、棒Ｂに移動するためには、最低でも何回の円盤の移動が必要か？　　

《詳細解答６》　３３回

この問題は、一筋縄ではいかない。ｎ枚の円盤に対して、棒が４本あるときの最少手順を A6(n) と表わす。円盤の数が、４枚より少ないときの
最少手順はほぼ明らか（最初に、一番大きな円盤以外を、棒Ｂ以外に移せば良い）。

A6(1) = 1
A6(2) = 3
A6(3) = 5

実際のところ、この問題を一般化したｎ枚の円盤の時の最少手順数の求め方については、この問題が提起されてから１００年あまり経った現在においても、
未だ未解決問題となっている。

これでは余りにも不親切なので、円盤の動かした方を少し考えてみる。直感的には、次のようにすれば、最少の手順ですべての円盤を移すことができそう
だと判る。

まず最初に、４本の棒のすべてを使って、何枚かの円盤を棒Ｄに移す。残った円盤を、棒Ｄを除いた３本を使って棒Ｂに移す。その後、棒Ｄにあるすべての
円盤を、４本の棒すべてを使って棒Ｂに移せば良い。あるいは、初めから３本の棒だけを使って、すべての円盤を移動する。これらのなかで、最少のものが
答えになりそうだ。

これが正しいとすれば、最少手順数 A6(n) は、A6(0) = 0 として（動かす円盤がないから、移動の手順もゼロ回）、次のように表わせる。

A6(n) = min { A6(m) + A1(n-m) + A6(m) | n > m >= 0 }
= min { 2 * A6(m) + A1(n-m) | n > m >= 0 }

ここで、「min { ... }」は、集合要素「{ ... }」の中の最小値を表すものとする。

これを元に、４枚の円盤で考えてみる。すると、A6(4) の値は、次のいずれかの最少のもの。

2 * A6(3) + A1(1) = 2 * 5 + 1 = 11
2 * A6(2) + A1(2) = 2 * 3 + 3 = 9
2 * A6(1) + A1(3) = 2 * 1 + 7 = 9
2 * A6(0) + A1(4) = 2 * 0 + 15 = 15

ということで、

A6(4) = 9

となることが判る。

同様にして、円盤が、５枚、６枚、７枚、８枚で計算する。

A6(5) = min {
2 * A6(4) + A1(1) = 2 * 9 + 1 = 19
2 * A6(3) + A1(2) = 2 * 5 + 3 = 13
2 * A6(2) + A1(3) = 2 * 3 + 7 = 13
2 * A6(1) + A1(4) = 2 * 1 + 15 = 17
2 * A6(0) + A1(5) = 2 * 0 + 31 = 31
}
= 13

A6(6) = min {
2 * A6(5) + A1(1) = 2 * 13 + 1 = 27
2 * A6(4) + A1(2) = 2 * 9 + 3 = 21
2 * A6(3) + A1(3) = 2 * 5 + 7 = 17
2 * A6(2) + A1(4) = 2 * 3 + 15 = 21
2 * A6(1) + A1(5) = 2 * 1 + 31 = 33
2 * A6(0) + A1(6) = 2 * 0 + 63 = 63
}
= 17

A6(7) = min {
2 * A6(6) + A1(1) = 2 * 17 + 1 = 35
2 * A6(5) + A1(2) = 2 * 13 + 3 = 29
2 * A6(4) + A1(3) = 2 * 9 + 7 = 25
2 * A6(3) + A1(4) = 2 * 5 + 15 = 25
2 * A6(2) + A1(5) = 2 * 3 + 31 = 37
2 * A6(1) + A1(6) = 2 * 1 + 63 = 65
2 * A6(0) + A1(7) = 2 * 0 + 127 = 127
}
= 25

A6(8) = min {
2 * A6(7) + A1(1) = 2 * 25 + 1 = 51
2 * A6(6) + A1(2) = 2 * 17 + 3 = 37
2 * A6(5) + A1(3) = 2 * 13 + 7 = 33
2 * A6(4) + A1(4) = 2 * 9 + 15 = 33
2 * A6(3) + A1(5) = 2 * 5 + 31 = 41
2 * A6(2) + A1(6) = 2 * 3 + 63 = 69
2 * A6(1) + A1(7) = 2 * 1 + 127 = 129
2 * A6(0) + A1(8) = 2 * 0 + 255 = 255
}
= 33

これが答え。