Guess the number. Maximizing expected winnings?

Question

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 dollar up to 1,000 dollars. 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?

Answer 1

A binary tree of depth $N$ can have up to $$ \sum_{k=0}^N 2^k = 2^{N+1} - 1 $$ nodes. Here we have $N = 9$ and thus can store up to $1023$ values.

So $9$ questions are enough to drill down to any dollar value between $1$ and $1000$. We have a little wiggle room , but we take simply $512$.

Answer 2

My old answer is the right idea but the wrong answer.

New strategy. If it is 489 or below we will not guess it. If it is 490 or above, we will.

For our ninth guess we want to have only one possible guess. If the amount is 490 or above it will be the correct guess. Otherwise we have resigned to losing.

For our eight guess we will have 3 possible guesses. We will guess the middle amount. Either it is right. It is high. Or it is lower. If it is right we are done. If it isn't there are 1 possible guess remaining. That will be our 9th guess.

For our 7th guess we will have 7 possiblie guesses. We will guess the middle. If we are wrong the 3 remaining possibilities will form our 8th guess.

And so one.

For our 6th guess we guess the middle of 15. Our 5th the middle of 31. Our 4th, the middle of 63. Our 3rd, the middl of 127. Our second, the middle of 255. Our first the middle of 511.

Our first guess will be 746. If the amount is anywhere between 490 and 1000 we will guess it by 9 guesses. Otherwise we won't.

Our expected return is $511/1000*746 = \$381$.

==== old answer ====

Okay, you can't guess with certainty. 9 guesses will divide the information into 512 cases so you will only have about a 1 in 2 chance of making it.

Since the puzzle is to maximize expected return, we should guess so that if we make it we will win the highest amount of money. So if we don't make it we should fail to guess the lowest amount. So we should decide as we have a 1-2 (roughly) chance of losing, we should make it so that we lose only if there is less than 500 dollars and we will win if there is more. Thus our expected return will be about 375 dollars.

So we should first guess should be \$744 ($1000 - 2^8$). If we guess low we up the guess by \$256 ($2^8$) and if we guess high we lower by \$256. Each guess we hone in by half. If the amount is between \$489 and \$1000, we will guess it. If it isn't we won't. So our expected return is $512/1000 * (1000 + 489)/2 = \$381$