IMO 2012 Problem 3 part 1

The second half of the problem is too hard for me to solve.

==============

The liar's guessing game is a game played between two players \(A\) and \(B\) The rules of the game depend on two positive integers \(k\) and \(n\) which are known to both players.

At the start of the game \(A\) chooses integers \(x\) and \(N\) with \(1 \le x \le N\). Player \(A\) keeps \(x\) secret, and truthfully tells \(N\) to player \(B\). Player \(B\) now tries to obtain information about \(x\) by asking player \(A\) questions as follows: each question consists of \(B\) specifying an arbitrary set \(S\) of positive integers (possibly one specified in some previous question), and asking \(A\) whether \(x\) belongs to \(S\). Player \(B\) may ask as many questions as he wishes. After each question, player \(A\) must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any \(k+1\) consecutive answers, at least one answer must be truthful.

After \(B\) has asked as many questions as he wants, he must specify a set \(X\) of at most \(n\) positive integers. If \(x\) belongs to \(X\) then \(B\) wins; otherwise, he loses. Prove that:

1. If \(n \ge 2^k,\) then \(B\) can guarantee a win.
2. For all sufficiently large \(k\) there exists an integer \(n \ge (1.99)^k\) such that \(B\) cannot guarantee a win.

Proposed by David Arthur, Canada

==============

Solution to part 1:

Formally, the only possible inference that \(B\) could make is: assume \(k+1\) consecutive answers are all lies, then take the negation of the conclusion. This could be used to solve part 2 as well.

When there are more than \(2^k\) candidates, let \(y\) be a fixed member of it. Now \(B\) could ask if \(y=x\). If the answer is yes, assume it's a lie and focus on the rest \(\ge 2^k\) candidates: in the next \(k\) questions binary partition these numbers. \(B\) can then at least eliminate one of them.

If the answer to whether \(y=x\) is no, \(B\) will keep asking the same question until the answer becomes yes. If it doesn't in \(k+1\) rounds then \(B\) can eliminate \(y\).

Q.E.D.