IMO 2012 #3
by Wolstenholme, Oct 29, 2014, 2:29 AM
The liar's guessing game is a game played between two players 
and 
. The rules of the game depend on two positive integers 
and 
which are known to both players.
At the start of the game chooses integers 
and 
with 
Player keeps secret, and truthfully tells to player . Player now tries to obtain information about by asking player questions as follows: each question consists of specifying an arbitrary set 
of positive integers (possibly one specified in some previous question), and asking whether belongs to . Player may ask as many questions as he wishes. After each question, player 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 has asked as many questions as he wants, he must specify a set 
of at most positive integers. If belongs to , then wins; otherwise, he loses. Prove that:
1. If
then can guarantee a win.
2. For all sufficiently large, there exists an integer 
such that cannot guarantee a win.
Proof:
So I could only do part
, but I'm assuming this would be worth 
points at the IMO?
When I first saw part, given that asking yes and no questions corresponds to binary digits and the appearance of 
, I immediately saw that converting numbers into binary would be important. Given this motivation, let's proceed with the proof!
For the rest of the proof, given a question
(where is a set) let ![$ [R] = 1 $](//latex.artofproblemsolving.com/c/b/a/cba8bad4ce0521f737037661dfd8639862d5c70c.png)
if the answer to 
is yes and let ![$ [R] = 0 $](//latex.artofproblemsolving.com/f/d/1/fd1c9acec9733fbc59041f612b8594d5714eeb21.png)
otherwise. Also, a number with a line on top of it will be the notation for a string of binary digits. Assume 
(if not, the problem is trivial). Consider any -element subset of 
Call this subset 
Identify each element of 
with a different binary string of length 
Let 
for all integers 
denote the set of numbers in with a 
in the 
th position (from left to right) of their binary representation. Now, 
ask questions 
. After answers, let ![$ a_i = \overline{[S_1][S_2]\dots[S_i](1 - [S_{i + 1}])(1 - [S_{i + 2}])\dots(1 - [S_{k}])} $](//latex.artofproblemsolving.com/d/a/3/da3ef61f26d2aad2dc153b465c4b263ae050fa8e.png)
for all integers 
.
Now have ask questions 
.
For now, assume that answers that 
for some 
and that is the minimal such number. Then if in reality 
we would have that 
were all lies. But this is a sequence of 
consecutive lies, which is impossible. Therefore we would have that 
. We can continue using this method to cancel possibilities for 
until we are left with a set of candidates, as desired.
On the other hand, assume that answers that 
for all integers . Then one of these must be the truth so we have a set of 
candidates, as desired.
Therefore wins!
and 
. The rules of the game depend on two positive integers 
and 
which are known to both players.At the start of the game
chooses integers 
and 
with 
Player keeps secret, and truthfully tells to player . Player now tries to obtain information about by asking player questions as follows: each question consists of specifying an arbitrary set 
of positive integers (possibly one specified in some previous question), and asking whether belongs to . Player may ask as many questions as he wishes. After each question, player 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
has asked as many questions as he wants, he must specify a set 
of at most positive integers. If belongs to , then wins; otherwise, he loses. Prove that:1. If
then can guarantee a win.2. For all sufficiently large
, there exists an integer 
such that cannot guarantee a win.Proof:
So I could only do part
, but I'm assuming this would be worth 
points at the IMO?When I first saw part
, given that asking yes and no questions corresponds to binary digits and the appearance of 
, I immediately saw that converting numbers into binary would be important. Given this motivation, let's proceed with the proof!For the rest of the proof, given a question
(where is a set) let ![$ [R] = 1 $](http://latex.artofproblemsolving.com/c/b/a/cba8bad4ce0521f737037661dfd8639862d5c70c.png)
if the answer to 
is yes and let ![$ [R] = 0 $](http://latex.artofproblemsolving.com/f/d/1/fd1c9acec9733fbc59041f612b8594d5714eeb21.png)
otherwise. Also, a number with a line on top of it will be the notation for a string of binary digits. Assume 
(if not, the problem is trivial). Consider any -element subset of 
Call this subset 
Identify each element of 
with a different binary string of length 
Let 
for all integers 
denote the set of numbers in with a 
in the 
th position (from left to right) of their binary representation. Now, 
ask questions 
. After answers, let ![$ a_i = \overline{[S_1][S_2]\dots[S_i](1 - [S_{i + 1}])(1 - [S_{i + 2}])\dots(1 - [S_{k}])} $](http://latex.artofproblemsolving.com/d/a/3/da3ef61f26d2aad2dc153b465c4b263ae050fa8e.png)
for all integers 
.Now have
ask questions 
.For now, assume that
answers that 
for some 
and that is the minimal such number. Then if in reality 
we would have that 
were all lies. But this is a sequence of 
consecutive lies, which is impossible. Therefore we would have that 
. We can continue using this method to cancel possibilities for 
until we are left with a set of candidates, as desired.On the other hand, assume that
answers that 
for all integers . Then one of these must be the truth so we have a set of 
candidates, as desired.Therefore
wins!This post has been edited 1 time. Last edited by Wolstenholme, Oct 29, 2014, 2:29 AM
August 2016
June 2016