Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I pick a random subset $S\subseteq\lbrace1,\ldots,N\rbrace$, and you have to guess what it is. After each guess $G$, I tell you the number of elements in $G \cap S$. How many guesses do you need to determine the subset? (If there is only one possibility left, then you can omit the last guess.)

There is an obvious strategy that requires only $N$ guesses. Guess $\lbrace1\rbrace$, then guess $\lbrace2\rbrace$, then guess $\lbrace3\rbrace$, and so on. But there is a clever strategy that requires only $\lceil 4N/5 \rceil$ guesses.

We know that the minimum number of guesses is at least $\left\lceil \frac{N}{\log_2{(N+1)}}\right\rceil$, because each guess reveals at most $\log_2(N+1)$ bits of information. I seek a proof or disproof of the conjecture that the number of guesses $g(N)$ is sublinear, i.e. $\lim_{N\to\infty} g(N)/N = 0$.

I will donate $100 to the American Red Cross if a proof or disproof is posted to this thread by April 30, 2011. For this purpose, I will accept an argument as correct if I believe it to be correct; or if a user with reputation above 1000 asserts that it is correct, and no user with reputation above 1000 denies that it is correct. Naturally, I would welcome improved upper bounds, even if they are linear.

share|improve this question
3  
How much will you donate if no proof/disproof meeting the conditions is posted by the deadline? –  Gerry Myerson Mar 16 '11 at 3:48
2  
I probably would have donated the same amount. –  Dave R Mar 16 '11 at 4:47

1 Answer 1

up vote 16 down vote accepted

This is a well-studied problem, sometimes phrased as a coin-weighing problem. It is known that $g(N)$ is $O(N / \log N)$. (We can even specify the guessing sets in advance, without knowing the previous answers.) I believe these three papers are the earliest to show this bound:

B. Lindstrom (1964), "On a combinatory detection problem I", Mathematical Institute of the Hungarian Academy of Science 9, pp. 195-207.

B. Lindstrom (1965), "On a combinatorial problem in number theory", Canadian Math. Bulletin 8, pp. 477-490.

D. Cantor and W. Mills (1966), "Determining a subset from certain combinatorial properties", Canadian J. Math 18, pp. 42-48.

There was a lot of work after these papers too (some with simpler constructions, some to solve more general problems). A book by Aigner covers this topic and more:

M. Aigner (1988), "Combinatorial search", John Wiley and Sons.

share|improve this answer
1  
Thanks Ravi! I was hoping that this was a new problem, but I think I knew that it couldn't be. I sent the donation, but I will keep the question open for a while. –  Dave R Mar 16 '11 at 4:10
4  
+1 for sending the donation. –  Gerry Myerson Mar 16 '11 at 12:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.