Combinatorics question from IMO 2012 This is the 3rd problem of the International Mathematical Olympiad 2012.

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 the player $A$
   chooses integers $x$ and $N$
   with $1\leq x\leq N$. Player $A$ keeps $x$ secretly, and truthfully tells $N$ to the player $B$. The 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\in X$, then $B$ wins; otherwise, he loses. Prove that:
(a) If $\geq2k$
   then $B$ has a winning strategy.
(b) There exists a positive integer $_0$
   such that for every $\geq_0$
   there exists an integer $\geq1.99$ 
   for which  cannot guarante a win.

How to solve this question without using complex methods?.
 A: All but the youngest IMO problems have solutions on imomath.com. I've reproduced verbatim from here:

The game can be reformulated in an equivalent one: The player $A$
  chooses an element $x$ from the set $S$ (with $|S|=N$) and the player
  $B$ asks the sequence of questions. The $j$-th question consists of
  $B$ choosing a set $D_j\subseteq S$ and player $A$ selecting a set
  $P_j\in\left\{ Q_j,Q_j^C\right\}$. The player $A$ has to make sure
  that for every $j\geq 1$ the following relation holds: $x\in P_j\cup
> P_{j+1}\cup\cdots \cup P_{j+k}$.
The player $B$ wins if after a finite number of steps he can choose a
  set $X$ with $|X|\leq n$ such that $x\in X$.
(a) It suffices to prove that if $N\geq 2^k+1$ then the player $B$ can
  determine a set $S^{\prime}\subseteq S$ with $|S^{\prime}|\leq N-1$
  such that $x\in S^{\prime}$. 
Assume that $N\geq 2^n+1$.
In the first move $B$ selects any set $D_1\subseteq S$ such that
  $|D_1|\geq 2^{k-1}$ and $|D_1^C|\geq 2^{k-1}$. After receiving the set
  $P_1$ from $A$, $B$ makes the second move. The player $B$ selects a
  set $D_2\subseteq S$ such that $|D_2\cap P_1^C|\geq 2^{k-2}$ and
  $|D_2^C\cap P_1^C|\geq 2^{k-2}$. The player $B$ continues this way: in
  the move $j$ he/she chooses a set $D_j$ such that $|D_j\cap P_j^C|\geq
> 2^{k-j}$ and $|D_j^C\cap P_j^C|\geq 2^{k-j}$. 
In this way the player $B$ has obtained the sets $P_1$, $P_2$,
  $\dots$, $P_k$ such that $\left(P_1\cup \cdots \cup P_k\right)^C\geq
> 1$. Then $B$ chooses the set $D_{k+1}$ to be a singleton containing
  any element outside of $P_1\cup\cdots \cup P_k$. There are two cases
  now:
  
  
*
  
*The player $A$ selects $P_{k+1}=D_{k+1}^C$. Then $B$ can take    $S^{\prime}=S\setminus D_{k+1}$ and the statement is proved.
  
*The player $A$ selects $P_{k+1}=D_{k+1}$. Now the player $B$ repeats    the previous procedure on the set $S_1=S\setminus D_{k+1}$
  to obtain    the sequence of sets $P_{k+2}$, $P_{k+3}$, $\dots$,
  $P_{2k+1}$. The    following inequality holds: $$\left|S_1\setminus
> \left(P_{k+2}\cdots    P_{2k+1}\right)\right|\geq 1,$$
     since $|S_1|\geq 2^k$. However, now we have $$\left|\left(P_{k+1}\cup P_{k+2}\cup\cdots\cup   
> P_{2k+1}\right)^C\right|\geq 1,$$ and we may take
$S^{\prime}=P_{k+1}\cup \cdots \cup P_{2k+1}$.
  
  
  (b) Let $p$ and $q$ be two positive integers such that $1.99< p< q<
> 2$. Let us choose $k_0$ such that $$\left(\frac{p}{q}\right)^{k_0}\leq
> 2\cdot
> \left(1-\frac{q}2\right)\quad\quad\quad\mbox{and}\quad\quad\quad
> p^k-1.99^k> 1.$$
We will prove that for every $k\geq k_0$ if $|S|\in\left(1.99^k,
> p^k\right)$ then
there is a strategy for the player $A$ to select sets $P_1$, $P_2$,
  $\dots$ (based on sets $D_1$, $D_2$, $\dots$ provided by $B$) such
  that for each $j$ the following relation holds: $P_j\cup
> P_{j+1}\cup\cdots\cup P_{j+k}=S.$
Assuming that $S=\{1,2,\dots, N\}$, the player $A$ will maintain the
  following sequence of $N$-tuples:
  $(\mathbf{x})_{j=0}^{\infty}=\left(x_1^j, x_2^j, \dots, x_N^j\right)$.
  Initially we set $x_1^0=x_2^0=\cdots =x_N^0=1$. After the set $P_j$ is
  selected then we define $\mathbf x^{j+1}$ based on $\mathbf x^j$ as
  follows:
$$x_i^{j+1}=\left\{\begin{array}{rl} 1,&\mbox{ if } i\in P_j \\ q\cdot
> x_i^j, &\mbox{ if } i\not\in P_j.\end{array}\right.$$
The player $A$ can keep $B$ from winning if $x_i^j\leq q^k$ for each
  pair $(i,j)$. For a sequence $\mathbf x$, let us define $T(\mathbf
> x)=\sum_{i=1}^N x_i$. It suffices for player $A$ to make sure that
  $T\left(\mathbf x^j\right)\leq q^{k}$ for each $j$.
Notice that $T\left(\mathbf x^0\right)=N\leq p^k < q^k$.
We will now prove that given $\mathbf x^j$ such that $T\left(\mathbf
> x^j\right)\leq q^k$, and a set $D_{j+1}$ the player $A$ can choose
  $P_{j+1}\in\left\{D_{j+1},D_{j+1}^C\right\}$ such that $T\left(\mathbf
> x^{j+1}\right)\leq q^k$. 
Let $\mathbf y$ be the sequence that would be obtained if
  $P_{j+1}=D_{j+1}$, and let $\mathbf z$ be the sequence that would be
  obtained if $P_{j+1}=D_{j+1}^C$. Then we have 
$$T\left(\mathbf y\right)=\sum_{i\in D_{j+1}^C}
> qx_i^j+\left|D_{j+1}\right|$$
$$T\left(\mathbf z\right)=\sum_{i\in D_{j+1}}
> qx_i^j+\left|D_{j+1}^C\right|.$$
Summing up the previous two equalities gives:
$$T\left(\mathbf y\right)+T\left(\mathbf z\right)= q\cdot
> T\left(\mathbf x^j\right)+ N\leq q^{k+1}+ p^k, \mbox{ hence}$$
$$\min\left\{T\left(\mathbf y\right),T\left(\mathbf
> z\right)\right\}\leq \frac{q}2\cdot q^k+\frac{p^k}2\leq q^k,$$
because of our choice of $k_0$.

I welcome any copyright-motivated edits to this answer before I have time to make my own.
