問題24　（boojam　さん）　　

　【ハノイの塔】

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

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

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

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

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

順位の決め方　各問を100点満点にします（問題１と２はセットで完全解答）。１位の方には100点　２位の方には99点というように点数を１点づつ減らします。
　　　　　　　　　　合計点の高い方から順位をつけます。


すべての問題の解答


問題24　正解者一覧表