for N=100, 10 questions to ask

I guess here is the optimal procedure:
At each stage, when there are m 0-strikes and n 1-strikes, we should try to divide these two sets as evenly as possible, i.e.
(m,n) = (floor(m/2), ceil(n/2)) + (ceil(m/2), floor(n/2))

But, to avoid proving this is the optimal case, I will assume Bob divide the two sets slightly uneven:
(m,n) = (floor(m/2), floor(n/2)) + (ceil(m/2), ceil(n/2))
and each time, he is unlucky to get the smaller set stroke out.

For N = 100, here are the procedure in the worst senario (the first column is the number of 0-strikes, the second is the 1 strikes, the ith row is the state after i questions):
50 50
25 50
13 37
7 25
4 16
2 10
1 6
0 4
0 2
0 1
So, after 10 questions, we have only one number left, which must be the number picked by Alice.

所有跟帖： 

• I think that there is a mistake at the eighth guess -ettubrute- ♂ (284 bytes) () 06/12/2008 postreply 20:36:40