2
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.