Solution #26

We will show that if n >= 2^k, then player B can guarantee a victory.

Suppose B, over a sequence of k+1 guesses, guesses the sets S₁,...,S_k+1. For the j-th guess, let T_j be S_j if A's answer is "yes", and {1,...,N} - S_j if A's answer is "no".

If A's j-th answer is truthful, then x is in T_j. Since at least one answer in a string of k+1 answers must be truthful, x must be in the union of T₁ through T_k+1.

Suppose now that B has more than 2^k uneliminated possibilities. We will show how B can eliminate another possibility. Given what was said above, it suffices to show that B can make a sequence of k+1 guesses such that the union of the T_j resulting from those guesses does not exhaust the uneliminated possibilities -- since x must be in that union, anything outside that union can be eliminated, and if there is at least one thing outside, B will have succeeded.

We now describe B's guessing procedure. Let S₁ be a subset of the uneliminated possibilities of size at least 2^k-1, and which also omits at least 2^k-1 of the uneliminated possibilities.

If A's answer is "yes", then B proceeds to pick S₂ so that S₂'s overlap with C(S₁) (the complement of S₁ -- the uneliminated possibilities not in S₁) is of size at least 2^k-2, and so that C(S₂)'s overlap with C(S₁) is also of size at least 2^k-2.

If A's answer is "no", B proceeds in the same way, but with C(S₁) replaced with S₁.

S₃ is determined in the same way, with S₁ in the previous method replaced by S₂.

B continues in this way through S_k. Given the construction, it follows that the size of the complement of the union of the S_j is at least 1. For his k+1-st guess, B then takes the singleton set of some member of that complement.

If A says "no" to that guess, then that single element can be eliminated, because the complement of that singleton is added to the union where x must be.

If A says "yes" to that guess, B repeats the above procedure starting with the uneliminated possibilities minus the single element on which the previous procedure ended. After k steps of that procedure, we are guaranteed that the complement of the determined sets, along with C(S_k+1), will be non-empty. We then eliminate anything in that complement.

So B can reduce any collection of more than 2^k uneliminated possibilities. Thus B can reduce the uneliminated possibilities to size 2^k. If B's allotted number of guesses n is at least 2^k, then, B is guaranteed victory with proper play.