Minipolymath4 Project Now Open!

As we talked about here, there was plans afoot to group-solve online an interesting and problem from the IMO.  The online discussion going on right now (unless, of course, you’re reading this later).  They decided to work on Question 3.  Here it is:

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 k and n which are known to both players.

At the start of the game, A chooses two integers x and N with 1 \leq x \leq N.  Player A keeps x secret, and truthfully tells N to player B.  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 a previous question), and asking A whether x belongs to S.  Player B may ask as many such 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 wishes; 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 belongs to X, then B wins; otherwise, he loses.  Prove that:

  1. If n \geq 2^k, then B can guarantee a win.
  2. For all sufficiently large k, there exists an integer n \geq 1.99^k such that B cannot guarantee a win.

Check out (and join in on) the discussion here.