Lowest-cost Search

We are trying to find a hidden number selected from the set of integers $\{1, 2, \dots, 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 “$\mathbf 4$” and if the hidden number is higher than $4$ we will need one or two additional questions.
Let our second question be “$\mathbf 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 “$\mathbf 7$” and the total cost for this worst-case scenario will be $4+6+7={\color{red}\mathbf{17}}$.
We can improve considerably the worst-case cost for $n=8$, by asking “$\mathbf 5$” as our first question.
If we are told that the hidden number is higher than $5$, our second question will be “$\mathbf 7$”, then we’ll know for certain what the hidden number is (for a total cost of $5+7={\color{blue}\mathbf{12}}$).
If we are told that the hidden number is lower than $5$, our second question will be “$\mathbf 3$” and if the hidden number is lower than $3$ our third question will be “$\mathbf 1$”, giving a total cost of $5+3+1={\color{blue}\mathbf 9}$.
Since ${\color{blue}\mathbf{12}} \gt {\color{blue}\mathbf 9}$, the worst-case cost for this strategy is ${\color{red}\mathbf{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 \limits_{n = 1}^{100} C(n) = 17575$.
Find $\sum \limits_{n = 1}^{200000} C(n)$.

Let $a_n$ denote the optimal first guess for a sequence ending at $n$.

Then the worst-case cost is given by: $C(n)=2a_n+C(n-a_n)-a_n$.

The first term $2a_n$ offers a sure fire way to determine at least $a_n$ numbers, and the second term, $-a_n$, is actually a substractor, that derives from all leftover residues $C(n-a_n)$.

The dynamic algorithm of this problem can be set up from bottom to top, first sort out all $C(i)$, $1 \leq i \leq n$, then find out the maximum $a_m$ (which comes from residue deduction) , such that $2*m \leq n$, and finally iterate $a_m-1 \leq m \leq a_{m+1}$ for the $1+2+…+m+C(n-m)$ to find the minimum amount of $C(n)$.

Thus applying this strategy, we can apply a dynamic programming approach to solve for $C(n)$:

1. Initialize array `C` of length `n+1` with `C(1)`=0 and all others as large value.
2. `C(2)=1`, `C(3)=2`.
3. For `4` to `n`:
– For `k` in `1` to `n`:
– If `2*k` <= `i`, set `kmax = k` (to find maximum `k` that `2*k` <= `i`). - For `k` in `kmax+1` to `kmax-1` in steps of `-1`: - set `C(i)` = min(`C(i)`, `2*k+C(i-k)`) 4. Return `C`. The direct mathematical solution to solve $C(n)$ isn't straightforward, as it's nontrivial. However, this problem can be more or less solved by designing a smart strategy for questioning, coupled with using dynamic programming, and using efficient data structures to store and calculate these values. To find $\sum_{n=1}^{200000} C(n)$, add up all the elements $C(n)$ as they get computed in the dynamic programming. While this approach doesn't give a direct equation to solve $C(n)$, it is efficient for programming and can solve the given problem in a reasonable time.

More Answers: