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.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s