« 音程問題 | トップページ

ハノイの塔(再掲+α)

以前にも話題にしたことがある(以下、一部重複)

Img_0734

これは「ハノイの塔」というパズルだ。数学的でありまた芸術的でもあるパズルだ。ルールは簡単。

ゴール:全部の円盤を右の塔に移す。
(1)1回に1枚ずつしか動かせない。
(2)大きな円盤を小さな円盤の上に置いてはいけない。

このゲームのWEB版がインターネットで見つかった。自由に使ってよいというので、自分のHPに置いた。遊んでいただきたい。

http://takashiyoshida.com/hanoi.html

このゲームから、いろいろなことを考えることができる。代表的なものは次の通り。

(1)円盤がn枚の時には円盤を最少で何回移動すればゴールにたとりつくか。
(2)任意のnにおいて(nがいかなる自然数の場合にも)n枚の時に最低の回数でゴールにたどりつく手順を示すプログラムをつくれ。

(1)については私程度でも何とか自分で問題が解ける。現在の「高校数学B」の「数列」を理解すれば解ける。
① n=1のときは1回、n=2 の時3回、n=3のときは7回・・・という経験則から、2^n-1(^は累乗を表す。すなわち 2を n 乗して 1引いた数)が最少移動回数。これを数学的帰納法を用いて証明すればよい。
②漸化式を使う方法もある。本当は、TeXを使って表したいのだが、面倒だし使い方を忘れたので、手書きで示す。

Hanoi

(2)については「再帰」という考え方で作るらしいが、頭がまわらない。
そこでもっと単純化する方法を考えた。
次のように動かせば、かならずゴールにたどりつける。
一番大きな円盤から順番に数字をつける。(1〜N)
(1)奇数番号の円盤は、左→右 右→中 中→左としか動かせない。
(2)偶数番号の円盤は、左→中 中→右 右→左としか動かせない。
(3)連続して同じ円盤を動かせない。

このパズルのルールと合わせると不思議なことに(?)、動かせる円盤は1枚に限定される。そしてそしてその限定された1枚を限定された位置に動かす。これを続けるとゴールにたどり着く。ゴールにたどり着くと動かせる盤がなくなる。これならプログラミングも簡単である。実は昔のBasic 言語で作っているのだが、Webで公開する方法がわからない。

しかしなぜ上のルールによるとゴールにたどりつくのか証明ができない。もちろんNが限定された数なら10だろうと20だろうと証明できるのだが。上のルールも経験則なのだ。

 

ところで、 2^n-1と簡単に書いたが、これは実はすごい数なのだ。
上で紹介した  Web 上のプログラムでは、 n=8 まで実行することが可能である。
このとき最少移動回数は、 2^8-1=255 である。1秒間1枚動かせるとすれば4分15秒。10枚くらいならなんとかなるだろう。しかし、それを過ぎるともう大変だ。ほぼ、2倍ずつ増えていくのである。計算は省略するが、32枚で人間の一生を超える時間になる。そして100枚となるとどうなるか。エクセルで  "=2^100-1 "と入力すると、 "1.26765E+30" と出力される。これは 1.26765の10^30倍という意味なので31桁の数字である。これは宇宙の歴史さえ超える数値であり「天文学的」を超える数値なのである。

こうやって考えてみると、人間の一生がいかに小さいものであるかがよくわかる。こんな簡単なゲームでも一生かかって30枚程度しか動かせないのである。囲碁や将棋が瞬く間にAIに席巻されたのも当然といえば当然のことである。

|

« 音程問題 | トップページ

コメント

コメントを書く



(ウェブ上には掲載しません)




« 音程問題 | トップページ