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.
On the second count (Baller implies the expected value is negative), if he's choosing randomly, then he's wrong. The expected value is $0.20 (calculated discretely using the code below). The code calculates the number of guesses for each value and an overall expected value assuming Ballmer chooses randomly.
use strict;
use warnings;
my @v = (0, 5, 4, 3, 2, 1, 0, -1, -2);
my $ev = 0;
my $ec = 0;
my @range = (1..100);
foreach my $r (@range) {
my $l = $range[0];
my $h = $range[$#range];
my $s = 0;
while (1) {
$s += 1;
my $g = int(($l + $h)/2);
if ($r == $g) {
print "$r found in $s steps (" . dollar($v[$s]) . ")\n";
$ev += $v[$s];
$ec += 1;
last;
}
if ($g < $r) {
$l = $g + 1;
next;
}
if ($g > $r) {
$h = $g - 1;
next;
}
}
}
$ev /= $ec;
print "Game expected value is " . dollar($ev) . "\n";
sub dollar {
my ($d) = @_;
my $f = (int($d) == $d)?'%d':'%.2f';
return sprintf("%s\$$f", ($d<0)?'-':'', abs($d));
}
This chart shows the expected winnings (or loss) depending on the number Ballmer chooses. The shape of the binary search can be seen in the chart itself.
A different way to think about the expected value and binary search is as follows:
1. On the first guess you choose 50 and win $5 with a probability of 1/100
2. On the second guess you choose 25 or 75 and win $4 with a probability of 2/100
3. On the third guess you choose 12, 37, 62 or 88 and win $3 with a probability of 4/100
4. On the fourth guess you choose 6, 18, 31, 43, 56, 68, 81 or 94 and win $2 with a probability of 8/100
5. And so on.
The gives the expected value as 5 * 1/100 + 4 * 2/100 + 3 * 4/100 + 2 * 8/100 + 1 * 16/100 + 0 * 32/100 + -1 * 37/100 (note the last term is the remaining possible numbers having reached the end of the binary search). That's 0.2.
Why was Ballmer wrong?
One possibility is that he didn't mean to have the $0 for 6 guesses. If he'd said "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, you pay me a buck, you pay me two, you pay me three" then the expected value is -$0.49.
