Minipolymath4 project, second research thread

July 13, 2012

Minipolymath4 project, second research thread

Filed under: polymath proposals — Terence Tao @ 7:49 pm

It’s been almost 24 hours since the mini-polymath4 project was opened in order to collaboratively solve Q3 from the 2012 IMO. In that time, the first part of the question was solved, but the second part remains open. In other words, it remains to show that for any sufficiently large $k$ and any $N$ , there is some $n \geq (1.99)^k$ such that the second player B in the liar’s guessing game cannot force a victory no matter how many questions he asks.

As the previous research thread is getting quite lengthy (and is mostly full of attacks on the first part of the problem, which is now solved), I am rolling over to a fresh thread (as is the standard practice with the polymath projects). Now would be a good time to summarise some of the observations from the previous thread which are still relevant here. For instance, here are some relevant statements made in previous comments:

Without loss of generality we may take N=n+1; if B can’t win this case, then he certainly can’t win for any larger value of N (since A could simply restrict his number x to a number up to n+1), and if B can win in this case (i.e. he can eliminate one of the n+1 possibilities) he can also perform elimination for any larger value of N by partitioning the possible answers into n+1 disjoint sets and running the N=n+1 strategy, and then one can iterate one’s way down to N=n+1.
In order to show that B cannot force a win, one needs to show that for any possible sequence of questions B asks in the N=n+1 case, it is possible to construct a set of responses by A in which none of the n+1 possibilities of x are eliminated, thus each x belongs to at least one of each block of k+1 consecutive sets that A’s answers would indicate.
It may be useful to look at small examples, e.g. can one show that B cannot win when k=1, n=1? Or when k=2, n=3?

It seems that some of the readers of this blog have already obtained a solution to this problem from other sources, or from working separately on the problem, so I would ask that they refrain from giving spoilers for this question until at least one solution has been arrived at collaboratively.

Also, participants are encouraged to edit the wiki as appropriate with new developments and ideas, and participate in the discussion thread for any meta-discussion about the polymath project.

Comments (21)

21 Comments »

If k=1 n=1 then then A chooses N=2 x=1. To the question is x=1 or x=2 A answers yes unless the previous question was the same and he answered yes to it then he answers no. To the question is x in the set containing both 1 or 2 A answers yes. Then he never tells 2 lies in a row and never breaks symmetry between 1 or 2 so it will be impossible for B to figure out which A has chosen.

Comment by kristalcantwell — July 13, 2012 @ 8:15 pm | Reply
Just to rephrase the question, as it takes me a long time to figure out how B can extract information if A just acts randomly:

Suppose that B askes a series of questions, and A answers a sequence of Yes and No. We call A’s answers a “dubious” sequence, call it Ans, indexed by i.

For every element x in {1,2,…,N}, we can construct a “truthful” sequence, call it Truth(x), i being the index, where A always give the correct answer given that x is the secret number.

Now B can exclude the possibility of y being secret number, if Truth(y) and Ans differ in k+1 consecutive terms (*). Phrasing in this way, A’s lying strategy would be looking at the set of all truthful sequences given B’s question, and choose Yes or No to prevent scenario (*) from happening.

Comment by prospector — July 14, 2012 @ 3:22 am | Reply
- Comparing sequences Ans and Truth(y), we could define Lie(y)_ j := total number of consecutive lies by A so far, after answering j-th question, after last telling truth. If Ans_i = Truth(x)_i, Lie(x)_i clears to zero; otherwise, Lie(x) increments by 1. When Lie(y) reaches k+1, we know that y is not the secret number; and this is what A wants to avoid.
  
  The trick here for B is to force the sequence Lie(x) for some x, to increase k+1 times consecutively, regardless of how A answer. At first, all Lie(x) are 0.
  
  If B asks if “x is in S?”, A has two choices:
  
  1. Say “Yes”. Then Lie(x) clears to zero for x in S, and Lie(x) increments by 1 for x not in S.
  2. Say “No”. Then Lie(x) increments by 1 for x in S, and Lie(x) becomes 0 for x not in S.
  
  In this way, we can think of the following games, similar to Conway’s checkers:
  
  There are N checkers on horizontal line y=0. Each time, B can partition these checkers into two set, X and Y, then A can either move all the checkers in X vertically up by 1 and put all checkers in Y back to line y = 0, or move all the checkers in Y vertically up by 1 and all checkers in X back to the line y = 0. (Here Lie(x) is the vertical distance of checker x to the line y = 0.) Show that no checkers can reach line y = k+1.
  
  Comment by Prospector — July 14, 2012 @ 6:31 am | Reply
