Problem 406 「推測ゲーム」

質問することで整数の集合 {1, 2, ..., n} より選ばれた秘密の数字を見つけ出したい. 質問する数字それぞれに対し, 以下の3つの回答から一つを得る.

  • 「あなたの推測は秘密の数字より小さいです.」 ( a のコストがかかる )
  • 「あなたの推測は秘密の数字より大きいです.」 ( b のコストがかかる )
  • 「はい, 正解です.」 ( ゲーム終了 )

与えられた値 n, a, b において, 最適戦略とは最悪のケースの総コストを最小化することである.

例えば, もし n = 5, a = 2, b = 3 の場合, そして最初の質問として ( 秘密の数字が ) "2" であるかどうかを聞いてみる.

もし 2 が秘密の数字より大きければ ( コストは b=3 ), 秘密の数字は "1" であることがわかる. ( 総コストは 3 )
もし 2 が秘密の数字より小さければ ( コストは a=2 ), 次の質問は "4" となる.
もし 4 が秘密の数字より大きければ ( コストは b=3 ), 秘密の数字は "3" であることがわかる. ( 総コストは 2+3=5 )
もし 4 が秘密の数字より小さければ ( コストは a=2 ), 秘密の数字は "5" であることがわかる. ( 総コストは 2+2=4 )
このようにして, この戦略における最悪のケースのコストは 5 となる. またこれが最も低い最悪ケースのコストであることを示すことができる. つまり, これが与えられた値 n, a, b における最適戦略である.

与えられた値 n, a, b において最適戦略における最悪ケースのコストを C(n, a, b) としよう.

以下に例を示す:
C(5, 2, 3) = 5
C(500, √2, √3) = 13.22073197...
C(20000, 5, 7) = 82
C(2000000, √5, √7) = 49.63755955...

フィボナッチ数 Fk を定義しよう: Fk = Fk-1 + Fk-2, 初期条件は F1 = F2 = 1.

Σ1≤k≤30C(1012, √k, √Fk) を求め, 回答を小数点以下8桁になるよう四捨五入して答えよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2012-12-17 (月) 00:39:45 (1704d)