The game goes like this:
I pick a random number between 1 and 1000. You have to guess what the number is. If you guess right, you get 1150. If you guess wrong, you lose 98. You may also ask for any number of hints, but the first hint will cost you 2, the second hint will cost 4, third will cost 8, etc. The hints are only yes/no questions. What is the optimal strategy?
I thought about doing this with binary search but that uses too many hints. However binary search removes half the values every time and I can't figure out something that is more efficient. Is there a better strategy?
Best Answer
Added: I now think you should be able to guess as many times as needed, paying $98$ for each wrong guess. Under this rule you should play. Do $7$ stages of binary search, costing $254$ and leaving you $7$ (with probability $\frac {21}{125}$) or $8$ (with probability $\frac {104}{125}$) possibilities left. Now guess the remaining numbers one by one. You expect to guess half the wrong numbers before the right one, so your expectation is $1150-\frac {21}{125}\cdot 3\cdot 98 -\frac {104}{125}\cdot \frac 72 \cdot 98-254=561.232$. Your best result is $1150-254=896$ and your worst is $1150-254-7\cdot 98=210$. You don't want to ask one more search question because that costs $256$ and only saves you about two guesses for $98$. You don't want to start guessing after six search questions because that saves $128$ but adds about four more expected wrong guesses.
This was written assuming you only got one guess and either got $1150$ if it was right and paid $98$ if it was wrong. Either way you stopped. You clearly don't want to ask the last question, as it costs $1024$ to get from $2$ possibilities to $1$ (here we consider the numbers go to $1024$ so you always have two left after nine guesses. It won't change much). You improve your expected payout from $\frac 12(1150-98)=526$ to $1150$. If you do binary search for $k$ questions you have $\frac {1024}{2^k}$ possibilities left and spend $2^{k+1}-2$. You then guess among the remaining possibilities. Your expected gain is $1150 \cdot \frac {2^k}{1024}-98\left(1-\frac {2^k}{1024}\right)-2^{k+1}+2$. I find asking any question lowers your expectation, so the best you can do is guess right out of the box. Going back to $1000$ possibilities, the expected payout is then $\frac {1150-98\cdot 999}{1000}=-96.752$. Asking one question lowers this to $\frac {1150-499\cdot 499}{500}-2=-97.504$ Don't play the game.