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.

I agree with you; I came up with the same answer using probability equations and a lot of algebra. If anyone is interested, the equation for EV of the envelope game played with n guesses and a value between a and b is: (b(2^(n + 1)) – 2(4^n) + 3(2^n) – 1) / (b – a + 1) … For n = 8 (0-indexed, sue me), a = 1, b = 1000, it yields: 380.695

0-based indexing for life! Thanks for the formula. If I understand, it’s probably derived from the summation formula, (n^2 + n) / 2, but with a starting value determined by the max number minus 2^ the number of guesses minus 1, or something?

Huumm. Your best guess of 745 is definitely the correct answer, and I agree that it will have 511 successes. However I don’t think the expected value is 380.695. The expected value you find is simply the sum of all numbers between 490 and 1000, divided by 1000, which implies that with a guess of 745, you would find all these numbers but none below. According to my own simulations, you would indeed find 511 numbers, which would include 745 and all those above. However, below 745, you would find some numbers in 9 tries and not others. The exact set of numbers you would find in 9 tries depends on whether you round up or down when you reset your guess for each try. I don’t see in your code where that rounding occurs (I don’t know the Go language). But according to my simulations, if you round down, the expected value with a first guess of 745 is 318.063, and if you round up it is 318.632, simply because the exact set of correct answers you will get is slightly different.

I guess the crux of the question is this: with binary search over a domain that is too large for the number of attempts that we have, is the set of answers we can find with a given first guess contiguous or not? My answer is no. Yours seems to be yes.

The number of answers we can find is contiguous if we ensure they will be. What I’m doing is setting my minimum number to be 490, with the max of 1000. That’s a range of 511 numbers, which I can guarantee I will find. I am also guaranteeing that I will fail to find all 489 numbers below 490. You can see this in my calls to DoTrialRecursively(490, 1000).

This is essentially the same as 489 + DoTrialRecursively(1, 511). Make sense?

You’re right! I had not thought about setting the lower bound to 490 right from the start. My procedure still finds the best guess, but the wrong expected gain (too low relative to the optimum). Thanks for clarifying!

No problem. Thanks for reading and commenting.

I came up with the same number, first by trying every number from 0 to 1000, and doing binary searches on the rest, and then after seeing the result at 745…ooooohhhh! Of course! You only want to try the top 511 values.

It’s always nice to get confirmation from others on a guess. That way I’ll have company if we are wrong! (But I think we are right.)