The guess-a-number game starts with one player (the chooser) picking a number between 1 and 100 (inclusive) and secretly writing it down. The other player (the guesser) attempts to guess the number. After each guess, the chooser responds with “correct” (the guesser guessed the number and the game is over), “higher” (the actual number is higher than the guess), or “lower” (the actual number is lower than the guess).

What is the average number of guesses the guesser will need to find the number given that he uses the optimal, most efficient strategy?

I found that it will be 6 guesses $29/32$ times and 7 guesses $3/32$ times using the most clumsy method ever which I won't post. It can be no more than 7 since $2^7=124>100$.

It was like

$(100-1)/2 = 49.5, \\(49-1)/2 = 24, \\(50-1)/2 = 24.5 \\-> 24, 25 $

with 24 $3/4$ of the time and 25 $1/4$ of the time, etc etc etc.

What is a better way (since the method had so many opportunities for error I'm probably wrong anyway)?

  • $\begingroup$ I don't think there is a better way. $\endgroup$ – Arthur Mar 26 '17 at 0:13
  • $\begingroup$ @Arthur I was thinking use some properties of the number 100 like a binary representation (1100100) to do some magic or something, immediately arriving at the conclusion that is was 6 guesses 29/32 times. $\endgroup$ – Joao Noch Mar 26 '17 at 0:17
  • $\begingroup$ Note that $2^7=128$, but that doesn't change anything. $\endgroup$ – Ross Millikan Mar 26 '17 at 0:18
  • $\begingroup$ @RossMillikan if it helps $100=2^6+2^5+2^2$ $\endgroup$ – Joao Noch Mar 26 '17 at 0:19
  • 1
    $\begingroup$ You might want to be slightly more specific about what you mean by "average". Are you assuming the chooser picks the number at random (according to which distribution?) and you are averaging over that? Are you assuming that the guesser's algorithm is randomized, and you are averaging over the guesser's choices? $\endgroup$ – Anonymous Mar 26 '17 at 7:43

If you want to split the interval, your first guess should be $\frac {100+1}2=50.5$ You can be a bit more efficient by making your guesses whole numbers, giving a chance of getting "correct". early. So if your first guess is $50$, you get away with $1$ guess $1/100$ of the time, while if you guess $50.5$ you lose the chance to be lucky. You have $2/100$ chance of winning in two guesses, $4/100$ chance in three, and so on. Other than that, binary search cannot be beaten.

  • $\begingroup$ What about a formula that when given the range (1-100) outputs the guess average length? I just want an easier way to find the average number of guesses. $\endgroup$ – Joao Noch Mar 26 '17 at 1:09
  • $\begingroup$ This answer assumes that the chooser picks a number at random. In a game, both players try their best and thus the chooser may be e.g. "hiding" his numbers in 1 or in 100, making the average higher. $\endgroup$ – mlc Mar 27 '17 at 6:35
  • $\begingroup$ Hey, don't I have a 2 in 99 chance of winning in two guesses, 4 in 97 chance of winning in three, etc because if you are on your second guess you are selecting out of a range of 99 options? (every number except 50) $\endgroup$ – Joao Noch Apr 2 '17 at 1:29
  • $\begingroup$ Not quite. Before you start, you have a 2 in 100 chance of winning in exactly two guesses, as you will do so if the number is 25 or 75 (or some small variation). Having failed on the first guess, your chance on the second depends on the result of the first. If your first was 50 and you are told lower, your chance on the second is 1 in 49. If you are told higher it is 1 in 50. If you are told correct, your chance on the second is zero. $\endgroup$ – Ross Millikan Apr 2 '17 at 4:35

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.