Problem 328
Lowest-cost Search
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, has a cost equal to the number asked and we get one of three possible answers:
- “Your guess is lower than the hidden number”, or
- “Yes, that’s it!”, or
- “Your guess is higher than the hidden number”.
Given the value of n, an optimal strategy minimizes the total cost (i.e. the sum of all the questions asked) for the worst possible case. E.g.
If n=3, the best we can do is obviously to ask the number “2“. The answer will immediately lead us to find the hidden number (at a total cost = 2).
If n=8, we might decide to use a “binary search” type of strategy: Our first question would be “4“ and if the hidden number is higher than 4 we will need one or two additional questions.
Let our second question be “6“. If the hidden number is still higher than 6, we will need a third question in order to discriminate between 7 and 8.
Thus, our third question will be “7“ and the total cost for this worst-case scenario will be 4+6+7=17.
We can improve considerably the worst-case cost for n=8, by asking “5“ as our first question.
If we are told that the hidden number is higher than 5, our second question will be “7“, then we’ll know for certain what the hidden number is (for a total cost of 5+7=12).
If we are told that the hidden number is lower than 5, our second question will be “3“ and if the hidden number is lower than 3 our third question will be “1“, giving a total cost of 5+3+1=9.
Since 12>9, the worst-case cost for this strategy is 12. That’s better than what we achieved previously with the “binary search” strategy; it is also better than or equal to any other strategy.
So, in fact, we have just described an optimal strategy for n=8.
Let C(n) be the worst-case cost achieved by an optimal strategy for n, as described above.
Thus C(1) = 0, C(2) = 1, C(3) = 2 and C(8) = 12.
Similarly, C(100) = 400 and $\sum_{n=1}^{100}$C(n) = 17575.
Find $\sum_{n=1}^{200000}$C(n).
最低成本搜索
我们正试图通过提问的方式从数集{1, 2, …, n}中找出一个特定的隐藏数。每次我们提问一个数，需要付出和所问的数同等大小的成本，我们得到的回答可能是以下三种之一：
- “你猜的数小于隐藏数”，或者
- “你猜对了！”，或者
- “你猜的数大于隐藏数”。
给定n的值，最优策略指的是在在最差的情况下最小化总成本（即所有提问的数字之和）的策略，下面来举一些例子进行说明。
如果n=3，我们最好的选择显然是提问”2“，回答将直接告诉我们隐藏数是多少（总成本=2）。
如果n=8，我们先考虑这样一个“二分搜索”的策略：第一次我们提问“4”；如果隐藏数大于4，我们还需要再问一两次问题。
第二次不妨问“6”。如果隐藏数仍然比6大，我们需要问第三次问题以区分7和8。因此，第三次我们问“7”，因此这种最差的场景下的总成本为4+6+7=17。
然而，如果我们第一次提问“5”，能够可观地降低n=8的最差情况下的总成本。
如果我们被告知隐藏数大于5，我们第二次问“7”就可以立即确认隐藏数（总成本为5+7=12）。
如果我们被告知隐藏数小于5，我们第二次问“3”，如果隐藏数还小于3，第三次我们问“1”，总成本为5+3+1=9。
因为12>9，这种策略在最差情况下的成本是12。这比之前使用“二分搜索”策略的结果更优；比起其它策略，这个策略也更好或至少一样好。
事实上，我们刚才描述的就是n=8时的一个最优策略。
记C(n)为n的最优策略在最差情况下的成本，其中最优策略的含义如上所述。
因此C(1) = 0，C(2) = 1，C(3) = 2以及C(8) = 12。
此外，已知C(100) = 400以及$\sum_{n=1}^{100}$C(n) = 17575。
求$\sum_{n=1}^{200000}$C(n)。