# 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:

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.

-
"each query can yield at most O(logN) bits of information, since each query has only O(N) possible answers". However, since you get to choose what set to query, doesn't that change the amount of information you could theoretically gain? –  barrycarter Mar 6 '11 at 17:19
@barrycarter: Here's a longer explanation. Before each query, there are some number $X$ of possible subsets. The result of the query will be $i \in \{0,1,...,N\}$, so the $X$ subsets are partitioned into $N+1$ disjoint classes $X_i$ (where the subsets in $X_i$ are those consistent with the result $i$). The largest of these must have size at least $X / (N+1)$, and in the worst case, that is the result you'll get. So you've reduced the number of possible subsets from $X$ to no less than $X / (N+1)$; i.e., you've gained no more than $\log_{2}(N+1)$ bits of information about the answer. –  mjqxxxx Mar 6 '11 at 18:20

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

-
The question is "How many guesses do you need?", not "Is there a brute-force way to determine $S$?". After your first guess, there are $\left(N\atop \lvert M\rvert\right)$ possibilities left, and you could theoretically get $\lvert M\rvert+1$ different answers for each of your subsequent guesses, so the only obvious lower bound on the number of guesses needed after your first guess (which might itself not be optimal) is $\max_{\lvert M\rvert}\lceil\log_{\lvert M\rvert+1}\left(N\atop \lvert M\rvert\right)\rceil$, which is a lot less than $N$. –  joriki Mar 6 '11 at 13:15

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

-
I don't see how you deduce the first displayed equation. Why is it not possible that subsequent guesses contribute to the solution of both subproblems? That would prevent you from simply adding the numbers for the two subproblems. –  joriki Mar 6 '11 at 13:32
That can't be right. Suppose $|S|=1$, then it's always possible to determine the set in $\sim \log_2(N)+1$ steps. Can you elaborate a little more on the induction step? Certainly, $F(N)=N$ will always be the worst case scenario. But I don't think it will always turn out that way. –  Raskolnikov Mar 6 '11 at 13:42
This is not correct, for the reason that @joriki gives; see my example for $N=5$. –  mjqxxxx Mar 6 '11 at 15:39
Indeed, the above proof is very incorrect. Perhaps it would be possible to employ finite-field linear algebra to solve the problem as posed. –  charles.y.zheng Mar 7 '11 at 2:24