# Minipolymath4 project: IMO 2012 Q3

Standard

IMO is the Mecca of young mathematicians battling out in this divine field of which I am in oblivion of until now. Whenever I try and study mathematics it is with a notion of solving a problem and that problem is hard enough for veterans to try but what I have come to know from those who do “Research” is that they don’t do it to solve the problem but to firstly understand it well and secondly to find why is that problem tough than what it seems to be. Terence Tao as you all know is a known child prodigy and inculcated abilities to solve problems involving numbers at a very young age. He id the youngest even to have received a fields medal. This Re-Blogged post concerns a question which appeared in this year’s IMO (International Mathematical Olympiad in case you are not familiar with what it is) and a good thread to discuss what comes to your mind while approaching it.

Originally posted on The polymath blog:

This post marks the official opening of the mini-polymath4 project to solve a problem from the 2012 IMO.  This time, I have selected Q3, which has an interesting game-theoretic flavour to it.

Problem 3.   The liar’s guessing game is a game played between two players $latex A$ and $latex B$.  The rules of the game depend on two positive integers $latex k$ and $latex n$ which are known to both players.

At the start of the game, $latex A$ chooses two integers $latex x$ and $latex N$ with $latex 1 \leq x \leq N$.  Player $latex A$ keeps $latex x$ secret, and truthfully tells $latex N$ to player $latex B$.  Player $latex B$ now tries to obtain information about $latex x$ by asking player A questions as follows.  Each question consists of $latex B$ specifying an arbitrary set $latex S$ of positive integers (possibly one specified in a previous question), and asking $latex A$ whether $latex x$ belongs to $latex S$.  Player $latex B$ may ask as many such questions as he wishes.  After each question, player $latex A$ must immediately answer it with yes or no, but is allowed to lie as many times as she wishes; the only restriction is that, among any $latex k+1$ consecutive answers, at least one answer must be truthful.

After $latex B$ has asked as many questions as he wants, he must specify a set $latex X$ of at most $latex n$ positive integers.  If $latex x$ belongs to $latex X$, then $latex B$ wins; otherwise, he loses.  Prove that:

1. If $latex n \geq 2^k$, then $latex B$ can guarantee a win.
2. For all sufficiently large $latex k$, there exists an integer $latex n \geq 1.99^k$ such that $latex B$ cannot guarantee a win.
The comments to this post shall serve as the research thread for the project, in which participants are encouraged to post their thoughts and comments on the problem, even if (or especially if) they are only partially conclusive.  Participants are also encouraged to visit the discussion thread for this project, and also to visit and work on the wiki page to organise the progress made so far.

View original