For k = 2, n = 2 (which, like (k, n) = (1, 1), has k = 1/2 * 2^n)), one can proceed as follows (here N = 3; say the numbers are 1, 2, and 3):
I) Whatever B guesses on turn 1, A answers as if A’s number was ACTUALLY 1.
II) Whatever B guesses on turn 2, A answers as if A’s number was ACTUALLY 2.
III) Whatever B guesses on turn 3, A answers as if A’s number was ACTUALLY 3.

And so A goes on: pretending his number is actually 1 on turns congruent to 1 mod 3, 2 on turns that are 2 mod 3, and 3 that are 3 mod 3… no matter what A chooses, A’s statement is automatically true at least every third move..

Comment by William Meyerson — July 14, 2012 @ 9:41 pm | Reply
Here’s some tentative ideas; they need cleaned up.

Formulation 1

Let $Q = \{1,2,\ldots,n+1\}$ , and let $G$ be a sequence of $k+1$ non-empty subsets of $Q$ . Player A needs to find a cover $C$ of $Q$ , with $|C| \leq k+1$ , consisting of member(s) of $G$ and their complement(s) with respect to $Q$ .

If such a strategy exists for $k = m$ , it exists for all $k \geq m$ as well, since Player A could simply use the $k = m$ strategy.

If Player B asks $q_a$ followed by $q_b$ , $q_a \supseteq q_b$ and $|b - a| \leq k$ , then Player A can complete the cover by negating the answer for $q_a$ .

If the set of possible $x$ indicated over the past $k$ turns by Player A is $A$ and $q_n \subseteq A$ , then the cover can be completed by answering “No”. If the set of not-yet indicated $x$ over the past $k$ turns by Player A is $A$ and $q_n \supseteq A$ , then the cover can be completed by answering “Yes”.

Formulation 2

There are $2^{n+1}-1$ questions. Assign each question a unique, $n+1$ -digit binary string $b_i$ , where the $i$ -th digit of $b_i$ equals 1 if it is asked, and accumulate the indicated answers in a bit string $A$ . Player A can either bitwise or $b_i$ and $A$ , or bitwise or $\lnot b_i$ and $A$ . The goal is to have $A = 11111...$ after $k+1$ turns.

$1.99^k \leq n \leq 2^k$ , so an equivalent condition is $k\ \log_2(1.99) \leq \log_2(n) \leq k$ . Therefore Player A must indicate half or more of the remaining digits with each question. This can be done by selecting either $b_i$ or $\lnot b_i$ , depending on whichever indicates more new bits. $b_i$ or its negation will indicate at least half of the remaining bits, since any $b_i$ and its negation indicate all of the bits. This can be done in at most $k+1$ operations: given $\log_2(n) \leq k$ , $\lceil \log_2(n+1) \rceil \leq k+1$ . For at least one of those operations, telling the truth will be the optimal choice. If it were not, Player B would have to ask $k+1$ unique questions such that $x$ was always in the smaller group of bits. This would mean that only $x$ was not indicated on question $k+1$ . However, $x$ would still be indicated in that answer. If $x \in b_{k+1}$ , then a “yes” answer indicates $x$ , and if not, a “no” answer indicates $x$ as well.

