Guess my number

Probability Level 2

Here's a fun game for the classroom: I randomly generate a number from 1 to 1000. A chosen student makes a guess and (unless they happen to guess correctly) I tell them whether the actual number is higher or lower. They get 10 guesses, each time they don't get the number I tell them "higher" or "lower." It is clear that with perfect guessing they should always win, although if they are figuring in their heads and other students are giving them suggestions, this is not always the case.

If a student does make optimal guesses at every stage, what is the probability that they will win on or before their 9th guess?

The answer is 0.511.

1 solution

Jeremy Galvagni
Jun 20, 2018

One guess can get you only one number.

Suppose you got 2 guesses. You could win if the game were to guess a number from 1 to 3 (just guess 2 first)

Suppose you got 3 guesses. Now you can win if the number is 1 to 7. (guess 4 first and the "higher" or "lower" will reduce it to one of 3 numbers.

It should now be clear that with n guesses you can win if there are $2^{n}-1$ numbers (or fewer)

$2^{10}-1=1023$ so that's why the 1 to 1000 game is guaranteed with 10 guesses.

$2^{9}-1=511$ so you can only discern this many numbers out of 1000.

So the answer is $\frac{511}{1000}=\boxed{0.511}$

Guess my number

The answer is 0.511.

1 solution

0 pending reports