問題24　（boojam　さん）　　

　【ハノイの塔】

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

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

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

《問題１》
　　最初に棒Ａに積まれた８枚の円盤すべてを棒Ｂに移すには、最低でも何回の円盤の移動が必要か？　

《詳細解答１》　　　255回

円盤を小さいものから順に、円盤１、円盤２、・・・、円盤８と名前を付ける。

最初棒Ａの一番下に詰まれている一番大きな円盤８を、棒Ｂに移動するためには、上の７枚の円盤すべてを棒Ｃに移動する必要がある。
その後、棒Ｃにある７枚の円盤を棒Ｂへ移せば良い。次に、上の７枚を考える。この中の一番大きな円盤７を棒Ｃに移動するには、
上の６枚の円盤を棒Ｂに移動させる必要がある。

つまり、A1(n) を、ｎ枚の円盤をある棒からある棒へ移動させる最少手順の数とすると、

A1(8) = A1(7) + 1 + A1(7)
: : :
: : → 棒Ｃにある７枚の円盤を棒Ｂに移動する
: → 棒Ａにある円盤８を棒Ｂに移動する
→ 棒Ａにある上の円盤７枚を棒Ｃに移動する

同様に、

A1(7) = A1(6) + 1 + A1(6)
A1(6) = A1(5) + 1 + A1(5)
A1(5) = A1(4) + 1 + A1(4)
A1(4) = A1(3) + 1 + A1(3)
A1(3) = A1(2) + 1 + A1(2)
A1(2) = A1(1) + 1 + A1(1)
A1(1) = 1

∵ 円盤が１枚だけなら、直接、元の棒から目的の棒へ移動すれば良いから。

それぞれ、逆順に計算していくと次のようになる。

A1(1) = 1
A1(2) = A1(1) + 1 + A1(1)
= 1 + 1 + 1 = 3
A1(3) = A1(2) + 1 + A1(2)
= 3 + 1 + 3 = 7
A1(4) = A1(3) + 1 + A1(3)
= 7 + 1 + 7 = 15
A1(5) = A1(4) + 1 + A1(4)
= 15 + 1 + 15 = 31
A1(6) = A1(5) + 1 + A1(5)
= 31 + 1 + 31 = 63
A1(7) = A1(6) + 1 + A1(6)
= 63 + 1 + 63 = 127
A1(8) = A1(7) + 1 + A1(7)
= 127 + 1 + 127 = 255

これが答え。

ちなみに、一般化すると、次のようになる。

A1(1) = 1
A1(n) = 2 * A1(n-1) + 1 [n > 1] … 【式 1-1】

これを解くには、２番目の式の両辺に１を足して、

A1(n) + 1 = 2 * A1(n-1) + 1 + 1

これを変形して、

A1(n) + 1 = 2 * A1(n-1) + 2
A1(n) + 1 = 2 * (A1(n-1) + 1) … 【式 1-2】

ここで、

B1(n) = A1(n) + 1

とおくと、上の【式 1-2】は、次のように表わされる。

B1(n) = 2 * B1(n-1)

また、

B1(1) = A1(1) + 1 = 1 + 1 = 2

だから、B1(n) は、初項 2、公比 2 の単純な等比数列。

B1(n) = 2^n = A(n) + 1 [n > 0]

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