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);
```