# Misc: Number Guessing

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.