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

• Learn $\LaTeX$. – Rodrigo de Azevedo Mar 17 '19 at 13:13
• Can you solve it already using "complex methods" then? ;-) – drhab Mar 17 '19 at 13:16

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.