Guessing a subset of $\{1,…,N\}$

Question

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?

Answer 1

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:

1. 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).
2. 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\}$.
3. 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\}$.
4. 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.

Answer 2

$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).

Answer 3

The answer is $N$.

Let $F(N)$ be the number of guesses needed for determining $S$ of $\{1,...,N\}$ when the size of $S$ is unknown and let $H(N)$ be the number of guesses needed for determining $S$ of $\{1,...,N\}$ when the size of S is known. Obviously $H(0)=0, H(1) = 0, F(0)=0,F(1)=1$.

Suppose we know the size $|S|.$ After one guess, the problem reduces to determining $G \cap S$ of G, where we know $|G \cap S|$ and $G^C \cap S$ of $G^C \cap \{1,...,N\}$, where we know $|G^C \cap S|$. Thus

$$H(N) = 1+\min_{|G|} H(|G|) + H(N - |G|).$$

Now suppose that $H(N) = N-1$ for $N=1,...,n$. Then by our induction hypothesis, $H(|G|) + H(n+1-|G|)=|G|-1 + n-|G| = n-1$ when $\min(|G|,N-|G|) > 0$. When $|G|=0$ or $|G|=n+1$, $H(|G|) + H(n+1-|G|)=H(n+1)$, yet it is impossible that $H(n+1) = 1 + H(n+1)$, so $|G|=0$ and $|G|=n+1$ cannot be the minimizing choices of $|G|$. Therefore we conclude by induction that $H(N) = N-1$.

Now we will show that $F(N) = N$.

Suppose that $F(N) = N$ for $N=1,...,n$. We have $$F(N) = 1+\min_{|G|} H(|G|) + F(N - |G|).$$ and thus by a similar reasoning process as before, we conclude by induction that $F(n+1) = n+1$.