From the book The Riddler, by Oliver Roeder comes an excellent little puzzle about a man in a trench coat handing you money. Interested?
The Problem
A man in a trench coat approaches you and pulls an envelope from his pocket. He tells you that it contains a sum of money in bills, anywhere from $1 up to $1,000. He says that if you can guess the exact amount, you can keep the money. After each of your guesses, he will tell you if your guess is too high or too low. But! You only get nine tries. What should your first guess be to maximize your expected winnings?
Solution
Search strategy
Let \(g\) be the number of guesses you have and let \(n\) be the number of different values to guess from. In our problem \(g = 9\) and \(n = 1000\).
I started this problem by thinking about simpler cases where you could guarantee winning the money. For example, if \(g = 1\) and \(n = 1\), you can obviously win the money by using your guess on the only possible value.
Next I thought about what happens if \(g = 2\)? You can guarantee winning for up to \(n = 3\) by first guessing the middle value. If you’re right, you’ve won, and if you’re wrong, you’ll be told higher or lower, turning the problem back into our \(g =1\), \(n = 1\) case.
If \(g = 3\), then we can solve for up to \(n = 7\) by using our first guess to split the 7 values in half, making two groups of 3. Depending on if the man says higher or lower, we solve the indicated group of 3 with our remaining 2 guesses.
Using this technique of successively dividing our values in half (also called binary search), it’s straightforward to show that if \(max(g)\) represents the value of \(n\) for which we can guarantee finding a solution in \(g\) guesses, then
$$max(g) = 2^g-1$$
Optimizing for expected value
So, in our problem when \(g = 9\), we can guarantee a solution when \(n = 2^9-1 = 511\). Unfortunately for us, n = 1000. So what should we do?
Since we care about the expected value of our winnings, we would like to guess correctly more often when the value of the envelope is high, and we care less about guessing correctly when the value in the envelope is low. Thus, let’s just perform binary search on the highest 511 values ($490 to $1000), and give up completely on the other values($1 to $489).
Note that we can’t do any better than a \(\frac{511}{1000}\) chance of winning, so if we’re going to lose some of the time, we might as well lose when the envelopes are worth the least!
Doing binary search on $490 to $1000 will make our first guess \(\frac{490 + 1000}{2}\) or $745.
This approach will correctly find the value of the envelope if it’s between $490 to $1000, and fail otherwise. Thus the expected value is…
$$\frac{1}{1000}\sum_{n=490}^{1000} n = $380.695$$
Or more intuitively, notice that our chance of winning is \(\frac{511}{1000}\) and our average winnings are $745. Thus we can also compute our expected value as…
$$\frac{511}{1000} \times $745 = $380.695$$