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
re: some thoughts -- cases of small n by Charlie)
I agree with all you said. In the case of 3, one should clearly chose the floor - i.e. query the singleton first - and then process is tantamount to {1}, {2}, {3}. And, with N=4, the binary approach is identical in average steps to individual queries (and I am guessing inferior to using {1,2,3} or {1} as the starting query.)
But when the remaining number of candidates is odd (as in N=3), is it _always_ optimal to query the smaller (floor) group first? The larger group does have a higher likelihood of containing the solution. Does it matter which group is the odd one and which is the even one? I don't know for which odd N's the floor is the better choice. So this is why I say for N=15 the above questions might be relevant.
Edited on October 23, 2019, 3:19 pm
re(2): some thoughts -- cases of small n
