12
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ How much will you donate if no proof/disproof meeting the conditions is posted by the deadline? $\endgroup$ Mar 16, 2011 at 3:48
  • 4
    $\begingroup$ I probably would have donated the same amount. $\endgroup$
    – Dave R
    Mar 16, 2011 at 4:47

1 Answer 1

19
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Dave R
    Mar 16, 2011 at 4:10
  • 5
    $\begingroup$ +1 for sending the donation. $\endgroup$ Mar 16, 2011 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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