問題24-2　（boojam　さん）　　

　【ハノイの塔】

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

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

この時、すべての円盤を棒Ａから棒Ｂに移すことを考える。ただし、円盤の移動は、次の規則にしたがうこと。
　　　　　　　　規則１　円盤は１度に１枚ずつしか移動できない。
　　　　　　　　規則２　大きな円盤は小さな円盤の上には積むことができない。
　　　　　　　　規則３　円盤は任意の棒から棒へ移動できるだけで、その他の場所には移動できない。
《問題２》
　　円盤の移動規則３を、次のように変更する。
　　　　　規則３′　円盤は、棒Ａと棒Ｂの間で直接移動できないこととする。つまり、すべての移動は必ず棒Ｃに移すか、棒Ｃから移す。
　　　　　　　　　　　　棒以外の場所にも移動できない。
　　この時、最初に棒Ａに積まれた８枚の円盤すべてを棒Ｂに移すためには、最低でも何回の円盤の移動が必要か？

《詳細解答２》　６５６０回。

問題１の時と同様に、円盤８を棒Ｂへ移すには、まず、棒Ｃに移動してから、棒Ｂに移動しなければいけない。ここで、棒Ｃに移動する時には、
上の７枚の円盤が棒Ｂに移動しなけばならない。次にこの状態で円盤８を、棒Ｃから棒Ｂに移動するためには、棒Ｂにあった７枚の円盤を棒Ａに
移動さなければならない。７枚の円盤を棒Ａに移動した後、棒Ｃにある円盤８を棒Ｂに移し、棒Ａにある７枚を棒Ｂに移動すれば良い。

ｎ枚の円盤を、棒Ａから棒Ｂへ移動する最少手順の数を、A2(n) と表わすことにすると、上の手順は以下のようになる。

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

ここで、棒Ｂから棒Ａへの円盤の移動手順は、棒Ａから棒Ｂの手順と同じである（対称）。

このようにして、

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

∵　１枚の円盤を棒Ａから棒Ｂに移すには、棒Ａから棒Ｃ、棒Ｃから棒Ｂへの２回の移動が必要。

これを、A2(1) から逆順に計算すると次のようになる。

A2(1) = 1 + 1 = 2
A2(2) = A2(1) + 1 + A2(1) + 1 + A2(1)
= 2 + 1 + 2 + 1 + 2 = 8
A2(3) = A2(2) + 1 + A2(2) + 1 + A2(2)
= 8 + 1 + 8 + 1 + 8 = 26
A2(4) = A2(3) + 1 + A2(3) + 1 + A2(3)
= 26 + 1 + 26 + 1 + 26 = 80
A2(5) = A2(4) + 1 + A2(4) + 1 + A2(4)
= 80 + 1 + 80 + 1 + 80 = 242
A2(6) = A2(5) + 1 + A2(5) + 1 + A2(5)
= 242 + 1 + 242 + 1 + 242 = 728
A2(7) = A2(6) + 1 + A2(6) + 1 + A2(6)
= 728 + 1 + 728 + 1 + 728 = 2186
A2(8) = A2(7) + 1 + A2(7) + 1 + A2(7)
= 2186 + 1 + 2186 + 1 + 2186 = 6560

これが答え。

ちなみに、A2(n) の一般項は、次のようにして求まる。

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

ここで、【式 2-1】の両辺に１を足して変形する。

A2(n) + 1 = 3 * A2(n-1) + 2 + 1
A2(n) + 1 = 3 * A2(n-1) + 3
A2(n) + 1 = 3 * (A2(n-1) + 1)

さらに、

B2(n) = A2(n) + 1　　　とおくと、B2(n) は次のようになる。

B2(1) = A2(1) + 1 = 3
B2(n) = 3 * B2(n-1) [n > 1]

つまり、B2(n) は、初項 3、公比 3 の単純な等比数列だから、

B2(n) = 3^n = A2(n) + 1

∴ A2(n) = 3^n - 1 [n > 0]