Comment by ajk — July 14, 2012 @ 10:06 pm | Reply
One can have a look at Chapter 15 in Alon & Spencer’s book `Probabilistic Methods’…

Comment by lowai — July 14, 2012 @ 10:10 pm | Reply
- eh, it’s Chapter 15 in the third edition … specficially sectin 15.3 (tenure game)
  
  Comment by lowai — July 15, 2012 @ 2:10 pm | Reply
An easy observation that probably a lot of people have made: A can win if k=n=1. A chooses either 1 or 2, at random, and then alternates answering between answering the question as if the correct answer were 1 and answering as if it were 2. There is no way for B to know which half of A’s answers are truthful. More generally, A can win whenever k=n.

What is the current fastest growing function f(k) so that A can win for n=f(k)?

Comment by David Speyer — July 15, 2012 @ 12:14 am | Reply
Here is how I am currently thinking about the problem. I’m using the reduction where $N=n+1$ .

Let’s say that player A “suggests” $i$ whenever she gives an answer which is consistent with $i$ being the secret number.

For any $i$, if $A$ ever goes $k+1$ turns without suggesting $i$ , then $A$ loses. If $i$ was the secret number, then $A$ has broken the rules. If not, then $B$ can eliminate $i$ and win.

If there are ever $2$ numbers, say $i$ and $j$ , which have not been suggested for $k$ turns, then $B$ wins. This is because $B$ can ask a question which makes it impossible for $A$ to suggest both $i$ and $j$ , then win as in the previous paragraph.

Similarly, $A$ loses if there are ever $4$ numbers which have not been suggested in $k-1$ turns, or $8$ which have not been suggested in $k-2$ , etc.

Turning this logic around, in a winning strategy for $A$ , the number of digits which have NOT been suggested for the last $k-r$ rounds should grow exponentially in $r$ .

This hasn’t suggested a strategy to me yet, but my understanding is that the rules of a Polymath are that I should toss all my ideas out there.

Comment by David Speyer — July 15, 2012 @ 12:23 am | Reply
- Here is a template for a strategy for $A$ . At any moment in time, let $a_i$ be the number of values which have not been suggested for the last $i$ rounds. So the number of elements which just got suggested is $a_0$ , and we want to make sure that $a_{k+1}$ is always $0$ . Choose some positive real weights $w_0$ , $w_1$ , …, $w_k$ . $A$ always makes the choice (whether to lie or tell the truth) which minimizes $\sum a_i w_i$ . At the moment, I don’t have specific weights to nominate, but my intuition is that $w_i$ should grow just a little slower than $2^i$ .
  
  Comment by David Speyer — July 15, 2012 @ 12:47 am | Reply
- For example, suppose that we take $w_i = 1.99^i$ . Let the current score be B. Let $B_1$ be the part of the score which comes from numbers that would be suggested by answering YES and let $B_2$ be the part of the score which comes from numbers that would be suggested by answering NO. So $B=B_1 + B_2$ . Let $n_1$ be the number of numbers contributing to $B_1$ , and likewise for $n_2$ . So $n+1=n_1+n_2$ , and both are positive.
  
  Without loss of generality, say $B_1 > B_2$ . So A answers YES, and the new score is
  $n_1 + (1.99) B_2 < n + (1.99/2) B$ .
  
  So the score can never get above the fixed point of this recursion, at $B = 200 n$ . So there will never be an element which goes unsuggested for $k+1$ steps where $1.99^{k+1} = 200 n$ . So this is a winning strategy for $n = 1.99^{k+1}/200$ .
  
  I think I just solved the problem. I'm going to sit back and think about this for a bit.
  
  Comment by David Speyer — July 15, 2012 @ 1:00 am | Reply
  - You want to solve it for n greater than 1.99^k. That can be fixed by changing w_i to 1.999^i. If your method works I think you can change the exponent in your w_i and get an answer greater than any exponent less than 2for large enough k.
    
    Comment by kristalcantwell — July 15, 2012 @ 1:27 am | Reply
Here is an attempt to write up my solution neatly from scratch. My apologies if either (1) I have stolen people’s fun by getting to the answer too fast or (2) I have wasted people’s time with a faulty solution.

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

With $n=\epsilon (2-\epsilon)^{k+1}/2$ , Alice starts by choosing a random integer from $1$ to $n+1$ . 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 $k+1$ rounds.

We say that Alice “suggests $i$ ” if she gives an answer which would be truthful, if her number were $i$ . We will describe a strategy so that Alice suggests every number at least once every $k+1$ turns. In particular, she suggests the true number once every $k+1$ rounds, and thus obeys the rules.

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

“Just the place for a Snark! I have said it twice: That alone should encourage the crew.
Just the place for a Snark! I have said it thrice: What I tell you three times is true.”

Comment by David Speyer — July 15, 2012 @ 1:23 am | Reply
- As there were comments about the threshold of n.
  Is it the most one can get using this method?
  For example could the weights (2 – \epsilon)^r be modified to handle the case when n = 2^k / k^m
  
  Comment by Gagik Amirkhanyan — July 15, 2012 @ 4:33 am | Reply
We need to prove given any set of questions offered by questioner B, A can always make an answer such that at least (2-epsilon)^k numbers satisfy the rules for that answer.

So we just need to construct a strategy for A such that eventually (2-epsilon)^k possibilities remain.

Comment by Anonymous — July 15, 2012 @ 4:03 am | Reply
- Is there anything wrong with the following proof that the bound of part 1 can be improved to
  n>2^(k-1) +1?
  Preamble
  For a set U of 2^m possible integers, define strategy X for B as follows. First ask m “binary digit” questions. A will then have claimed x is in m subsets which exclude just 1 of the 2^m possible integers – call this integer X(U). B then asks if x is X(U).
  Proof
  Suppose n = 2^(k-1) +2.
  As noted by others, A can be “forced” to say x is a particular element. Consider this to be the first question and answer.
  Let U be 2^(k-1) of the integers, excluding the particular element and one other. Apply strategy X for questions 2 to k+1. (For questions 2 to k arbitrarily add just one of the two excluded elements to S.)
  As before, A is “forced” to say x is X(U) in answer to question k+1. Now consider questions k and k+1 to be the first two questions. At this point, A has claimed that x is in a set containing 2^(k-2) + 1 integers and has claimed that x is X(U). Let V and W be two sets, each containing 2^(k-2) integers, but excluding X(U), such that V is part of the first claimed set and W is not.
  Now, for questions 3 to k+1, apply strategy X to set W. Questions 3 to k can be used to similarly and simultaneously analyse set V. (For questions 3 to k arbitrarily add just one of the two elements not in V or W to S.)
  As before, A is “forced” to say x is X(W) in answer to question k+1. Furthermore, if B asks if x is X(V) for question k+2, then A is “forced” to say yes.
  Now, once again, consider questions k and k+1 to be the first two questions. Let Z be the 2^(k-1) integers excluding X(V) and X(W) and apply strategy X to Z. Before the final question is asked B knows that x is not X(Z).
  
  Comment by Stan Dolan — July 16, 2012 @ 2:17 pm | Reply
  - For N = 2 if N = 2^k, thus sharpening the assertion of the IMO problem to n >= 2^k – 1 for k >= 2. For k = 2 it seems to be similar to Jerzy Wojciechowski’s in #10. Combining this with William Meyerson’s #3 we thus know that n = 2^k – 1 = 3 is the minimum for k = 2. From other posts we have n = 1 for k = 0 and n = 2 for k = 1. The question of the minimum for arbitrary k appears to be still open.
    
    Comment by Kai Neergård — October 7, 2012 @ 1:21 pm | Reply
    - The interface apparently does’nt like “less than” and “larger than” signs and so skipped a large part of my post. Since I see no way of editing or withdrawing posts, I thus have to submit it once more. Please neglect that above:
      
      For N less than 2^k, binary digit questions don’t necessarily enforce a yes. The x that is excluded may be larger than N. In that case B learns nothing from asking if it is the true x. Thus the “particular element” of Stan Dolan’s argument may not exist.
      
      The argument seems to work for k not less than 2 if N = 2^k, thus sharpening the assertion of the IMO problem to n not less than 2^k – 1 for k not less than 2. For k = 2 it seems to be similar to Jerzy Wojciechowski’s in #10. Combining this with William Meyerson’s #3 we then know that n = 2^k – 1 = 3 is the minimum for k = 2. From other posts we have n = 1 for k = 0 and n = 2 for k = 1. The question of the minimum for arbitrary k appears to be still open.
      
      Comment by Kai Neergård — October 7, 2012 @ 1:37 pm | Reply
Let’s look at the case when k=2 and n=3. It seems to me that B can win. Let N=4. Let B ask the first question with S={1,2} and the second with S={1,3}. Then there is exactly one number m in {1,2,3,4} so that when x=m the first two answers of A are false. Then B asks the third question with S={m}, A must answer yes, since otherwise m could be eliminated. Let w be such that the second question was false when x=m or when x=w. Let B ask the fourth question with S={w}. Again A must answer yes, since otherwise w could be eliminated. If {1,2,3,4}-{m,w}={y,z} then let B ask the fifth question with S={z}. If A answers yes, then y can be eliminated, if A answers no, then z can be eliminated.

Comment by Jerzy Wojciechowski — July 19, 2012 @ 9:53 pm | Reply
Looks like I’m very late to the party. I wanted to point out a different solution to part 1 that has ties to the De Brujin sequence cycle, though admittedly it’s more complicated. I typed up a little bit here: http://evan-qcs.blogspot.com/2012/07/liars-guessing-game-and-de-brujin.html

The idea still uses the fact that within k questions, we can get player 1 to lie about one of the numbers k times (for instance, the strategy of asking about what the i-th bit is does that trick), and then… how to uses subsequent questions to force player 1 into fewer and fewer options for answer choices.

In short, for this strategy, player 2 follows the de Brujin sequence for bitstrings of length k (B(2,k)) to figure out when he should include a particular number i in the question. For the i-th number, start from the i-th element of the de Brujin sequence, if we see a 1, include it in the set for the question. What this does is that for every contiguous block of questions, and no matter what player 1 answers, he will lie about a particular number $k$ times, and this number rotates. In effect, if we examine all possible strategies for player 1 for this set of questions, the player must follow 1 of 2^k possible sequences.

Then, use the last number (2^k+1) as a trap: throw in this number and follow a particular possible answer sequence for k questions. On the k+1-th question, place the last number to oppose that answer sequence, then player 1 is trapped if he followed that answer sequence. Set these traps one bunch at a time, until all of them are gone. It takes a lot longer than the short answer proposed already, but it seems fun. Should have occurred to me to set the trap up at the beginning. Oh well…

Comment by Evan — July 26, 2012 @ 2:01 am | Reply
I realize that this polymath project has ended about a month ago. I’m writing this comment only for “future reference” if someone is interested in this IMO problem and wants to figure out a better estimate (asymtotics) for the smallest n (as a function of k) that makes the game a win for B.

First I state an equivalent formulation of the problem in terms of existence of certain binary trees. This provides another way to look at the problem and has the advantage that this problem has been studied in relation to unsatisfiable CNF Boolean formulas and the complexity of certain restrictions of SAT, so I can quote results (including one that is partially mine – sorry).

A finite rooted binary tree is called a (k, d)-tree if
(i) every non-leaf vertex has exactly two children,
(ii) each leaf has distance at least k from the root, and
(iii) every node u of the tree has at most d leaves that are both descendants of u and in distance at most k from u.

We call leaves satisfying (iii) with respect to a vertex u “visible from u”. We call them left- or right-visible depending on whether they are descendants of the left or right child of u (the two children of u are distinguished arbitrarily).

CLAIM: The liar’s guessing game for k and n is a win for B if and only if there exists a (k+1,n+1)-tree.

PROOF: Let’s assume first that B wins and fix a winning strategy for N=n+1. We assume he stops asking questions as soon as he can eliminate one of the n+1 possibilities for the unknown x, that is when A’s last k+1 answers are all false for some possible choice for x. Let us build the game tree from B’s strategy: the root corresponds to the initial position before the first question was answered, its two children correspond to the two possible answers, etc. Leaves correspond to the end of the game when the last k+1 answers eliminate a possible value for x. Let us label each leaf with one of the eliminated values.

For the “only if” part we prove that this is a (k+1,n+1)-tree. Parts (i) and (ii) of the definition are satisfied trivially. Part (iii) follows from the observation that all leaves visible from a vertex u of the tree must have different labels. Indeed, otherwise there would be a vertex u’ of the tree with a left-visible and a right-visible leaf having the same label x. But this would mean that both answers to the question B asks at the position u’ rules out x – a contradiction.

For the reverse direction (the “if” part) we use the observation that B wins if and only if he wins with N=n+1. Assume there is a (k+1,n+1)-tree. Label the leaves with values 1<=x<=n+1 such that all leaves visible from the same vertex have distinct labels. This is possible, one can label the leaves in increasing order of their level (distance from the root). Condition (iii) makes sure we have always enough labels to choose from. Now here is a strategy for B to eliminate one of the n+1 possible values for x: Start at the root. At a vertex u ask if there is a leaf labeled x left-visible from u. If the answer is YES move to right child, for NO answer move to the left child. When B arrives to a leaf it can rule out its label and hence wins the game.

QED

And now the references: Let f(k) denote the largest d with no (k,d)-tree (referred to as f_2 in [GST]). Then f(k)=\Theta(2^k/k) by [G] and f(k)=(2/e+O(k^{-1/2}))2^k/k by [GST]. The lower bound can easily be derived from Lovasz's local lemma, the upper bound is based on an elaborate construction. Because of the shift by 1 this means that the smallest n such that B wins the liar's guessing game for k and n is (4/e+O(k^{-1/2}))2^k/k.

[G] H. Gebauer, Disproof of the Neighborhood Conjecture with Implications to SAT, Combinatorica, to appear, Proc. 17th Annual European Symposium on Algorithms (ESA 2009), LNCS 5757, 764–775. http://www.inf.ethz.ch/personal/gebauerh/NeighborhoodConjecture.pdf

[GST] H. Gebauer, T. Szabo, G. Tardos, The local lemma is tight for SAT, Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011). http://www.renyi.hu/~tardos/SAT.pdf

Comment by Gabor Tardos — August 14, 2012 @ 8:55 pm | Reply

RSS feed for comments on this post. TrackBack URI

	Anonymous on Polymath6: improving the bound…
	Anonymous on Rota’s Basis Conjecture:…
	Anonymous on Polymath proposal: bounded gap…
	Anonymous on Rota’s Basis Conjecture:…
	Anonymous on Rota’s Basis Conjecture:…
	Cherrypick India on Polymath projects 2021
	tanner808 on Polymath projects 2021
	Anonymous on Polymath 11 is Now Open
	Chenxiao Tian on Polymath 11 is Now Open
	ryeguy10 on Polymath 11 is Now Open
	ndnnnd on Polymath projects 2021
	Prime time on Two polymath (of a sort) propo…
	What comes after exp… on Minipolymath2 project: IMO 201…
	Will AI Replace Math… on Spontaneous Polymath 14…
	gui7575 on A new polymath proposal (relat…

The polymath blog

July 13, 2012