Problem 887

Bounded Binary Search

Consider the problem of determining a secret number from a set $\{1, \ldots, N\}$ by repeatedly choosing a number $y$ and asking “Is the secret number greater than $y$?”.

If $N=1$ then no questions need to be asked. If $N=2$ then only one question needs to be asked. If $N=64$ then six questions need to be asked. However, in the latter case if the secret number is $1$ then six questions still need to be asked. We want to restrict the number of questions asked for small values.

Let $Q(N, d)$ be the least number of questions needed for a strategy that can find any secret number from the set $\{1, \ldots, N\}$ where no more than $x + d$ questions are needed to find the secret value $x$.

It can be proved that $Q(N, 0) = N - 1$. You are also given $Q(7, 1) = 3$ and $Q(777, 2) = 10$.

Find $\displaystyle \sum_{d=0}^7 \sum_{N=1}^{7^{10}} Q(N, d)$.

有界二分搜索

考虑如下问题：现需从集合$\{1, \ldots, N\}$中确定一个秘密数值，每次可以选择一个数$y$，并询问“秘密数值是否大于$y$？”。

如果$N=1$，则无需提问。如果$N=2$，则只需要问一个问题。如果$N=64$，则需要问六个问题，但采取这种策略时，即使秘密数值是$1$，也仍然需要问六个问题。相反，本题希望寻找一种尽可能减少秘密数值较小时所需提问数量的策略。

考虑所有从集合$\{1, \ldots, N\}$中找出任意秘密数值$x$所需的问题数不超过$x + d$的策略，记这种策略所需的最少提问次数为$Q(N,d)$。

可以证明$Q(N, 0) = N - 1$。已知$Q(7, 1) = 3$，$Q(777, 2) = 10$。

求$\displaystyle \sum_{d=0}^7 \sum_{N=1}^{7^{10}} Q(N, d)$。