Guess my number for money
A secret whole number is chosen uniformly at random from 1 to 100. You guess repeatedly; after each wrong guess you are told whether the secret number is higher or lower. If you find it on guess , you receive dollars: 5 dollars on the first guess, 4 on the second, and so on, with a loss from the seventh guess on.
With the best guessing strategy, what is your expected payoff?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
The payoff is minus the number of guesses, so you want to minimise the expected number of guesses.
Any strategy is a binary search tree. How many numbers can be found with exactly guesses?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. The payoff is linear in the number of guesses, so the question is the smallest possible average number of guesses. At most numbers can be found on guess , and a balanced binary search reaches that bound.
Step 1: the bound. A guessing strategy is a binary search tree: the first guess is the root, and each answer “higher” or “lower” leads to one of two subtrees. So at most 1 number is found on the first guess, 2 on the second, 4 on the third, and in general on guess .
Step 2: the best case. To make the total number of guesses as small as possible, fill the first levels completely: numbers found within 6 guesses, and the remaining on guess 7. The total number of guesses over the 100 numbers is A balanced binary search (always guess the middle of the remaining range) achieves this.
Step 3: the payoff. The expected number of guesses is , so the expected payoff is
The twist. This assumes the number is chosen at random. If the host chooses it knowing your strategy, they will avoid the numbers you find early, and the game turns into a zero-sum game in which, with best play on both sides, you lose a little on average.