406 : 推測ゲーム

質問することで整数の集合${1, 2, \dots, 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, \sqrt{2}, \sqrt{3}) = 13.22073197\dots$ $C(20000, 5, 7) = 82$ $C(2000000, \sqrt{5}, \sqrt{7}) = 49.63755955\dots$

$F_k$をフィボナッチ数と定義しよう：$Fk = F_{k-1} + F_{k-2}$, 初期条件は$F_1 = F_2 = 1$

$\displaystyle \sum_{k=1}^{30} C(10^{12}, \sqrt{k}, \sqrt{F_k})$を求め、回答を小数点以下8桁になるよう四捨五入して答えよ。