Can You Best The Mysterious Man In The Trench Coat?

A man in a trench coat pulls an envelope from his pocket. Inside is a whole number of dollars, anywhere from $1 up to $1,000. If you can name the exact amount, the money is yours. After each guess he tells you only whether you are too high or too low, and you get just nine guesses. What should your first guess be to maximise your expected winnings?

The Riddler, FiveThirtyEight (Dan Oberste)(original post)

Solution

The instinct is to binary-search the whole range and corner the number for certain. That instinct is wrong twice over, and seeing why hands you the answer. Nine yes/no splits can separate at most $2^9-1 = 511$ amounts with certainty, short of the $1{,}000$ on offer, so you cannot guarantee a win. And the prize is not a fixed sum but the amount itself, so a guaranteed $5 and a guaranteed $995 are not worth the same. The real task is to choose which amounts you lock up.

Two observations settle it.

Always reach for the top. On any final guess where several amounts remain equally possible, name the largest. It has the same chance of being right as the others and pays more when it is. The same logic scales: of the amounts you can secure, you want them to be the dear ones.

Each guess doubles your reach, plus one. Suppose with $n$ guesses you can pin down any block of $M$ consecutive amounts for certain. With one more guess, aim at the middle of a block of $2M+1$: whatever the man answers, “higher” or “lower” leaves a block of $M$, which your remaining $n$ guesses finish. One guess handles $M=1$, so $n$ guesses handle $$M = 2^n - 1 .$$ Nine guesses give a sure win over any $511$ consecutive amounts.

Since $511 < 1{,}000$, concede the cheapest $489$ amounts ($1 through $489), which you were going to lose somewhere anyway, and lock up the most valuable $511$: the block $490 through $1,000. Your first guess is the middle of that block, $$\frac{490 + 1000}{2} = \boxed{745}.$$ You win whenever the true amount lies in $490 to $1,000, with probability $511/1000$, and the amounts you win average to their midpoint $745, so your expected take is $\tfrac{511}{1000}\times 745 \approx \$380.70$. Throwing the poor end overboard is exactly what maximises the haul.

The computation

Encode the strategy and let it report the first guess and the expected winnings. Nine guesses secure the top $2^9-1$ amounts; keep that block, aim at its centre, and average the amounts won.

G, N = 9, 1000
secure = 2 ** G - 1                 # 511 amounts can be cornered for certain
win_lo = N - secure + 1            # concede the cheap tail, keep $490..$1000
first  = (win_lo + N) // 2         # middle of the winning block
exp    = sum(range(win_lo, N + 1)) / N
print(first, round(exp, 3))
# 745 380.695