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