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
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 two integers
and
with
. Player
keeps
secret, and truthfully tells
to player
. Player
now tries to obtain information about
by asking player A questions as follows. Each question consists of
specifying an arbitrary set
of positive integers (possibly one specified in a previous question), and asking
whether
belongs to
. Player
may ask as many such 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 wishes; 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:
- If
, then
can guarantee a win.
- For all sufficiently large
, there exists an integer
such that
cannot guarantee a win.
- All are welcome. Everyone (regardless of mathematical level) is welcome to participate. Even very simple or “obvious” comments, or comments that help clarify a previous observation, can be valuable.
- No spoilers! It is inevitable that solutions to this problem will become available on the internet very shortly. If you are intending to participate in this project, I ask that you refrain from looking up these solutions, and that those of you have already seen a solution to the problem refrain from giving out spoilers, until at least one solution has already been obtained organically from the project.
- Not a race. This is not intended to be a race between individuals; the purpose of the polymath experiment is to solve problems collaboratively rather than individually, by proceeding via a multitude of small observations and steps shared between all participants. If you find yourself tempted to work out the entire problem by yourself in isolation, I would request that you refrain from revealing any solutions you obtain in this manner until after the main project has reached at least one solution on its own.
- Update the wiki. Once the number of comments here becomes too large to easily digest at once, participants are encouraged to work on the wiki page to summarise the progress made so far, to help others get up to speed on the status of the project.
- Metacomments go in the discussion thread. Any non-research discussions regarding the project (e.g. organisational suggestions, or commentary on the current progress) should be made at the discussion thread.
- Be polite and constructive, and make your comments as easy to understand as possible. Bear in mind that the mathematical level and background of participants may vary widely.
Have fun!