Probability of guessing correct number between 1-100

Question

You need to guess a number between 1-100 and after each guess I'm going to tell you if you guessed too high or too low. If you guess it on the first try you get \$5, on the second try \$4, then \$3, \$2, \$1, \$0, -$1 (you begin to lose money), etc. until you guess it right. The question is: should you play the game or not, meaning are you more likely to win or lose money? The problem was given by Steve Ballmer to candidates for position in Microsoft. He says that you're more likely to lose money but I'm not getting that result with my approach which is using binary search to filter out as many numbers on each try.

E.g.

1. I pick 50, if he says the guess is too low I eliminate the numbers <=50 and I'm left with 50 numbers (if he said too high I'd be left with 49 numbers but I'll go for the worst case scenario)
2. I pick the middle number out of the remaining ones and I'm left with 25 numbers
3. 12 numbers left
4. 6 numbers left
5. 3 numbers left
6. 1 numbers left
7. I guess the correct number

In the worst case scenario I need 7 tries to guess the correct number. Now, I calculate the expected value like this:

5 * 1/100 +
4 * 99/100*1/50 +
3 * 99/100*49/50*1/25 +
2 * 99/100*49/50*24/25*1/12 +
1 * 99/100*49/50*24/25*11/12*1/6 +
0 * 99/100*49/50*24/25*11/12*5/6*1/3 +
-1 * 99/100*49/50*24/25*11/12*5/6*2/3

which equals 0.068832 meaning I should be up 6.88 cents on average.

What am I getting wrong here?

Answer 1

Check the source for the original version of the problem, not what OP is quoting. In particular, watch Steve's interview for the exact phrasing which indicates that Steve gets to choose the number, as opposed to OP's interpretation that the number is randomly chosen from 1 to 100.

---

For this strategy of "guess the middle", the probability of needing exactly X guesses is:

• 1 guess - 1% -> corresponding to the probability that the number is 50.
• 2 guesses - 2% -> corresponding to the probability that the number is 25 or 75.
• 3 guesses - 4% -> corresponding to the probability that the number is any of the 4 "middles", like 12/37/62/87.
• 4 guesses - 8%
• 5 guesses - 16%
• 6 guesses - 32%
• 7 guesses - 37% -> 100% minus the above

This gives us an expected value of

$$ 1\% \times 5 + 2\% \times 4 + 4\% \times 3 + 8\% \times 2 + 16\% \times 1 + 32 \% \times 0 + 37 \% \times (-1) = 0.2 . $$

This is higher than what OP calculated, because OP assumed the "worst case scenario" and somehow came up with lower probability for 1-6 guesses, resulting in higher probability of 7 guesses. For example, my interpretation of OP's claims is the the probability of needing exactly 2 guesses is $99/100 \times 1/50 = 1.98\%$, and "it couldn't be more obvious". My interpretation is that "for 99% of the time, we have at least a 1/50 chance of guessing the number".

The reason why this is incorrect for the exact scenario, is because in the exact scenario,

• in $49\% $ of the time (when the number is 1-49), we have a $1/49$ chance of guessing it on the second guess
• in $0\%$ of the time (when the number is 50), we have a 0 chance of guessing it on the second guess
• in $50\%$ of the time (when the number is 51-100), we have a $1/50$ chance of guessing it on the second guess
  Hence, the total probability is $ 49 \% \times \frac{1}{49} + 1\% \times 0 + 50 \% \times \frac{1}{50} = 2\% $.