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.
I wanted an exact solution, so I solved this using dynamic programming. This approach solves the problem first for n=1, then n=2, then n= 3, etc.
The solution was somewhat surprising. While a binary solution approach works except for n = 3 (where you need to choose an interval of 1), you can sometimes get far away from picking half the numbers and still be optimal. The pattern looked interesting, so I solved it for up to n = 24, and I can guess the rest.
expected
n guesses best pick
1 1.00000 1
2 1.50000 1
3 2.00000 1
4 2.50000 1/2
5 2.80000 2/3
6 3.00000 3
7 3.28571 3/4
8 3.50000 3/4/5
9 3.66667 3/4/5/6
10 3.80000 4/5/6
11 3.90909 5/6
12 4.00000 6
13 4.15385 6/7
14 4.28571 6/7/8
15 4.40000 6/7/8/9
16 4.50000 6/7/8/9/10
17 4.58824 6/7/8/9/10/11
18 4.66667 6/7/8/9/10/11/12
19 4.73684 7/8/9/10/11/12
20 4.80000 8/9/10/11/12
21 4.85714 9/10/11/12
22 4.90909 10/11/12
23 4.95652 11/12
24 5.00000 12
So instead of a binary search, the following interesting strategy also works:
Pick 1 number if the number of remaining possibilities is between 1 and 4
3 numbers if the number of remaining possibilities is between 5 and 9
6 numbers if the number of remaining possibilities is between 9 and 18
12 numbers if the number of remaining possibilities is between 18 and 36
24 numbers if the number of remaining possibilities is between 36 and 72
48 numbers if the number of remaining possibilities is between 72 and 144
etc.
Two other notes:
1) Illustrating the dynamic programming approach.
Knowing the expected probability if there are between 1 and 4 numbers left,
I can calculate the best action to take for 5 remaining.
If I choose 1, the expected guesses = 1 + (1/5)*0 + (4/5)*2.5 = 3
If I choose 2, the expected guesses = 1 + (2/5)*1.5 + (3/5)*2 = 2.8
If I choose 3, the expected guesses = 1 + (3/5)*2 + (2/5)*1.5 = 2.8
If I choose 4, the expected guesses = 1 + (4/5)*2.5 + (1/5)*1 = 3.2
So, either 2 or 3 is optimal if there are 5 numbers remaining, and the expected guesses = 2.8
2) It may be obvious, but the selected range can be in the middle, instead of being at one end.
For instance, starting with 1 - 15, I can guess [4-9], which contains 6 numbers.
If the answer is no, then there are 9 possibles left, and I can guess [2-13],
an interval which includes 6 of the 9 remaining possibilities.
Full solution: 15 and beyond
