問題24-3 （boojam さん）
【ハノイの塔】
大きさの異なる８枚の円盤と垂直に立った３本の棒、Ａ、Ｂ、Ｃがある。各円盤の中心には棒の太さと同じ大きさの穴が
空いていて、それぞれの棒に突き刺すようにして積みあげることができるようになっている。
最初、８枚の円盤は、一番大きい円盤が一番下、一番小さな円盤が一番上になるように、大きさの順に棒Ａに積まれている。
この時、すべての円盤を棒Ａから棒Ｂに移すことを考える。ただし、円盤の移動は、次の規則にしたがうこと。
規則１ 円盤は１度に１枚ずつしか移動できない。
規則２ 大きな円盤は小さな円盤の上には積むことができない。
規則３ 円盤は任意の棒から棒へ移動できるだけで、その他の場所には移動できない。
《問題３》
最初の円盤の移動規則３を、次のように変更する。
規則３″ 円盤は、棒Ａから棒Ｂ、棒Ｂから棒Ｃ、または、棒Ｃから棒Ａにしか直接移動できない（棒から棒への移動は一方通行）。
当然のことながら、棒以外の場所には移動できない。
この時、最初に棒Ａに積まれた８枚の円盤すべてを棒Ｂに移すためには、最低でも何回の円盤の移動が必要か？
《詳細解答３》 ２４４７回
これまでと同様な考え方をする。棒Ａにある円盤８を棒Ｂに移動するには、まず、上の７枚の円盤を棒Ｃに移動させる必要がある。そして、
円盤８を棒Ｂに移動後、棒Ｃにある７枚の円盤を棒Ｂに移動する。
ここで、A3(n) を、ｎ枚の円盤を棒Ａから棒Ｂに移す最少手順数。B3(n)、棒Ｂから棒Ａへ移す最少手順数とする。ここで、順方向の移動である。
棒Ｂ→Ｃへの移動と棒Ｃ→Ａへ移動の最少手順数は A3(n) に同じ。同様に、逆方向の移動、棒Ａ→Ｃ、棒Ｃ→Ｂの最少手順数は
B3(n) に同じ。
すると、上の手順は以下のようになる。
A3(8) = B3(7) + 1 + B3(7)
: : :
: : → 棒Ｃにある７枚の円盤を棒Ｂに移動
: → 棒Ａにある円盤８を棒Ｂに移動
→ 棒Ａにある上の７枚の円盤を棒Ｃに移動
次に、B3(7)、つまり、７枚の円盤を棒Ａから棒Ｃに移すことをで考えてみる。
７枚の円盤のうち一番大きな円盤７を、棒Ａから棒Ｃに移すとすると、移動規則により直接棒Ａから棒Ｃへ移動できないので、
棒Ａ→Ｂ、棒Ｂ→Ｃの二段階の移動の手順が必要。最初の棒Ａから棒Ｂへの移動では、小さい６枚を棒Ｃに移動しなければならない。
この移動には、B3(6) の手順が必要。この後、円盤７を、棒Ｂに移動する。次に、棒Ｃには、小さい６枚の円盤があるので、
これを棒Ａに移動した後でないと、棒Ｂにある円盤７を棒Ｃに移動できない。つまり、小さな６枚の円盤を棒Ａへ移さなければなければならない。
この手順は、順方向への移動だから A3(6) の手順が必要。この後、円盤７を棒Ｃに移動。
そして、棒Ａにある小さな６枚の円盤を棒Ｃに移動。この手順は、B3(6)。
この手順は、以下のようになる。
B3(7) = B3(6) + 1 + A3(6) + 1 + B3(6)
: : : : :
: : : : → 棒Ａにある６枚の小さな円盤を
: : : : 棒Ｃに移動
: : : → 棒Ｂにある円盤７を棒Ｃに移動
: : → 棒Ｃにある６枚の小さな円盤を棒Ａに移動
: → 棒Ａにある円盤７を棒Ｂに移動
→ 棒Ａにある６枚の小さな円盤を棒Ｃに移動
これらのことから、以下のようなる。
A3(8) = B3(7) + 1 + B3(7)
B3(7) = B3(6) + 1 + A3(6) + 1 + B3(6)
A3(6) = B3(5) + 1 + B3(5)
B3(6) = B3(5) + 1 + A3(5) + 1 + B3(5)
A3(5) = B3(4) + 1 + B3(4)
B3(5) = B3(4) + 1 + A3(4) + 1 + B3(4)
A3(4) = B3(3) + 1 + B3(3)
B3(4) = B3(3) + 1 + A3(3) + 1 + B3(3)
A3(3) = B3(2) + 1 + B3(2)
B3(3) = B3(2) + 1 + A3(2) + 1 + B3(2)
A3(2) = B3(1) + 1 + B3(1)
B3(2) = B3(1) + 1 + A3(1) + 1 + B3(1)
A3(1) = 1
B3(1) = 1 + 1
これを逆順に計算する。
B3(1) = 1 + 1 = 2
A3(1) = 1 = 1
B3(2) = B3(1) + 1 + A3(1) + 1 + B3(1)
= 2 + 1 1 + 1 2 = 7
A3(2) = B3(1) + 1 + B3(1)
= 2 + 1 + 2 = 5
B3(3) = B3(2) + 1 + A3(2) + 1 + B3(2)
= 7 + 1 + 5 + 1 + 7 = 21
A3(3) = B3(2) + 1 + B3(2)
= 7 + 1 + 7 = 15
B3(4) = B3(3) + 1 + A3(3) + 1 + B3(3)
= 21 + 1 + 15 + 1 + 21 = 59
A3(4) = B3(3) + 1 + B3(3)
= 21 + 1 + 21 = 43
B3(5) = B3(4) + 1 + A3(4) + 1 + B3(4)
= 59 + 1 + 43 + 1 + 59 = 163
A3(5) = B3(4) + 1 + B3(4)
= 59 + 1 + 59 = 119
B3(6) = B3(5) + 1 + A3(5) + 1 + B3(5)
= 163 + 1 119 + 1 + 163 = 447
A3(6) = B3(5) + 1 + B3(5)
= 163 + 1 + 163 = 327
B3(7) = B3(6) + 1 + A3(6) + 1 + B3(6)
= 447 + 1 + 327 + 1 + 447 = 1223
A3(8) = B3(7) + 1 + B3(7)
1223 + 1 + 1223 = 2447
これが答え。
一般化すると、A3(n) と B3(n) は、以下のように表わすことができる。
A3(1) = 1
A3(n) = 2 * B3(n-1) + 1 [n > 1]
B3(1) = 2
B3(n) = B3(n-1) + 1 + A3(n-1) + 1 + B3(n-1)
= (B3(n-1) + 1 + B3(n-1)) + A3(n-1) + 1
= A3(n) + A3(n-1) + 1 [n > 1]
これから、A3(n) は、次のように表わせる。
A3(1) = 1
A3(2) = 2 * B3(1) + 1 = 2 * 2 + 1 = 5
A3(n) = 2 * B3(n-1) + 1
= 2 * (A3(n-1) + A3(n-2) + 1) + 1
= 2 * A3(n-1) + 2 * A3(n-2) + 3 [n > 2]
∴ A3(n) = ((1+sqrt(3))^(n+1) - (1-sqrt(3))^(n+1)) / (2 * sqrt(3)) - 1
[n > 0]
解き方は省略。
数列サイトに、A005665 として掲載されている。