Robert Eisele
Engineer, Systems Architect and DBA

# Misc: 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, you have an arithmetic progression:

$a_n = 5 - (n - 1)$

Since the optimal solution is binary search, we're bound to

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

As such, the expected value is

$\mathbb{E} = a_n = a_{\lceil\log_2(100)\rceil} = a_{7} = -1$

Therefore, it's not a good idea to play the game.

Go to overview