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?

  • $\begingroup$ Picking at halfway between the range... $\endgroup$ – TheSimpliFire Jun 1 '18 at 16:16
  • $\begingroup$ Interesting question. I suspect it's bisecting until the last guess and then picking at random in the short interval remaining. See if that works for $1000$ numbers and $2$ guesses. $\endgroup$ – Ethan Bolker Jun 1 '18 at 16:17
  • $\begingroup$ There are rather a lot of ways to give a success probability of $\frac{31}{101}$ $\endgroup$ – Henry Jun 1 '18 at 16:35
  • 1
    $\begingroup$ Is the goal to know the number after $5$ guesses, or that one of the guesses is the unknown number? (for instance, if you have $2$ choices and only one guess, you try one, and you will know the solution even if you picked the wrong one). $\endgroup$ – Jean-Claude Arbaut Jun 1 '18 at 17:01
  • 2
    $\begingroup$ Choose $31$ of the $101$ possibilities. Make you first guess the median of these and your later guesses the medians of those which remain plausible after the clues from the earlier guesses. So you have ${101 \choose 31}$ possible optimal strategies, almost $10^{26}$ $\endgroup$ – Henry Jun 1 '18 at 17:25

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$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.