佐久間闇子と奇妙な世界

アクセスカウンタ

zoom RSS 世界はいつ終わる? 〜ハノイの塔の棒が1本増えたなら〜

<<   作成日時 : 2009/01/22 04:16   >>

かわいい ブログ気持玉 18 / トラックバック 0 / コメント 2

「ハノイの塔」の話は割と有名だと思うが、とりあえず説明しておこう。

◎初期設定・・・半径の全て異なるドーナツ状の円盤が、一つの棒にはまっている。円盤は半径の小さい順に上から並べられている。棒は3本である。

◎ルール1・・・円盤は1回に1つしか動かせない。

◎ルール2・・・円盤は、それより半径の小さい円盤の上に重ねてはいけない。

これらの設定とルールに従って、円盤を全て別の棒に初期状態と同じようにはめるには、何回動かせばよいか。その最小回数を求める問題だ。
円盤の枚数がX枚ならば、2のX乗回よりも1回少ない回数動かせば完了する。

ちなみにインドにあるという設定のオリジナルは、円盤が64枚。全て移し替えたときに世界は崩壊するという設定になっている。これを全て移し替えるにはどれくらいかかるのか。
1秒に1回動かしても、6000億年近くかかるのだ・・というのは有名な話。
私の研究はここからだ。

「孔子暗黒伝」というマンガをご存じだろうか。ラストは「暗黒神話」に続いている。
この話、物語としてもなかなか面白いのだが、作中でハノイの塔の話が出てくる。ハノイの塔の棒が1本増えて、4本になったのだ。こうなると、世界の破滅は遥かに早まる。では、どれくらい早まるのだろうか。
かつて挑戦したときには、力及ばず挫折した。しかし最近になって、おそらくこれが正解ではないかと思われるものを導き出した。少なくとも、これより回数が多いことはない。これより少ない回数で出来るかもしれないが。

それでは、ハノイの棒が4本のとき、世界の終わりはいつ来るか?
円盤は1秒に1回動かすものとする。

1:5時間後
2:5000年後
3:50万年後
4:50億年後

