I came across a fun game on social media recently, the rules are as follows:
- The player must guess a number between 1 and 100 (inclusive).
- If they guess it right, they get $5. If they guess it wrong, then they’re told if the number was higher or lower.
- They then guess again, but this time the amount for guessing correctly is decreased by $1.
- This continues until they guess correctly. The amount can go negative.
The question is: would you play the game?
To solve this we can use two approaches:
- Analytical: think through the solution and calculate an answer.
- Computational: figure out the optimal strategy, write a program which plays it and run many evaluations to approximate the solution.
SPOILER ALERT!
Analytical
This is a classic binary search problem. We want to optimise the information received from our guesses and the best way to do this is to split the remaining search space in half. Given this information, we can calculate how many guesses at each turn will be crossed out, all the way until we reach 100.
We start turn one by guessing 50, giving us 1 way chance at the correct answer and a reward of $5. On the second turn we now know if it’s above 50 or below it. If it’s below we could guess 25, splitting in half again. In total we would have 1x2=2 guesses with a reward of $4. This continues on with 4 guesses and $3, 8 guesses and $2, 16 guesses and $1 and 32 guesses and $0. At this point we’ve already made 63 guesses. So with the last guess we’ll only have 37 options.
To now work out if the game is worth playing we calculate the EV by summing the number of cases we would get a reward multiplied by the reward and then divide the whole thing by the 100 possible guesses. This yields 20c, so the game is worth playing as over time we would make money!
Computational
On the computational side we cam implement the binary search and run the simulations. This notebook has the code to do just that. Running for 100K simulations yields an estimated expected value of the game of $0.2004. This is just a 0.2% error from the analytical approach. Not bad!