Combinatorics question from IMO 2012

Question

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?.

Answer 1

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.