2012 IMO Problems/Problem 3
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 .