Imo 2012

This is the wiki page for the mini-polymath4 project, which will seek a solution to a problem from the 2012 International Mathematical Olympiad, held in Argentina from July 10-11. The project will start at Thursday, July 12, 2012 at 22:00:00. It will be held primarily at the polymath blog (with a discussion thread at the "What's new" blog.)

Rules

This project will follow the usual polymath rules. In particular:

• Everyone is welcome to participate, though people who have already seen an external solution to the problem should refrain from giving spoilers throughout the experiment.
• This is a team effort, not a race between individuals. Rather than work for extended periods of time in isolation from the rest of the project, the idea is to come up with short observations (or to carry an observation of another participant further) and then report back what one gets to the rest of the team. Partial results or even failures can be worth reporting.
• Participants are encouraged to update the wiki, or to summarise progress within threads, for the benefit of others. (In particular, linking between the wiki and specific comments on the blogs is highly encouraged.)

Threads

Planning:

• Two polymath projects, June 4, 2012.
• Updates on the two polymath projects, June 15, 2012.

Discussion:

• Discussion thread, July 12, 2012.

Research:

• Research thread, July 12, 2012.

The question

Problem 3. The liar's guessing game is a game played between two players [math]\displaystyle{ A }[/math] and [math]\displaystyle{ B }[/math]. The rules of the game depend on two positive integers [math]\displaystyle{ k }[/math] and [math]\displaystyle{ n }[/math] which are known to both players.

At the start of the game, [math]\displaystyle{ A }[/math] chooses two integers [math]\displaystyle{ x }[/math] and [math]\displaystyle{ N }[/math] with [math]\displaystyle{ 1 \leq x \leq N }[/math]. Player [math]\displaystyle{ A }[/math] keeps [math]\displaystyle{ x }[/math] secret, and truthfully tells [math]\displaystyle{ N }[/math] to player [math]\displaystyle{ B }[/math]. Player [math]\displaystyle{ B }[/math] now tries to obtain information about [math]\displaystyle{ x }[/math] by asking player [math]\displaystyle{ A }[/math] questions as follows. Each question consists of [math]\displaystyle{ B }[/math] specifying an arbitrary set [math]\displaystyle{ S }[/math] of positive integers (possibly one specified in a previous question), and asking [math]\displaystyle{ A }[/math] whether [math]\displaystyle{ x }[/math] belongs to [math]\displaystyle{ S }[/math]. Player [math]\displaystyle{ B }[/math] may ask as many such questions as he wishes. After each question, player [math]\displaystyle{ A }[/math] 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 [math]\displaystyle{ k+1 }[/math] consecutive answers, at least one answer must be truthful.

After [math]\displaystyle{ B }[/math] has asked as many questions as he wants, he must specify a set [math]\displaystyle{ X }[/math] of at most [math]\displaystyle{ n }[/math] positive integers. If [math]\displaystyle{ x }[/math] belongs to [math]\displaystyle{ X }[/math], then [math]\displaystyle{ B }[/math] wins; otherwise, he loses. Prove that:

1. If [math]\displaystyle{ n \geq 2^k }[/math], then [math]\displaystyle{ B }[/math] can guarantee a win.

2. For all sufficiently large [math]\displaystyle{ k }[/math], there exists an integer [math]\displaystyle{ n \geq 1.99^k }[/math] such that [math]\displaystyle{ B }[/math] cannot guarantee a win.

Observations and partial results

• Might be related to error-correcting codes?

Examples

• (Add contributions here.)

Possible strategies

• (Add contributions here.)

Completed solutions for part 1

• (Add contributions here.)

Completed solutions for part 2

• (Add contributions here.)