Hello, and welcome to my look at 538’s Riddler. Last week I managed to get the correct answer using a Monte Carlo, and Go’s really nice NormFloat64 function. Commenters squareandrare, mathisallaround, and guyshavit all shared voodoo mathy ways to get the answer, which I appreciated, including the chi-squared distribution. Thanks for reading and commenting!

This week’s Riddler concerns talking to strange men in trench coats.

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?

Obviously if a man in a trench coat offers you money the answer is to run. But let’s answer the question anyway. My immediate first guess for this was $744, which was wrong. But only because I’m pretty sure the answer is $745.

How did I get this number? Well, the guessing game where someone tells you whether your guess is higher or lower is a classic example of a binary search, which is one of the most important algorithms in computer science. With 9 guesses, we know that we can guarantee coverage of 511 (2^9 – 1) values. That leaves 489 values for which we are going to not be able to guess the right answer. Sad!

Now the question is, which values do we want to cover? Well, without any knowledge to the contrary we should assume that all values between $1 and $1000 are equally likely, assuming our trench-coated friend is trustworthy (and aren’t they all?). So since there is just as much chance that there is $1000 in the envelope as $1, we might as well make sure we cover the top 511 values.

Put another way, imagine the man in the trench coat offers you only one guess. What should you do? (Run.) Well, you have just as much chance of being right by guessing $1000 as $1, so guess $1000 and hope for the best. Your expected value (EV) is the odds of being right times the payout, so if you guess $1000, your EV is $1. If you guess $1, your EV is $.001, which is… less.

So covering the top 511 values would be everything from $490 to $1000. The middle value between those two numbers is $745. I wrote some code to show this, and then ran 1000 simulations for each amount of money that is in the envelope. Here it is in Go:

package main // Jon Wiesman, somedisagree.com import "fmt" func binSearchRecursive(min, max, value, guesses int) bool { if guesses == 0 { return false } if min > max { return false } guess := (min + max) / 2 if guess == value { return true } if guess < value { return binSearchRecursive(guess+1, max, value, guesses-1) } else { return binSearchRecursive(min, guess-1, value, guesses-1) } return false } func binSearchIterative(min, max, value, guesses int) bool { for ; guesses > 0; guesses-- { if min > max { return false } guess := (min + max) / 2 if guess == value { return true } if guess < value { min = guess + 1 } else { max = guess - 1 } } return false } func DoTrialRecursively(min, max int) { trials := 1000 found := 0 totalEarned := 0 for i := 1; i <= 1000; i++ { if binSearchRecursive(min, max, i, 9) { found++ totalEarned += i } } fmt.Printf("Recursively, with first value = %d, %d/%d success, total earned = %d\n", (min+max)/2, found, trials, totalEarned) } func DoTrialIteratively(min, max int) { trials := 1000 found := 0 totalEarned := 0 for i := 1; i <= 1000; i++ { if binSearchIterative(min, max, i, 9) { found++ totalEarned += i } } fmt.Printf("Iteratively, with first value = %d, %d/%d success, total earned = %d\n", (min+max)/2, found, trials, totalEarned) } func main() { DoTrialIteratively(489, 1000) DoTrialIteratively(490, 1000) DoTrialRecursively(490, 1000) DoTrialRecursively(491, 1000) }

And here’s a link to the Go playground for this code where you can play with the numbers and run it in your browser. Doing so gives this output:

Iteratively, with first value = 744, 511/1000 success, total earned = 380184 Iteratively, with first value = 745, 511/1000 success, total earned = 380695 Recursively, with first value = 745, 511/1000 success, total earned = 380695 Recursively, with first value = 745, 510/1000 success, total earned = 380205

So your EV if you start with a first guess of $745 is $380.695, and you’ve got a 51.1% chance of making some money. Pretty good deal. (You should still run.)

My binary search function differs from most binary searches in one small way. Here, I pass in the number of guesses and decrement it with each recursive call. When it reaches 0, I return false. I used recursion here first because it’s easiest for me to write but iteration might be easier for non CS people to follow so I wrote it iteratively as well. Both work.

If you call either function with min and max at $1 and $1000, respectively, giving a first guess of $500, you will still succeed 511 times but your expected value would only be $255.175. This is because the 489 missed values would be evenly distributed instead of all at the bottom. Try it.

So, that’s my answer: $745. I believe it is right unless there is some method to guarantee more than 511 found values with only 9 guesses. As always, I’m always willing to admit I am wrong so if I am, I’d love to know.

Thanks for reading.