Guessing a Number by Halving

Key idea. Each answer leaves either the guessed number (and you have found it) or one of two smaller sets, so $k$ guesses can handle at most $2^k-1$ candidates.

Let $f(k)$ be the largest number of candidates for which some strategy is guaranteed to guess the number within $k$ guesses. Here “identify” means making the correct guess.

Upper bound. Suppose the current candidate set $S$ can be resolved in $k$ guesses, and the first guess is $g$. The reply “correct” covers at most one candidate. The candidates below $g$ must then be resolved in $k-1$ further guesses, and so must those above $g$. So each of these two sets has at most $f(k-1)$ elements. Hence

Induction gives $f(k)\le 2^k-1$.

Achievability. We show by induction that any block of $2^k-1$ consecutive integers can be resolved in $k$ guesses. For $k=0$ the block is empty and there is nothing to do. For $k\ge 1$, guess the middle element of the block. If the reply is “correct” you are done. Otherwise the remaining candidates form a block of $2^{k-1}-1$ consecutive integers, which the induction hypothesis resolves in $k-1$ more guesses. So $f(k)=2^k-1$.

Applying this to $1000$ numbers.

• Since $2^9-1=511<1000$, no strategy can guarantee success within $9$ guesses.
• Since $2^{10}-1=1023\ge 1000$, ten guesses suffice. Run the halving strategy on $\{1,\dots,1023\}$; the extra numbers $1001$ to $1023$ are simply never the answer. Equivalently, always guess the midpoint of the remaining interval.

The uniform randomness of the choice plays no role, because the guarantee must hold for every number. The tempting count of $2^k$ numbers in $k$ guesses is slightly off; the correct count is $2^k-1$. Here this does not change the answer.