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. Active

Research:

• Research thread, July 12, 2012. Inactive
• Second research thread, July 13, 2012. Active

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.
  • In fact, it suffices to assume that [math]\displaystyle{ n = 2^k, N = 2^k+1 }[/math].

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 [math]\displaystyle{ N \leq n }[/math]. Then he outputs the remaining numbers.
  • If [math]\displaystyle{ N }[/math] is not a power of 2 but [math]\displaystyle{ N \gt 2^{k+1} }[/math], [math]\displaystyle{ B }[/math] groups all numbers in [math]\displaystyle{ 2^{r+1} }[/math] non-empty clusters. Then he labels each cluster, and all numbers in it, with a unique binary string of length [math]\displaystyle{ r+1 }[/math]. He then asks if the first bit of the label of [math]\displaystyle{ x }[/math] is 0; then he asks if the second bit is 0, and so on. After [math]\displaystyle{ B }[/math] asks [math]\displaystyle{ r+1 }[/math] questions, he finds a label [math]\displaystyle{ L = (1 - b_1, ..., 1 - b_{r+1}) }[/math] such that [math]\displaystyle{ x }[/math] is not labeled with [math]\displaystyle{ L }[/math]. Now he can exclude all number with label [math]\displaystyle{ L }[/math] and iterate. This reduces [math]\displaystyle{ n }[/math] to be at most [math]\displaystyle{ 2^{k+1}-1 }[/math].

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

We can assume N = 2^k + 1, n = 2^k.

It means that x has at most k + 1 binary digits (k+1 digits only for n = 2^k)

[math]\displaystyle{ x = b_1 b_2\dots b_{k+1} }[/math]

Then we can keep asking if b_1 is 1, there are two possibilities,

1. k + 1 times we get the answer NO, then we exclude the number 10…0

1. There is a YES answer. Then we stop asking about b_1 and ask b_2 = 1, b_3 = 1 … b_{k+1} = 1. After we are done we can exclude the number for which all the last k + 1 asnwers would have been lies whose first digit is 0 (because of the YES answer).

Completed solutions for part 2

Let [math]\displaystyle{ \epsilon \gt 0 }[/math] be a small parameter. Our strategy will allow Alice to deny Bob a certain win with [math]\displaystyle{ n+1 = \epsilon (2-\epsilon)^{k+1} }[/math]. By first choosing [math]\displaystyle{ \epsilon }[/math] sufficiently small (say [math]\displaystyle{ 10^{-3} }[/math]) and then [math]\displaystyle{ k }[/math] sufficiently large, this is greater than [math]\displaystyle{ 1.99^k }[/math].

With [math]\displaystyle{ n=\epsilon (2-\epsilon)^{k+1}/2 }[/math], Alice starts by choosing a random integer from [math]\displaystyle{ 1 }[/math] to [math]\displaystyle{ n+1 }[/math]. Alice then never considers this value again. Since her answers will in no way depend what number she has chosen, they can reveal no information about that number, and therefore can provide Bob with no aid. What we must see is that Alice can do this while obeying the rule that she must tell the truth once every [math]\displaystyle{ k+1 }[/math] rounds.

We say that Alice "suggests [math]\displaystyle{ i }[/math]" if she gives an answer which would be truthful, if her number were [math]\displaystyle{ i }[/math]. We will describe a strategy so that Alice suggests every number at least once every [math]\displaystyle{ k+1 }[/math] turns. In particular, she suggests the true number once every [math]\displaystyle{ k+1 }[/math] rounds, and thus obeys the rules.

Let [math]\displaystyle{ a_r }[/math] be the number of values which have not been suggested in the last [math]\displaystyle{ r }[/math] rounds. Alice's strategy will be to always answer so as to minimize the quantity [math]\displaystyle{ \sum a_r (2-\epsilon)^r }[/math]. We'll call this quantity the score. At the beginning of the game, the score is [math]\displaystyle{ n+1 }[/math]. Suppose that the score is [math]\displaystyle{ B }[/math]. The next question is asked about set [math]\displaystyle{ S }[/math]. Let [math]\displaystyle{ n_1 = |S| }[/math] and [math]\displaystyle{ n_2 = (n+1) - |S| }[/math]. Let [math]\displaystyle{ B_1 }[/math] be the part of the score contributed by numbers in [math]\displaystyle{ S }[/math], and let [math]\displaystyle{ B_2 }[/math] be the part contributed by numbers not in [math]\displaystyle{ S }[/math]. Then the new score is [math]\displaystyle{ \min((2- \epsilon) B_1 + n_2, (2- \epsilon) B_2 + n_1) }[/math]. Since [math]\displaystyle{ ( (2- \epsilon) B_1 + n_2 ) + ((2- \epsilon) B_2 + n_1) = (2-\epsilon) B + n + 1 }[/math], Alice can definitely arrange for the new score to be [math]\displaystyle{ \leq ((2-\epsilon) B + n+1)/2 = (1-\epsilon/2) B + (n+1)/2 }[/math]. So, inductively, the score never gets higher than [math]\displaystyle{ (n+1)/\epsilon }[/math]. In particular, there is no contribution from [math]\displaystyle{ r }[/math] such that [math]\displaystyle{ (2-\epsilon)^r \gt (n+1)/\epsilon }[/math]. Since we chose [math]\displaystyle{ (k,n) }[/math] such that [math]\displaystyle{ n+1 = \epsilon (2-\epsilon)^{k+1} }[/math], that means that we have succeeded in suggesting every value at least once every [math]\displaystyle{ k+1 }[/math] steps, as desired.