I am thinking of an integer in the interval [1-15]. You are to try to guess it by telling me intervals and I will tell you if my number lies in that interval.
For example if my number is 6 and you guess [6-9] I will tell yes but if you guess [7-11] I will tell you no but not if my number is higher or lower.
You win by guessing an interval of just one number and that number is my number. Find a strategy that minimizes the expected number of guesses.
(In reply to
Full solution: 15 and beyond by Steve Herman)
Thanks for the in-depth treatment. It was bothering me to have to assume the binary method was the the only game in town. But I believe your conclusion is that: it can be equaled with other bracketing schemes, but not beaten. If this true holds for all N, it is a refutation of the claim of the (somewhat unreadable) paper I cited of the superiority of their quadratic method. While people spend a lot of effort optimizing other aspects of such searches (like speed and storage), if "mean number bracketing steps" is alone the parameter to be optimized, then I think you are saying even for low N, the binary scheme can not be beat. If it could be beat, this would be important in computer science.
Finally, there is one part of this puzzle that I find idiosyncratic: in some searches, the contestant may learn the answer, but must still take one last step to announce the answer. In other cases the contestant does not know the answer but finds it on the last step. If the challenge is changed to: "how many steps to simply to know the answer?", would your results change?
Edited on October 24, 2019, 6:04 pm
re: Full solution: 15 and beyond
