ハノイの塔（３）
7段の「ハノイの塔」の最小手数の考え方は、次のようなものです。手順とは逆に、まず、最後に、右に7段の山を作るためには、中央に6段の山ができなければならない、と考えます。つまり、7段目を右に移すためには、右の柱を空けておかなければならないからです。左に7段目が残っていて、中央に6段の山ができていれば、次の手で7段目を左から右に移すことができます。逆に言えば、それ以外の方法はありません。その次に考えるのは、中央に6段の山を作るためには、右に5段の山ができないといけない、ということで、その後は、順に、中央に4段の山、右に3段の山、中央に2段の山、右に1段の山となりますが、1段の山とは1段目、つまり一番小さい板ということです。最初の1手は、1段目を左から右に移す、が正解です。何も考えないで、1段目を中央に移してしまうと、7段の山は中央にできてしまいます。それでも山を移したことにはなりますが、課題とは違う結果になってしまいます。
さて、この説明を聞くと、なぜ、右と中央だけなのか、と思う人もいるでしょう。それは、元々の山が左にあるからです。元々の山の一部が常に左に残っているので、段を作ることができるのは右と中央だけということになります。これで分かったことと思いますが、「数える」という真意は、段数を逆に数えるということなのです。つまり、(1)右7段の山→(2)中央6段の山→(3)右5段の山→(4)中央4段の山→(5)右3段の山→(6)中央2段の山→(7)右1段の山（1段目）、となります。
しかし、これだけでは、説明としては不十分です。中間の目標をたどっただけなので、この途中には、中途半端な山が、左、中央、右の柱に次々とできます。この中途半端な山、つまり、整然と積まれていない、中間の大きさの板が抜けた山が迷いの元なのです。中間の目標を忘れてしまうと、この中途半端な山を見ても、この先どうすれば良いのか、判断に苦しみます。ある中間の目標から次の中間の目標へは、一気にたどりつく必要があります。そのためにこそ、この「数える」方法が役に立つのです。例えば、中央に6段の山ができたとしましょう。次の手で左の7段目を右に移すことになりますが、その後はどうすればよいでしょうか。中央の6段の山を右に移すには、一時、7段目のことは忘れて、(1)右6段の山→(2)左5段の山→(3)右4段の山→(4)左3段の山→(5)右2段の山→(6)左1段の山（1段目）、となるので、1段目を中央から左に移すのが最初の手となります。何段かの山を間違えずに移動するためには、その山のある柱を除いた残りの柱を、移したい柱を起点にして山の段数まで交互に数え、最終点になった柱に一段目の板を移せばよいのです。途中で分からなくなっても、何段の山をどこへ、がはっきりしていれば、この方法が役に立ちます。
要するに、最終目標は一時忘れて、次の中間目標までを一気に進めること、がポイントです。そのためには、3段や4段の山の移動方法は覚えてしまった方がスムーズに行きます。それができるようになれば、後は「数える」方法が迷ったときのガイドになります。
