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

• B can as well ask questions in “rounds” of k+1 questions. Then, each round is guaranteed to have at least 1 correct answer.
  • for any partition of some set of numbers into 2^(k+1) parts, one round of questioning allows to rule out one of the parts.
    • hence, while we can partition N into 2^(k+1) non-empty parts, we can rule out something each round of k+1 questions. We can go on ruling out numbers until no more than 2^(k+1) possible answers remain. After that, we need to somehow cut that in half.
• Since there is a possibility that B would win the game simply by guessing, there is no “always win” for A. Thus suggests that part 2 is somewhat harder than part 1. So it might be wise to completely focus on part 1 first.
• For part 1, it suffices to produce a winning strategy for [math]\displaystyle{ N=n+1 }[/math]. In other words, player B can win for [math]\displaystyle{ N }[/math] iff he can win [math]\displaystyle{ N=n+1 }[/math]. [math]\displaystyle{ \Rightarrow }[/math] is trivial. [math]\displaystyle{ \Leftarrow }[/math] is as follows:
  • Go by induction. Suppose [math]\displaystyle{ N \gt n+1 }[/math] and a winning strategy is known for all [math]\displaystyle{ n+1\leq N' \lt N }[/math]. Partition [math]\displaystyle{ N }[/math] into [math]\displaystyle{ n+1 }[/math] nonempty sets [math]\displaystyle{ G_1,\cdots,G_{n+1} }[/math]. Then instead of asking "is it in [math]\displaystyle{ S\subset \{1,\cdots,n+1\} }[/math]", he asks "is it in [math]\displaystyle{ \cup_{s\in S} G_s }[/math]"? By using the winning strategy for [math]\displaystyle{ n+1 }[/math], we can throw out one of the [math]\displaystyle{ G_i }[/math] and we now have a winning strategy by assumption.

Partial results and examples

• For [math]\displaystyle{ k=0 }[/math] any version of binary search works.
• Focus on k=1, n=2?
• assume that [math]\displaystyle{ N }[/math] is a power of 2. Say [math]\displaystyle{ N = 2^r }[/math]. Suppose that [math]\displaystyle{ r \geq k+1 }[/math]. Think of numbers from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ N }[/math] as vertices of [math]\displaystyle{ r }[/math]-dimensional Boolean cube. Then let [math]\displaystyle{ x_i\in\{0,1\} }[/math] be the [math]\displaystyle{ i }[/math]-th coordinate of [math]\displaystyle{ x }[/math]. First, [math]\displaystyle{ B }[/math] asks if [math]\displaystyle{ x_1 = 0 }[/math] (formally, B gives set [math]\displaystyle{ \{x:x_i = 0\} }[/math]), then he asks if [math]\displaystyle{ x_2 =0 }[/math], and so on. Finally, he asks if [math]\displaystyle{ x_{k+1} = 0 }[/math]. He gets "yes" and "no" answers. In other words, he gets [math]\displaystyle{ b_1, \dots, b_{r+1} }[/math] such that one of the statements "[math]\displaystyle{ x_i = b_i }[/math]" is true. Therefore, the first [math]\displaystyle{ r+1 }[/math] bits of [math]\displaystyle{ x }[/math] cannot be equal [math]\displaystyle{ 1-b_1,1-b_2, \dots, 1-b_{r+1} }[/math]. Thus B can exclude some values of [math]\displaystyle{ x }[/math], and essentially reduces [math]\displaystyle{ N }[/math]. He proceeds until $N \leq n$. Then outputs the remaining numbers.

Possible strategies

• Are there any results from Ramsey theory or related which might be useful for part one?
• Might be related to error-correcting codes?
• For the first part, proving for [math]\displaystyle{ n=2^k }[/math] suffices. The first approach that comes to my mind is to induct on [math]\displaystyle{ k }[/math].
• Since the solution is obvious if N is inside [1,n], then we could simply prove the case n+1 and the rest would follow by induction on N.

Completed solutions for part 1

• (Add contributions here.)

Completed solutions for part 2

• (Add contributions here.)