# Average number of guesses for simple game

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)?

• I don't think there is a better way. – Arthur Mar 26 '17 at 0:13
• @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. – Joao Noch Mar 26 '17 at 0:17
• Note that $2^7=128$, but that doesn't change anything. – Ross Millikan Mar 26 '17 at 0:18
• @RossMillikan if it helps $100=2^6+2^5+2^2$ – Joao Noch Mar 26 '17 at 0:19
• 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? – 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.