# 538 Riddler: Can You Best The Mysterious Man In The Trench Coat?

In this Riddler we have a shot to win some cash!

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?

Ok, so we can't really win some cash.  And honestly, if a mysterious man in a trench coat approaches me and starts to pull something out of his pocket I'm probably going to start walking briskly in the opposite direction.  But we can figure out how to maximize our expected winnings if we're ever presented with this odd opportunity.

You may already be familiar with the basic strategy to guess a number from a range: Start in the middle, and each time you're told "higher" or "lower" divide the remaining range in half until you've homed in on the target.  Since we're repeatedly dividing the range R by 2, this guarantees that we'll find the number in at most N guesses, where N = $\lfloor \log_2 R \rfloor + 1$.

So in this case we know we can find the exact amount of money in the envelope in at most $\lfloor \log_2 1000 \rfloor + 1 = 10$ guesses.  But we only get nine tries!  With nine guesses we can only guarantee to find the exact answer in a range of $2^9 - 1 = 511$ possible values.

The correct strategy, then, relies on the realization that if we have to guess between two or more equally likely options, our expected value will be greatest if we simply guess the greatest number.  Imagine, for instance, the envelope only contained either \$1 or \$2, and you only had one guess.  What would you do?  It's equally likely to be \$1 or \$2, but you win twice as much when you guess \$2 and get it right than when you guess \$1 and get it right.  So you'd maximize your winnings by just guessing \$2 every time.

Similar logic applies here.  We can only guarantee a win in a range of 511 numbers, so we'll guess among the greatest 511 numbers - that is, the range from 490 - 1000.  By employing this strategy, we're guaranteed to find the number if it's greater than or equal to 490, at the expense of guaranteeing we won't find it if it's less than that.  But we have to throw away 489 numbers anyway, so the optimal strategy is to throw away the 489 lowest possible values.

So our first guess would be the midpoint of 490 and 1000, which is 745.  By doing so, 48.9% of the time we'll win \$0, and the other 51.1% of the time we'll win \$745 on average, so our total expected winnings are:

$(0.489 * 0) + (0.511 * 745) \approx 380.70$