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 $A$ chooses integers $x$ and $N$ with $1 \le x \le N.$ Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. 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 previuos 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$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that:
1. If $n \ge 2^k,$ then $B$ can guarantee a win.
2. For all sufficiently large $k$, there exists an integer $n \ge 1.99^k$ such that $B$ cannot guarantee a win.
IMO 2012: Day 1 Problem 3
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.
Re: IMO 2012: Day 1 Problem 3
The game can be re-formulated 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\} \). 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 of \( P_1\cup\cdots \cup P_k \). There are two cases now: \( 1^{\circ} \) 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. \( 2^{\circ} \) 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\lneq p\lneq q\lneq 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\gneq 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 S\\ q\cdot x_i^j, &\mbox{ if } i\not\in S. \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 \lneq 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/)
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 of \( P_1\cup\cdots \cup P_k \). There are two cases now: \( 1^{\circ} \) 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. \( 2^{\circ} \) 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\lneq p\lneq q\lneq 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\gneq 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 S\\ q\cdot x_i^j, &\mbox{ if } i\not\in S. \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 \lneq 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/)