46
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ see cs.mcgill.ca/~colt2009/papers/004.pdf if you know the cardinal of $S$ (which you can get in one guess) ( this could get a very good bound on average) $\endgroup$ – Elaqqad Aug 25 '17 at 20:26
  • $\begingroup$ Very nice! This answers my question, as it shows that the number of guesses required is $\Theta(N/\log(N))$. $\endgroup$ – Dave Radcliffe Aug 26 '17 at 1:48
21
+100
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "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? $\endgroup$ – barrycarter Mar 6 '11 at 17:19
  • 2
    $\begingroup$ @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. $\endgroup$ – mjqxxxx Mar 6 '11 at 18:20
  • $\begingroup$ @mjqxxxx: we can say more. If your guess has $k$ elements, the central binomial coefficient is about $\frac {2^k}{\sqrt {\frac \pi 2 k}}$ so in the worst case you only get $\log_2 \sqrt {\frac \pi 2 k}$ bits (taking $\sqrt{\frac \pi 2}\approx 1)$. The first guess where $k=N$ will only get you about $\frac 12 \log_2N$ bits. I suspect after the first guess you want $k$ to be around $\frac N2$, so that gets you $\frac 12 \log_2 N -1$ bits $\endgroup$ – Ross Millikan Aug 25 '17 at 3:58
  • $\begingroup$ @RossMillikan I must confess I don't know much about these things, but find them rather interesting nonetheless. Can you suggest any readings on the topic for me? $\endgroup$ – Fimpellizieri Aug 25 '17 at 4:33
  • $\begingroup$ @Fimpellizieri: I am not sure what you mean by "these things". The number of bits necessary to decide something is basic to information theory. A bit can give you the result of a yes/no question. Picking one item out of $N$ requires $\log_2 N$ bits because you can split the group in half and ask which half it is in $\log_2 N$ times and find it. One way to put a bound on the number of questions you need to ask is to count the bits needed and the number you get from each question, which is what we are doing here. $\endgroup$ – Ross Millikan Aug 25 '17 at 4:56
-2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – joriki Mar 6 '11 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.