直感で答えてみよう。
答を知ってる人はさっさと下へスクロール。





               /~\
  _           /ヾヽヽヽ
 〈三三ミ丶 、     /ミヾヽヽヽ
  ヽ三三ミミミ 丶、_ <ミ_ミヾヾ-ヽ- |_
  ヽ二ニニ=   ~`´        \
     ` -二ニ=   _: : : :    ,   `ヽ、
        〉ニ=  // 、、、 、、(   (●) >
    , -‐'´彡彡ノノ { 、x x x < ヽ   ,フ ああ・・・世界はいつ終わるのだろうか・・・
  ,/三 彡彡ノ/  ヽ、x X X X/lll|_/
 (二ニ 彡-‐'"´    ,-‐'`‐,-‐‐/川|
  ` ‐'"´        /彡''/   !彡"
             {彡'/
             ヽノ





               /~\
  _           /ヾヽヽヽ
 〈三三ミ丶 、     /ミヾヽヽヽ
  ヽ三三ミミミ 丶、_ <ミ_ミヾヾ-ヽ- |_
  ヽ二ニニ=   ~`´        \
     ` -二ニ=   _: : : :    ,   `ヽ、
        〉ニ=  // 、、、 、、(   (●) >
    , -‐'´彡彡ノノ { 、x x x < ヽ   ,フ この世の終わりまで生き延びてやる・・!
  ,/三 彡彡ノ/  ヽ、x X X X/lll|_/
 (二ニ 彡-‐'"´    ,-‐'`‐,-‐‐/川|
  ` ‐'"´        /彡''/   !彡"
             {彡'/
             ヽノ





               /~\
  _           /ヾヽヽヽ
 〈三三ミ丶 、     /ミヾヽヽヽ
  ヽ三三ミミミ 丶、_ <ミ_ミヾヾ-ヽ- |_
  ヽ二ニニ=   ~`´        \
     ` -二ニ=   _: : : :    ,   `ヽ、
        〉ニ=  // 、、、 、、(   (●) >
    , -‐'´彡彡ノノ { 、x x x < ヽ   ,フ 再び数学的キンギョッ!
  ,/三 彡彡ノ/  ヽ、x X X X/lll|_/
 (二ニ 彡-‐'"´    ,-‐'`‐,-‐‐/川|
  ` ‐'"´        /彡''/   !彡"
             {彡'/
             ヽノ







こいつらは、以前の記事で出てきた数学的金魚の面々です。まだまだ生き残っているようですね。
さて、金魚たちは終末まで生き延びられるか・・?

答はYESです。

何故なら、終末はたったの5時間で来るからです。

終末が週末よりも早く来てしまうとは・・!
我ながら、この結果には驚きました。間違ってるんじゃないかとも思いました。しかし、たとえ間違っていたとしても、これより遅くはならないのです。

以下は、棒が3本の場合と4本の場合の、かかる回数の表です。

円盤の枚数  3本の場合  4本の場合
   1        1        1
   2        3        3
   3        7        5
   4       15        9
   5       31       13
   6       63       17
   7      127       25
   8      255       33
   9      511       41
  10     1023       49
  11     2047       65
  12     4095       81
  13     8191       97

ちなみに4本の場合ですが、円盤の枚数が8枚までは自力でやったのですが、それ以上はこんがらがってきました。しかも、自分のやった方法が最短ルートかどうかわからない。
仕方ないので、厳密な証明は放棄しました。数学者としてあるまじき態度かもしれませんが、この考え方ならば結果はどうなるのか・・というのが、どうしても知りたかったのです。

9枚以降ですが、私はこう考えました。
最初のX枚のうち、Y枚は棒が4本の場合の動かし方で動かす。そして、残りのX−Y枚を、棒が3本の場合の動かし方で動かす。最後に、Y枚を棒が4本の場合の動かし方で動かし、X−Y枚の上に重ねる。
Yについては、具体的な試行錯誤で求めました。
この方法で13枚まで求めました。ただし、“少なくともこれより遅いことはない”回数であるわけです。
さて、ここでいったんストップ。
棒の数が4本の場合、数列は
1、3、5、9、13、17、25、33、41、49、65、81、97・・・・です。
この数列を見て、ある規則に気がつきました。
いくつずつ増えているのか。
2、2、4、4、4、8、8、8、8、16、16、16です。
ならば・・と思って、この先も計算を続けました。
すると、思った通り。
97の次は113。その次は129。そしてその次は161。
こうなれば、後は簡単。
増える数は2、2、4、4、4、8、8、8、8、16、16、16、16、16、32、32・・・だから、円盤が64枚のときのかかる回数はすぐにわかる。流石に枚数がX枚ならば難しくなるが・・。

計算が間違っていなければ、答は18433。
1秒に1回動かせば、5時間7分13秒。
ちなみに「暗黒神話」では世界の終わりは56億7千万年後という設定。つまり逆に考えれば、あの世界ではハノイの塔の円盤は1回動かすのに30万年以上かかっているというわけだ・・・。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ
気持玉数 : 18
かわいい かわいい かわいい かわいい かわいい かわいい
驚いた 驚いた 驚いた 驚いた 驚いた
なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー) なるほど(納得、参考になった、ヘー)
ガッツ(がんばれ!) ガッツ(がんばれ!)
面白い
ナイス

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(2件)

内 容 ニックネーム/日時
私の直感は4を指し示しました。当てになりませんね。数学的キンギョの面々は見ているとだんだん愛着が湧いてきました。不思議です。

直感といえばある数学協議会でこんな問いがあったそうです。「袋の中に赤い玉が3個、青い玉が1個入っています。この中から2個の玉を取り出す時,2つの玉の色が違っている確率はいくつでしょうか。この問題を直感的に解いてください。その後できちんと計算して解いてみてください。あなたの計算は直感を裏切らなかったですか?」
奄美の黒兎
2009/01/22 19:45
奄美さん、こんばんは。
問題を出すときに間が空白では寂しいので、金魚のアスキーアートを入れてみましたが、それが気に入ってしまいまして。
私も知らなければ4番と答えそうですね。何しろ“56億7千万年”という言葉が頭にこびりついていますから。直感って、怖いですねー。
ちなみにその問題、直感で解こうとしたんですが、私の頭が勝手に計算を始めてしまいました。理系の性か。暗算では計算できない問題にした方がいいですね。
アッキー
2009/01/22 23:43

コメントする help

ニックネーム
URL(任意)
本 文
世界はいつ終わる? 〜ハノイの塔の棒が1本増えたなら〜 佐久間闇子と奇妙な世界/BIGLOBEウェブリブログ
文字サイズ:       閉じる