What is the best way to guess a number in a limited number of guesses?

Question

A random integer is picked from 0 to 100. You can make 5 guesses at what the number is, and after each guess, you are told if your guess was too high or too low. What strategy maximizes your probability of guessing the number?

Answer 1

You can work your way back from the end of the game to optimize the strategy. At each stage, you know that the number is in some interval. On the last guess, you'll just guess any number in the interval, and your chance to win is one over the length of the interval. On the penultimate guess, you have some interval $[i,j[$ (closed at the beginning and open at the end to simplify the length calculations), and you can choose some integer $k\in[i,j[$ to maximize the remaining winning probability. You have probability $\frac1{j-i}$ to win right away by guessing right. You have probability $\frac{k-i}{j-i}$ to guess too high, and then you have probability $\frac1{k-i}$ to guess right on the last guess; and you have probability $\frac{j-k-1}{j-i}$ too guess too low, and then you have probability $\frac1{j-k-1}$ to guess right on the last guess; so the total winning probability as function of $k$ is

$$ \frac1{j-i}+\frac{k-i}{j-i}\cdot\frac1{k-i}+\frac{j-k-1}{j-i}\cdot\frac1{j-k-1}=\frac3{j-i}\;, $$

which doesn't in fact depend on $k$. Each of the three possibilities contributes $\frac1{j-i}$ to the winning probability, independent of $k$.

But that means we don't have to do much more work for the previous stages – they work essentially like the penultimate one, except the cases of guessing too high or too low contribute larger winning probabilities, whereas the case of guessing right still just contributes the reciprocal of the interval length. So on the third guess, your winning probability is $3+1+3=7$ over the interval length, on the second guess it's $7+1+7=15$ over the interval length, and on the first guess it's $15+1+15$ over the interval length, that is, $\frac{31}{101}$ – irrespective of which numbers you choose to guess.

Well, not completely irrespective, that can't be, since you obviously only have a $\frac5{101}$ winning probability if you guess $0$, $1$, $2$, $3$, $4$. The argument is only valid as long as you always leave enough numbers on either side to have all three possibilities – if you don't, you lose the contribution from that possibility. That means that you have to leave at least $2^{5-n}-1$ numbers on either side on the $n$-th guess, so for instance your first guess must be between $15$ and $85$.