John Graham-Cumming's blog

submited by

Style Pass

2024-09-03 13:30:05

Here's what he says: "I'm thinking of a number between 1 and 100. You can guess, after each guess I'll tell you whether high or low. You get it the first guess I'll give you five bucks. Four bucks, three, two, one, zero, you pay me a buck, you pay me two, you pay me three".

The question is "Should you accept to play this game?". In the interview, Ballmer states that the answer is "No" for two reasons: firstly, because he can pick numbers that'll be the most difficult for you to determine, secondly because the expected value of the game (assuming Ballmer chooses randomly) is negative: you end up paying Ballmer.

He's right on the first count. If you follow a binary search strategy (which will be optimal if he's choosing randomly) and he chooses one of 2, 5, 8, 11, 14, 17, 20, 22, 24, 27, 30, 33, 36, 39, 42, 45, 47, 49, 52, 55, 58, 61, 64, 67, 70, 72, 74, 77, 80, 83, 85, 87, 90, 93, 96, 98 or 100 then you owe him $1. For all other numbers you get $0 (if he chose 1, 4, 7, 10, 13, 16, 19, 23, 26, 29, 32, 35, 38, 41, 44, 48, 51, 54, 57, 60, 63, 66, 69, 73, 76, 79, 82, 86, 89, 92, 95 or 99) or a positive outcome (some of his money!).

In the video above Ballmer chooses 59 which a binary search strategy would have found in 5 steps resulting in the interviewer, Emily Chang, winning $1. She was actually pretty close to doing that. The binary search steps would be 50, 75, 62, 56, 59 and she guessed 50, 75, 60, 55, 57, 58, 59.