*[[Problem 497:http://projecteuler.net/problem=497]] 「酔いどれハノイの塔」 [#eb9a9ea1]

3本の直立した棒と, その棒に差し入れることのできる異なる大きさの複数の円盤からなる, 有名な数学パズル「ハノイの塔」についてボブはとても詳しい.
このゲームは一番左の棒に大きい順に '''n''' 個の円盤が入れられた状態から始まる.
以下のルールによって一番左の棒から一番右の棒まで円盤をすべて移動させるのがゲームの目的である: 

+ 1回につき1つの円盤のみ動かせる.
+ 正しい移動とは, 積み重なった円盤の山から一番上の円盤を取り, 別の円盤の山(もしくは何も置かれていない棒)へ置くことで構成される.
+ 小さい円盤の上に大きい円盤を置いてはならない.

このゲームの変形版として, 1 から '''k''' の昇順に番号付けされた, '''k''' 区画(真四角のタイル)からなる細長い部屋を考えよう.
3本の棒は区画 '''a''', '''b''', '''c''' に置かれ, '''n''' 個の円盤からなる山が '''a''' 区画の棒に置かれている.

ボブは区画 '''b''' に立ってゲームを開始する.
彼の目的は区画 '''c''' の棒にすべての円盤を移動してハノイの塔をプレイすることだ.
ただし, ボブはお目当てとなる棒や円盤の山がある区画の上にいる時にのみ円盤を拾い上げるか置くことができる.

残念なことに, さらにボブは酔っ払ってもいる.
この移動では, ボブは同じ確率で1つ左の区画か1つ右の区画かのどちらかによろめいてしまう, ただしボブが部屋の端にいるときにかぎり, 彼は1方向にのみ移動できる.
ボブはほろ酔い気分であるにもかかわらず, このようなゲームのルールに従い, 円盤を拾い上げ置いたりする円盤を選択することができる.

以下のアニメーションは例として '''n''' = 3, '''k''' = 7, '''a''' = 2, '''b''' = 4, '''c''' = 6 の場合のゲームを横から見たところを表現したものである.

#ref(p497_hanoi.gif,center,nolink)

最適にプレイされた1回のゲームの期間中にボブが移動する区画の最小期待数を E('''n''','''k''','''a''','''b''','''c''') としよう.
ゲームは円盤の拾い上げた回数が最小の時に最適にプレイされる.

大変興味深いことに, その結果は常に整数となる.
例えば, E(2,5,1,3,5) = 60, そして E(3,20,4,9,17) = 2358.

∑&sub{1≤n≤10000}; E(n,10&sup{n};,3&sup{n};,6&sup{n};,9&sup{n};) の下9桁を求めよ.


トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS