問題24　（boojam　さん）　　

　【ハノイの塔】
　　　　先にも書いたように、この問題に対する一般解については未解決問題なので、私の力の範囲を超えている。そこで、私の知っていることを
簡単に補足しておく。
棒が４本の時の最少手順数の求め方は、１９０７年から未解決問題とされている。また、今回の問題を、円盤ｎ枚、棒ｐ本に拡張した場合における
最少手順数 S(n,p)については、１９４１年に J. S. Frame と B. M. Stewart が、以下のようにして求められるという予想を発表している。
　　　　　　　　　　　S(n,p) = min { 2 * S(m,p) + S(n-m,p-1) | n > m >= 0, p > 3 }
上で解説した円盤の移動方法は、実質的に Frame と Stewart の予想と同じである。つまり、本当の最少手順数ではない可能性があるということだ。
しかしながら、今回の問題を含めて、棒の数と円盤の数が少ない場合は、総当りによる方法によって求めた最少手順数と、Frame と Stewart の方法で
求めた手順数が一致することは既に確認されている。
　　　　一般に、Frame と Stewart の予想は正しいと広く信じられている。つい最近この予想が正しいとする有力な証拠が得られたとする論文が
発表されているものの、完全な証明や反証は、この解説を書いている２００４年９月の時点では得られていない。
　　　皆さんお馴染みの数列サイトにも、棒４本と５本の場合の最少手順数が、それぞれ A007664と A007665 として掲載されている。
また、インターネット検索において、「hanoi multi peg」あるいは「Frame Stewart conjecture」などをキーワードにすれば、一般化されたこの問題に
関する論文や説明を多数見つけることができる。

《あとがき（のようなもの）》

　　問題６の解説に対するお詫びのため、「ハノイの塔」に関する蘊蓄を少し。「ハノイの塔」は、１８８３年にフランスの数学者 Edouard Lucas
(日本では、リュカとして知られている）が、インドに伝わる神話の「梵天の塔」を元に発明したとされている。
　　この「梵天の塔」の神話の要旨は次の通り。神様である「梵天」が宇宙創成の際、ベナレスというところに、奥の院を持つ大寺院を建てた。
奥の院の中には、ダイヤモンドで出来た３本の柱があり、その内の１本の柱には、金で出来た穴の空いた大きさの異なる６４枚の円盤が
重ねられている。それらの円盤を「ハノイの塔」と同じ移動規則に従って（というか、こちらの方が先）、６４枚の円盤すべてを別の柱に移すことを、
僧侶たちに命じた。そして、すべての円盤を移し終えたとき、大寺院は崩壊し、宇宙も消滅すると伝えられている。
ちなみに、１秒に１枚ずつ円盤を移動できたとして、６４枚をすべて移し終えるには、約５８５０億年かかる。
　　Lucas の発表以来、「ハノイの塔」の数学的考察は、２００件以上も論文の形で発表されている。最近でも年に数件コンスタントに発表されている。
問題６を一般化したものだけでなく、問題２や３のように移動方法に制約を設けたもの、問題４や５のように円盤の重ね方に制約を設けたものなど、
多数の変種も存在する。「ハノイの塔」は、単純な割には奥が深いと言えるだろう。
　　また、数列サイトで、「Tower of Hanoi」として、word 検索すれば、「ハノイの塔」およびその変種に関する数列の一部が検索できる。
その他の変種については、インターネットで検索するなり、新たに考案するなり、皆さん自身で楽しんでいただきたい。
　　最後に。これら一連の問題は、Graham、Knuth、Patashnik ３人の共著である「Concrete Mathematics」（翻訳では「コンピュータの数学」）の
第１章の問題を参考にしたこと（というか、ほとんど、そのまま）を断っておく。



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

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

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

《問題１》
　　最初に棒Ａに積まれた８枚の円盤すべてを棒Ｂに移すには、最低でも何回の円盤の移動が必要か？　
《問題２》
　　円盤の移動規則３を、次のように変更する。
　　　　　規則３′　円盤は、棒Ａと棒Ｂの間で直接移動できないこととする。つまり、すべての移動は必ず棒Ｃに移すか、棒Ｃから移す。
　　　　　　　　　　　　棒以外の場所にも移動できない。
　　この時、最初に棒Ａに積まれた８枚の円盤すべてを棒Ｂに移すためには、最低でも何回の円盤の移動が必要か？
《問題３》
　　最初の円盤の移動規則３を、次のように変更する。
　　　　　　規則３″　円盤は、棒Ａから棒Ｂ、棒Ｂから棒Ｃ、または、棒Ｃから棒Ａにしか直接移動できない（棒から棒への移動は一方通行）。
　　　　　　　　　　　当然のことながら、棒以外の場所には移動できない。
　　この時、最初に棒Ａに積まれた８枚の円盤すべてを棒Ｂに移すためには、最低でも何回の円盤の移動が必要か？
《問題４》
　　大きさが異なる８枚の円盤に、同じ大きさのものを１枚ずつ加える。つまり、同じ大きさの円盤が２枚ずつ計１６枚ある。
　　この１６枚の円盤が、大きさの順に棒Ａに積まれている。

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

解答編

《詳細解答１》　　　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]

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

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

ｎ枚の円盤を、棒Ａから棒Ｂへ移動する最少手順の数を、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]

《詳細解答３》　２４４７回

これまでと同様な考え方をする。棒Ａにある円盤８を棒Ｂに移動するには、まず、上の７枚の円盤を棒Ｃに移動させる必要がある。そして、
円盤８を棒Ｂに移動後、棒Ｃにある７枚の円盤を棒Ｂに移動する。

ここで、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 として掲載されている。

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

基本的に、《問題１》と同じ。まず、（ｎ−１）の２倍の数の円盤を棒Ｃに移す。残りの２枚を棒Ｂに移した後、棒Ｃにあるすべての円盤を
棒Ｂに移せば良い。この手順は、一番下にある円盤を動かすための最少手順をとっているので、結果として順序を保存しないで移動
するための最少手順であることが判る。

ここで、ｎ種類の円盤（計ｎ×２枚）を移す最少手順数を A4(n) と表わせば、以下のようになる。

A4(1) = 2
A4(n) = A4(n-1) + 2 + A4(n-1)
= 2 * A4(n-1) + 2 [n > 1]

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

解き方は省略。

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

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

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

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

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

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

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

ここで、ｎ種類２組みの円盤を元の順番を保存して移動する手順の最少手順数を 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

となっている。

《詳細解答６》　３３回

この問題は、一筋縄ではいかない。ｎ枚の円盤に対して、棒が４本あるときの最少手順を 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

これが答え。