Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 IMO Problems/Problem 3"
 
Line 31: Line 31:
  
 
This completes the induction. In particular, since <math>g(m)<1.999^{k+1}</math> at all times, A will never indicate that <math>x\neq i</math> more that <math>k</math> times in a row. So player B will never be able to rule out any element of <math>\{1,2,\dots,N\}</math> and submit a set of <math>n</math> integers that are guaranteed to contain <math>x</math>.
 
This completes the induction. In particular, since <math>g(m)<1.999^{k+1}</math> at all times, A will never indicate that <math>x\neq i</math> more that <math>k</math> times in a row. So player B will never be able to rule out any element of <math>\{1,2,\dots,N\}</math> and submit a set of <math>n</math> integers that are guaranteed to contain <math>x</math>.
 +
 +
==See Also==
 +
 +
{{IMO box|year=2012|num-b=2|num-a=4}}

Latest revision as of 00:23, 19 November 2023

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 \le x \le N$. Player A keeps $x$ secret, 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 $n \ge 2^k$ then B has a winning strategy.

(b) There exists a positive integer $k_0$ such that for every $k \ge k_0$ there exists an integer $n \ge 1.99^k$ for which B cannot guarantee a victory.

Solution to Part (a)

It suffices to show that there is a winning strategy for $n = 2^k-1$, as a winning strategy for any $n \ge 2^k$ easily gives a winning strategy for $n = 2^k-1$.

Player B first divides all integers $1$ through $N$ into $2^k$ nonempty sets $T_s$, where $s$ is some binary string of length $k$. On the $i^{th}$ question for $1 \le i \le k$, player B asks whether the set containing $x$ is labeled with a string that has a $1$ in the $i^{th}$ position. After asking these questions, there is one set that player A must indicate does not contain $x$ at $k$ times in a row; WLOG we may assume this set is $T_{00 \dots 0}$.

On the next question, B asks if $x \in T_{00 \dots 0}$. If A says 'no', then B can rule out $T_{00 \dots 0}$. If A says 'yes', then B asks if $x \in T_{100 \dots 0}$. If A says 'no', then B can rule out $T_{100 \dots 0}$. If A says 'yes', then B asks if $x \in T_{0100 \dots 0}$. If A says 'no', then B can rule out $T_{0100 \dots 0}$, while if A says 'yes', B can rule out $T_{1100 \dots 0}$.

In any case, B can ascertain that $x \not \in T_s$ for some string $s$, thus reducing the number of possibilities for $x$. Player B can repeat this procedure as long as at least $2^k$ elements remain, eventually reducing the number of possible values of $x$ to at most $2^k - 1$.

Solution to Part (b)

Take $k$ sufficiently large so that there is some positive integer $n$ with $n \ge 1.99^k$ but $n+1 \le .001*1.999^{k+1}$.

Player A sets $N=n+1$. Let $f(i,m)$ denote the number of times in a row that A has just indicated that $i \neq x$. In other words, if A indicates on the $m^{th}$ step that $x$ was in a set containing $i$, then $f(i,m)=0$, while if A indicates otherwise, we would have $f(i,m)=f(i,m-1)+1$.

At the $m^{th}$ step, player A makes a decision so as to minimize the sum: \[g(m)=\sum_{i=1}^N 1.999^{f(i,m)}\] I claim that, by using this strategy, A will preserve the invariant that $g(m) < 1.999^{k+1}$. We can prove this by induction on $m$. Note that initially, $g(0)=N<1.999^{k+1}$.

Suppose that $g(m-1) < 1.999^{k+1}$. Note that if B asks if $x \in S$ for some $S \subset \{1,2,\dots,N\}$, then the two possibilities for $g(m)$ are: \[g_\text{in}(m)=N-|S|+1.999\sum_{i \in S} 1.999^{f(i,m-1)}\] and \[g_\text{out}(m)=|S|+1.999\sum_{i \not \in S} 1.999^{f(i,m-1)}\] Note that $g_\text{in}(m)+g_\text{out}(m)=N + 1.999g(m-1)$. Therefore, we have that:\[\min(g_{\text{in}}(m), g_{\text{out}}(m)) \le \frac{g_{\text{in}}(m) + g_{\text{out}}(m)}{2} = \frac{N + 1.999g(m-1)}{2} < \frac{.001*1.999^{k+1} +1.999^{k+2}}{2} = 1.999^{k+1}\]

This completes the induction. In particular, since $g(m)<1.999^{k+1}$ at all times, A will never indicate that $x\neq i$ more that $k$ times in a row. So player B will never be able to rule out any element of $\{1,2,\dots,N\}$ and submit a set of $n$ integers that are guaranteed to contain $x$.

See Also

2012 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_IMO_Problems/Problem_3&oldid=204552"