IMO 2012 Problem 3 part 2

The solution at the bottom is the official one. Just so that in the future I know that I once understand it. I do not know how to come up with the idea.

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

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

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

$A$ makes $N=n$. For every $i\in[n]$, let $m_i$ be the number of consecutive answers that is a lie if $x=i$. $A$'s strategy is to minimize 

$$y=\lambda^{m_1}+\lambda^{m_2}+\dots+\lambda^{m_n}$$

where $\lambda>1$ is to be determined later.

Our goal is to show that $y\le z<\lambda^{k+1}$ for some $z>0$, so that every $m_i<k+1$. Note that together with $z\ge n$, we can prove that $y\le z$ inductively if $$z\lambda/2+n/2\le z,\text{ or }\frac{n}{2-\lambda}\le z.$$

Hence we further require that $\lambda<2$ and $$\frac{n}{2-\lambda}<\lambda^{k+1}.$$

To sum it up, we hope that for sufficiently large $k$ there is an integer $n$ such that

$$1.99^k\le n<(2-\lambda)\lambda^{k+1}.$$

This is achievable for every $\lambda\in(1.99,2)$.