Difference between revisions of "2012 IMO Problems/Problem 3"
(Created page with "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...") |
|||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
− | 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. | + | 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 <math>k</math> and <math>n</math> which are known to both players. |
− | At the start of the game the player A chooses integers x and N with | + | At the start of the game the player A chooses integers <math>x</math> and <math>N</math> with <math>1 \le x \le N</math>. Player A keeps <math>x</math> secret, and truthfully tells <math>N</math> to the player B. The player B now tries to obtain information about <math>x</math> by asking player A questions as follows: each question consists of B specifying an arbitrary set <math>S</math> of positive integers (possibly one specified in some previous question), and asking A whether <math>x</math> belongs to <math>S</math>. 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 <math>k+1</math> 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 | + | After B has asked as many questions as he wants, he must specify a set <math>X</math> of at most <math>n</math> positive integers. If <math>x \in X</math>, then B wins; otherwise, he loses. Prove that: |
− | (a) If | + | (a) If <math>n \ge 2^k</math> then B has a winning strategy. |
− | (b) There exists a positive integer | + | (b) There exists a positive integer <math>k_0</math> such that for every <math>k \ge k_0</math> there exists an integer <math>n \ge 1.99^k</math> for which B cannot guarantee a victory. |
+ | |||
+ | ==Solution to Part (a)== | ||
+ | |||
+ | It suffices to show that there is a winning strategy for <math>n = 2^k-1</math>, as a winning strategy for any <math>n \ge 2^k</math> easily gives a winning strategy for <math>n = 2^k-1</math>. | ||
+ | |||
+ | Player B first divides all integers <math>1</math> through <math>N</math> into <math>2^k</math> nonempty sets <math>T_s</math>, where <math>s</math> is some binary string of length <math>k</math>. On the <math>i^{th}</math> question for <math>1 \le i \le k</math>, player B asks whether the set containing <math>x</math> is labeled with a string that has a <math>1</math> in the <math>i^{th}</math> position. After asking these questions, there is one set that player A must indicate does not contain <math>x</math> at <math>k</math> times in a row; WLOG we may assume this set is <math>T_{00 \dots 0}</math>. | ||
+ | |||
+ | On the next question, B asks if <math>x \in T_{00 \dots 0}</math>. If A says 'no', then B can rule out <math>T_{00 \dots 0}</math>. If A says 'yes', then B asks if <math>x \in T_{100 \dots 0}</math>. If A says 'no', then B can rule out <math>T_{100 \dots 0}</math>. If A says 'yes', then B asks if <math>x \in T_{0100 \dots 0}</math>. If A says 'no', then B can rule out <math>T_{0100 \dots 0}</math>, while if A says 'yes', B can rule out <math>T_{1100 \dots 0}</math>. | ||
+ | |||
+ | In any case, B can ascertain that <math>x \not \in T_s</math> for some string <math>s</math>, thus reducing the number of possibilities for <math>x</math>. Player B can repeat this procedure as long as at least <math>2^k</math> elements remain, eventually reducing the number of possible values of <math>x</math> to at most <math>2^k - 1</math>. | ||
+ | |||
+ | ==Solution to Part (b)== | ||
+ | |||
+ | Take <math>k</math> sufficiently large so that there is some positive integer <math>n</math> with <math>n \ge 1.99^k</math> but <math>n+1 \le .001*1.999^{k+1}</math>. | ||
+ | |||
+ | Player A sets <math>N=n+1</math>. Let <math>f(i,m)</math> denote the number of times in a row that A has just indicated that <math>i \neq x</math>. In other words, if A indicates on the <math>m^{th}</math> step that <math>x</math> was in a set containing <math>i</math>, then <math>f(i,m)=0</math>, while if A indicates otherwise, we would have <math>f(i,m)=f(i,m-1)+1</math>. | ||
+ | |||
+ | At the <math>m^{th}</math> step, player A makes a decision so as to minimize the sum: <cmath>g(m)=\sum_{i=1}^N 1.999^{f(i,m)}</cmath> I claim that, by using this strategy, A will preserve the invariant that <math>g(m) < 1.999^{k+1}</math>. We can prove this by induction on <math>m</math>. | ||
+ | Note that initially, <math>g(0)=N<1.999^{k+1}</math>. | ||
+ | |||
+ | Suppose that <math>g(m-1) < 1.999^{k+1}</math>. Note that if B asks if <math>x \in S</math> for some <math>S \subset \{1,2,\dots,N\}</math>, then the two possibilities for <math>g(m)</math> are: <cmath>g_\text{in}(m)=N-|S|+1.999\sum_{i \in S} 1.999^{f(i,m-1)}</cmath> and <cmath>g_\text{out}(m)=|S|+1.999\sum_{i \not \in S} 1.999^{f(i,m-1)}</cmath> Note that <math>g_\text{in}(m)+g_\text{out}(m)=N + 1.999g(m-1)</math>. Therefore, we have that:<cmath>\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}</cmath> | ||
+ | |||
+ | 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 and which are known to both players.
At the start of the game the player A chooses integers and with . Player A keeps secret, and truthfully tells to the player B. The player B now tries to obtain information about by asking player A questions as follows: each question consists of B specifying an arbitrary set of positive integers (possibly one specified in some previous question), and asking A whether belongs to . 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 consecutive answers, at least one answer must be truthful.
After B has asked as many questions as he wants, he must specify a set of at most positive integers. If , then B wins; otherwise, he loses. Prove that:
(a) If then B has a winning strategy.
(b) There exists a positive integer such that for every there exists an integer for which B cannot guarantee a victory.
Solution to Part (a)
It suffices to show that there is a winning strategy for , as a winning strategy for any easily gives a winning strategy for .
Player B first divides all integers through into nonempty sets , where is some binary string of length . On the question for , player B asks whether the set containing is labeled with a string that has a in the position. After asking these questions, there is one set that player A must indicate does not contain at times in a row; WLOG we may assume this set is .
On the next question, B asks if . If A says 'no', then B can rule out . If A says 'yes', then B asks if . If A says 'no', then B can rule out . If A says 'yes', then B asks if . If A says 'no', then B can rule out , while if A says 'yes', B can rule out .
In any case, B can ascertain that for some string , thus reducing the number of possibilities for . Player B can repeat this procedure as long as at least elements remain, eventually reducing the number of possible values of to at most .
Solution to Part (b)
Take sufficiently large so that there is some positive integer with but .
Player A sets . Let denote the number of times in a row that A has just indicated that . In other words, if A indicates on the step that was in a set containing , then , while if A indicates otherwise, we would have .
At the step, player A makes a decision so as to minimize the sum: I claim that, by using this strategy, A will preserve the invariant that . We can prove this by induction on . Note that initially, .
Suppose that . Note that if B asks if for some , then the two possibilities for are: and Note that . Therefore, we have that:
This completes the induction. In particular, since at all times, A will never indicate that more that times in a row. So player B will never be able to rule out any element of and submit a set of integers that are guaranteed to contain .
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 |