Home > ハノイの塔に関する考察

« いま一番面白いコントをしているのは | メイン | 一生懸命間違ってる »

ハノイの塔に関する考察

  • 2009-06-16 (火)

ハノイの塔というパズルをご存知でしょうか。

中央に穴のあいた大きさの異なる3枚の円盤と3本の棒があります。左の棒に3枚の円盤が下のものほど大きくなるようにささっています。この円盤を次のルールに従って移動させます。

20090616_01.gif

1回の操作で1枚の円盤をいずれかの棒に移動できます
小さい円盤の上に大きな円盤を置くような移動はできません

さて、すべての円盤を右側の棒に移動させるにはどうしたらいいでしょうか。

おもちゃ屋さんに売っていることもありますが、わざわざ買わなくても3枚の大きさの異なる紙などで代用して簡単に遊べます。ちなみに円盤は何枚あっても構いません。円盤を増やしていく中で自然にパズルが解ける「しくみ」が見えてきて、これは数学やアルゴリズムの題材として最適なものになります。

もはや数学者にとっては使い古された感のある古典パズル。でもこのパズルについて、少し面白い事実に気がつきました。いや、もちろんすでに有名なことなんだとは思いますので、正確には勝手に再発見だと思います。

このパズルを「最短の手数で解く方法」ではなく「どれだけ時間がかかっても確実に解ける方法」を探してみます。これは迷路の解法において有名な「右手を常に壁につけて進む」に相当するものです。

そのためにこのパズルに新たに一つのひとつ制約を加えます。

円盤は隣の棒にしか移動させることはできない

この条件を加えて円盤を動かそうとしてみましょう。最初の状態からは円盤の動かし方は1通りしかありません。そしてその次の状況からは動かし方は常に2通り、つまり「進むか」「戻るか」の選択肢しか存在しなくなります。やるべきことは常に「進む」を選択すること。そうすれば何も考えずに自動的にすべての円盤が右の棒に集まったところで道は行き止まりになり、晴れてパズルは解けたことになります。是非3枚のケースでやってみてください。ちなみに最短手数は7手ですが、この方法では26手かかります。でも解けます。

このような一定のルールに従って物を操作するパズルというのは、例えば「箱入り娘」などのスライドブロックパズルもそうですが、考えうるすべての状態を書き出し、1回の操作で移動できる状態を線でつないでいくことでスタートからゴールまでの「地図」を作ることができます。ですからこの手のパズルを解くことは本質的には迷路を解くことと全く同じなのです。このハノイの塔というパズルはスタートからゴールまでが枝分かれのない一本道でつながれる最も単純な構造を持つものだと言うことが分かりました。

しかも僕がとても感動したのは、先ほど言った3枚の操作手順26手は3枚を3つの棒に配置する方法の総数、つまり3の3乗の27パターン、をすべて網羅する経路になっているということ。つまり3枚の円盤がどのような状態で棒にささっていても(ただし大きなものほど下になっている)それは先ほどの1本道の途中の状態なので、そこから26手以下ですべての円盤を右の棒に集めることができるということです。

複雑な現象の奥に隠れている一本筋の通った事実を見つける。数学ってまさにこういうことだって思わせる発見でした。

ちなみに最近「役に立たない数学用語事典」を少しずつ更新してますので、久しく見ていなかった人はぜひお立ちよりください。

Comments:0

Comment Form

コメントを表示する前にこのブログのオーナーの承認が必要になることがあります。

Remember personal info

Home > ハノイの塔に関する考察

Search
Feeds

Page Top