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.
