Problem 406
Guessing Game
We are trying to find a hidden number selected from the set of integers {1, 2, …, n} by asking questions. Each number (question) we ask, we get one of three possible answers:
- “Your guess is lower than the hidden number” (and you incur a cost of a), or
- “Your guess is higher than the hidden number” (and you incur a cost of b), or
- “Yes, that’s it!” (and the game ends).
Given the value of n, a, and b, an optimal strategy minimizes the total cost for the worst possible case.
For example, if n = 5, a = 2, and b = 3, then we may begin by asking “2“ as our first question.
If we are told that 2 is higher than the hidden number (for a cost of b=3), then we are sure that “1“ is the hidden number (for a total cost of 3).
If we are told that 2 is lower than the hidden number (for a cost of a=2), then our next question will be “4“.
If we are told that 4 is higher than the hidden number (for a cost of b=3), then we are sure that “3“ is the hidden number (for a total cost of 2+3=5).
If we are told that 4 is lower than the hidden number (for a cost of a=2), then we are sure that “5“ is the hidden number (for a total cost of 2+2=4).
Thus, the worst-case cost achieved by this strategy is 5. It can also be shown that this is the lowest worst-case cost that can be achieved. So, in fact, we have just described an optimal strategy for the given values of n, a, and b.
Let C(n, a, b) be the worst-case cost achieved by an optimal strategy for the given values of n, a, and b.
Here are a few examples:
C(5, 2, 3) = 5
C(500, √2, √3) = 13.22073197…
C(20000, 5, 7) = 82
C(2000000, √5, √7) = 49.63755955…
Let Fk be the Fibonacci numbers: Fk = Fk-1 + Fk-2 with base cases F1 = F2 = 1.
Find ∑1≤k≤30 C(1012, √k, √Fk), and give your answer rounded to 8 decimal places behind the decimal point.
猜数游戏
我们尝试通过提问来确定整数集合{1, 2, …, n}中的某个特定数。每次提问时我们说一个数，可能会得到下面三个回答中的一个：
- “你的猜测比准确数要小。”（同时你需要付出成本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值下的最优策略。
记C(n, a, b)是在给定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≤30 C(1012, √k, √Fk)，并将答案四舍五入到小数点后八位小数。