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](https://math.stackexchange.com/questions/25270/guessing-a-subset-of-1-n) 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.



Guessing a subset of {1,...,N}
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.


