IMO 2012: Day 1 Problem 3

Discussion on International Mathematical Olympiad (IMO)
User avatar
Moon
Site Admin
Posts:751
Joined:Tue Nov 02, 2010 7:52 pm
Location:Dhaka, Bangladesh
Contact:
IMO 2012: Day 1 Problem 3

Unread post by Moon » Tue Jul 10, 2012 11:51 pm

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

gopugunda
Posts:1
Joined:Sat Jul 14, 2012 2:00 am

Re: IMO 2012: Day 1 Problem 3

Unread post by gopugunda » Sat Jul 14, 2012 2:05 am

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/)

Post Reply