Guessing a subset of $\{1,...,N\}$ I pick a random subset $S$ of $\{1,\ldots,N\}$, 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?
An obvious upper bound is $N$ queries, since you can test each element individually.  On the other hand, it takes at least $\Omega(N/\log N)$ queries: $N$ bits of information are required to identify the target subset, and each query can yield at most $O(\log N)$ bits of information, since each query has only $O(N)$ possible answers.  To see that the upper bound is not sharp, consider the following strategy for $N=5$, which takes at most $4$ queries:


Guess $\{1,2,3,4,5\}$.  If the result is $0$ or $5$, we have the answer.  If the result is $1$ or $4$, bisection search (for the single member or the single missing element) gives the answer in three more queries.  Suppose the result is $2$ (the strategy for $3$ is the same by symmetry).
Guess $\{1,2\}$.  If the result is $2$, we have the answer.  If the result is $0$, then bisection search on $\{3,4,5\}$ (for the single missing element) gives the answer in two more queries.  Suppose the result is $1$.  Then we know the answer is $\{a,b\}$ for some $a \in \{1,2\}$ and $b \in \{3,4,5\}$.
Guess $\{1,3\}$.  If the result is $2$, we have the answer.  If the result is $0$, then the answer is $\{2,b\}$ for some $b\in\{4,5\}$, and one more query gives the answer.  Suppose the result is $1$.  Then we know the answer is $\{1,4\}$, $\{1,5\}$, or $\{2,3\}$.
Guess $\{1,4\}$.  The answer is $\{1,4\}$ if the result is $2$, or $\{1,5\}$ if the result is $1$, or $\{2,3\}$ if the result is $0$.


This example gives an improved upper bound asymptotic to $4N/5$.  It seems likely that the correct answer is strictly $o(N)$ (i.e., eventually less than $cN$ for any fixed $c$), but whether or not it's $\Theta(N/\log N)$, I can't say.
$M$ denotes the solution set, $|M|$ denotes its cardinality (the number of elements).

Note that if I guess $\{1\dots N\}$, then you'll have to answer with $|M|$.

Now I can just brute force your set by removing the elements of $\{1\dots N\}$ one-by-one. Every time your answer decreases I will have identified an element of the solution. By induction, your answer will have to reach zero eventually. By that time I will have identified all $x\in M$. It will take me one more guess to win the game.

Using the algorithm outlined above I would guess at most $N+1$ times.

I am pretty sure in that you cannot do better than $O(n)$ in the worst case (I offer no proof though).