Guess a number

Suppose Alice is going to choose a number between $\ell$ and $h$ (both inclusive), which is a set of $h-\ell+1$ numbers Clearly the number of guesses required when $\ell = h$ is 1.

Now suppose $\ell < h$ , and suppose Bob guesses some number $k$ with $\ell \le k \le h$ . If $k$ happens to be Alice's number, then Bob is done, but otherwise space of possibilities is divided into two: $\ell$ to $k-1$ and $k+1$ to $h$ . In the worst case, Alice's number is in the larger of these two intervals, so that the number of guesses Bob needs is one more than the number of guesses needed for the larger of the two intervals. (One more to account for his first guess which was $k$ ). Clearly this will be minimized if Bob makes the two intervals as close as possible in size. That is, they are either of equal size or their sizes differ by 1.

Thus, if we start with an interval of length $N$ then Bob's best strategy is to have his guess divide the interval into two intervals, one of size $\lfloor N/2 \rfloor$ and the other either the same size or one less.

Each time the length of the interval is halved, Bob has used one guess. And he needs one guess for an interval of length 1. An easy induction now shows that the number of guesses required for an interval of length $N$ is $\lfloor\log_2(N)\rfloor+1$ . Note that this is both the number of guesses Bob needs in the worst case, as well as a sufficient number in any case, since we have demonstrated a strategy for Bob.

Plugging in $N= 10,000$ , we get $\lfloor\log_2(10,000)\rfloor +1 = \fbox{14}$

This is just a guess!

Bob just keeps on guessing half of what the sample space is. [E.g At first, he guesses 5000, then knowing whether its greater or smaller he guesses 7,500 or 2,500 respectively.] At the end of the 12th try, there would be 2 cards left [ $floor (\frac {10,000}{2^{12}})=2$ ]. Then he would need a maximum of just 2 more guesses, giving us the answer of 14 .

i don't know, i just using the computer science method of binary search to find the answers. find the median (5000), then divide the remains with N times until the the last remain is equal or lesser to 1, answers are 14 because the last remain is 0.687( less than 1) in the 14th times.

If the response is smaller or larger, he responds again. Since 2^14 > 10,000, but 2^13 < 10,000, the answer must be 14. Ed Gray