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