Let’s play a game!
Here’s a math game you can play while keeping up social distancing. Find someone to play with and read on.
The game:
You are given $20, and you must guess a whole number between 1 and 700. For each incorrect guess you make, you must pay $1, and then you are told if you were over or under the correct number. If you guess the number, you get to keep the money you have left.
Challenge 1: Can you guarantee a profit on this game? What's the greatest profit you can guarantee even if you are very unlucky on your guesses?
A Twist:
You are playing the same game as before, except now it has a twist: each time you guess, you pay $1 if you were under the correct number, but you pay $2 if you were over the correct number!
Challenge 2: Now can you guarantee a profit on the game? What's the greatest profit you can guarantee even if you are very unlucky?
Before diving into the solutions, we hope you’ll take some time to work on the answers. Spoiler alert: We’re going to show you the answers up front before our in-depth solutions, so you can try to match or even beat our answers.
Answer to challenge 1: Yes. We can guarantee a profit of at least $11.
Answer to challenge 2: Yes. We can guarantee a profit of at least $7.
Solution to Challenge 1:
If we randomly guessed 20 different (whole) numbers between 1 and 700, we would have less than a 3% chance of correctly predicting (since 20/700 = 0.0285…). Thus, we’re going to have to be a bit creative and use that we’re told how our guesses compare to the correct numbers.
Since I’m not sure about how to solve this problem, let’s consider a simpler problem and suppose instead the correct number lies between 1 and 30. We still can’t guess each possible number, so let’s think about a few possibilities for the first guess:
Table 1: Outcomes of possible first guesses if correct number between 1 and 30
Ah… we see that each incorrect guess leads us to a smaller collection of possibilities: the “Under” numbers or the “Over” numbers. So, to guess the correct number, we either need to get lucky with one of our guesses, or reduce down to 1 possibility then guess that 1 number. Since we might be very unlucky, let’s try to figure out a way to get down to just 1 possibility.
Back to the original problem, what’s the best first guess to reduce the number of possibilities? Well, if we choose a middle number, like 350, then we would cut the number of possibilities in half (or correctly guess). This means that the correct number is either between 1 and 349 (for “over), or it’s between 351 and 700 (for “under”).
Let’s repeat this. If the number is between 1 and 349, we can choose the middle number 175, which will leave us with 174 possibilities (if 175 is incorrect). On the other hand, if the number is between 351 and 700, we can choose a middle number 525, which will leave us with 174 or 175 possibilities (if 525 is incorrect).
So, it will cost at most $9 to guess the correct number between 1 and 700, which means we are guaranteed a profit of at least $11.
In general, suppose we were asked to guess a number between 1 and n. Then, the max cost to predict the right number is one less than the number of times we can halve n before arriving at a result strictly less than 1, which is:
log2(n), rounded down to the nearest whole number.
For example, log2(700) = 9.45…, which rounds down to $9 as we found above. Ah, I knew there was a reason we used to slog with logs!
Small tangent, if someone ever comes up to you at a party asking you to play this game with $20 and guessing a number between 1 and a million, you’re guaranteed to win at least $1 since
log2(1,000,000) = 19.93…,
which rounds down to 19!! (This is a really, really fun party game by the way.)
If you’d like to learn more about this search strategy and even use programming to code it up, you can look up “binary search algorithm”.
Solution to Challenge 2:
For the second challenge, we could try the same algorithm of halving the number of possibilities with each guess. If we do this, we can deduce that we’re guaranteed to earn a profit. Why? Well, each wrong guess costs at most $2. Since our solution to Challenge 1 required at most 9 wrong guesses, finding the right number here will cost at most $2 x 9 = $18. Hence, we will earn a profit of at least $2!
But that estimate seems… rough. Some guesses cost only $1. How can we use this fact to arrive at a better outcome?
Well, this problem seems… tough. So, let’s try a “bottom-up” approach of looking at some base cases, and hopefully find a pattern we can knead into a solution. Let’s try to solve the problem:
Starting with $x, what is the maximum whole number n(x) such that we can predict any number from 1 to n(x)?
Start with $0: We can’t afford to be wrong with any guess, so we can correctly predict only between 1 and 1, and n(0) = 1.
Start with $1: We will only be able to pay if our wrong guess is under, so n(1) = 2. We can predict 1 with our first guess, and then if we’re under, we can correctly guess 2.
Start with $2: Now things get more interesting because we can use our previous work. If our first guess is:
Under: We will have $1 remaining, from which we can predict correctly if there are at most n(1) = 2 possibilities remaining.
Over: We will have $0 remaining, from which we can win if there is at most n(0) = 1 possibility remaining.
This means that we should guess 2 with our first guess, and n(2) = 4.
Ah, we’re getting somewhere! Let’s try again.
Start with $3: If our first guess is:
Under: We will have $2 remaining, which we can predict from n(2) = 4 possibilities.
Over: We will have $1 remaining, which we can predict from n(1) = 2 possibilities.
This means that we should predict 3 = n(1) + 1 with our first guess, and n(3) = n(2) + n(1) + 1 = 7.
In general, suppose we start with $x, where x > 2. If our first guess is:
Under: We will have $(x-1) remaining, which we can correctly predict from n(x-1) possibilities.
Over: We will have $(x-2) remaining, which we can correctly predict from n(x-2) possibilities.
Hence, we should predict n(x-2) + 1 with our first guess, and
n(x) = n(x-1) + n(x-2) + 1.
Wow, this recurrence relation is like a modified Fibonacci sequence. Neato!
We can then use a table to solve our problem:
And there we have it! 700 is between 609 and 985, so it will cost at most $13 to correctly guess. This guarantees a profit of at least $7 no matter our unluckiness, a big improvement over the $2 profit we were guaranteed by repeated halving!
If you enjoyed this problem here are some additional problems to keep the fun going:
Additional question 1: What’s the highest profit that could be guaranteed if it cost $2 each time we were wrong and were asked to guess a number between 1 and 700? Are we guaranteed to earn a profit if it costs $1 each time we’re under and $3 each time we’re over?
Additional question 2: For Challenge 1, if we assume the machine randomly picks a number between 1 and 700, what is the average profit we expect to earn?
Additional question 3: Can you find a closed formula for nx in Challenge 2 using:
n(x) = n(x-1) + n(x-2) + 1, n(0)= 1, n(1) = 2?