Fdtxjr

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 $1leq xleq 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 $xin 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?.

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_jsubseteq S$ and player $A$ selecting a set
$P_jinleft Q_j,Q_j^Cright$. The player $A$ has to make sure
that for every $jgeq 1$ the following relation holds: $xin P_jcup
> P_j+1cupcdots 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 $xin X$.

(a) It suffices to prove that if $Ngeq 2^k+1$ then the player $B$ can
determine a set $S^primesubseteq S$ with $|S^prime|leq N-1$
such that $xin S^prime$.

Assume that $Ngeq 2^n+1$.

In the first move $B$ selects any set $D_1subseteq 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_2subseteq S$ such that $|D_2cap P_1^C|geq 2^k-2$ and
$|D_2^Ccap 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_jcap P_j^C|geq
> 2^k-j$ and $|D_j^Ccap 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_1cup cdots cup P_kright)^Cgeq
> 1$. Then $B$ chooses the set $D_k+1$ to be a singleton containing
any element outside of $P_1cupcdots 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=Ssetminus 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=Ssetminus 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_1setminus
  > left(P_k+2cdots P_2k+1right)right|geq 1,$$
  since $|S_1|geq 2^k$. However, now we have $$left|left(P_k+1cup P_k+2cupcdotscup
  > P_2k+1right)^Cright|geq 1,$$ and we may take
  $S^prime=P_k+1cup 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(fracpqright)^k_0leq
> 2cdot
> left(1-fracq2right)quadquadquadmboxandquadquadquad
> p^k-1.99^k> 1.$$

We will prove that for every $kgeq k_0$ if $|S|inleft(1.99^k,
> p^kright)$ 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_jcup
> P_j+1cupcdotscup P_j+k=S.$

Assuming that $S=1,2,dots, N$, the player $A$ will maintain the
following sequence of $N$-tuples:
$(mathbfx)_j=0^infty=left(x_1^j, x_2^j, dots, x_N^jright)$.
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{beginarrayrl 1,&mbox if iin P_j \ qcdot
> x_i^j, &mbox if inotin P_j.endarrayright.$$

The player $A$ can keep $B$ from winning if $x_i^jleq 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
$Tleft(mathbf x^jright)leq q^k$ for each $j$.

Notice that $Tleft(mathbf x^0right)=Nleq p^k < q^k$.

We will now prove that given $mathbf x^j$ such that $Tleft(mathbf
> x^jright)leq q^k$, and a set $D_j+1$ the player $A$ can choose
$P_j+1inleftD_j+1,D_j+1^Cright$ such that $Tleft(mathbf
> x^j+1right)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

$$Tleft(mathbf yright)=sum_iin D_j+1^C
> qx_i^j+left|D_j+1right|$$

$$Tleft(mathbf zright)=sum_iin D_j+1
> qx_i^j+left|D_j+1^Cright|.$$

Summing up the previous two equalities gives:

$$Tleft(mathbf yright)+Tleft(mathbf zright)= qcdot
> Tleft(mathbf x^jright)+ Nleq q^k+1+ p^k, mbox hence$$

$$minleftTleft(mathbf yright),Tleft(mathbf
> zright)rightleq fracq2cdot q^k+fracp^k2leq 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.