# Misc Solution: Number Guessing

Original Problem

I'm thinking of a number between one and a hundred, you can guess and after each guess I say higher or lower. After the first guess, I give you five bucks, then 4, 3, 2, 1, 0 and then you owe me 1, 2, 3, and so on. Would you like to play?

## Solution

In theory, you could be lucky and find the right solution instantly and maximize the gain, but that's a chance of one out of a hundred. More practically, we calculate the expected value to decide if we would play.

Since the optimal solution is binary search, the number of guesses is bound to

$n = \lceil\log_2(100)\rceil = 7$

We assume the numbers to be uniformly distributed:

$X\sim\text{unif}(1, 100)$

The expected value is thus:

$\mathbb{E}(X) = \sum\limits_{x=1}^{100}p(x)\cdot w(x)$

Where $$p(x)=\frac{1}{100}$$ and the value to win $$w(x)$$ depends on it's position:

$w(50)=5, w(25)=w(75)=4, w(13)=w(38)=w(63)=w(88)=3, ...$

As such, the expected value per trial is

$\mathbb{E}(X) = \frac{1}{100}5 + \frac{2}{100}4 + \frac{4}{100}3 + \frac{8}{100}2 + \frac{16}{100}1 + \frac{32}{100}0 + \frac{37}{100}(-1) = 0.2$

Since the expected value is positive, it's okay to accept the game in the long run. The same could have been achieved with a simple monte carlo method:

function simulate(s, e, x, c) {

while (s <= e) {
var m = (s + e) >> 1;
if (c == m)
return x;
else if (c < m)
e = m - 1;
else
s = m + 1;
x--;
}
return 0;
}

var s = 0;
for (var i = 0; i < 100000; i++) {
s+= simulate(1, 100, 5, 1 + Math.random() * 100 | 0);
}
console.log(s / 100000);

« Back to problem overview