How many subset intersections do you require?

Question

Alice chooses a subset S of {A,B,C,D,E}.

Bob makes a guess of any subset T and Alice tells him the number of elements in S$\cap$T.

Bob has to continue making guesses until he can exactly determine S.

Prove that the minimum number of times Bob has to guess is 4

(Note: I have an algorithm that does it in 4 guesses but I do not have a proof that it is the lowest)

Answer 1

Guess the following:

{A,B,c} {A,D} {B,D} {C,E}

Multiply the second answer by 5, the third by 25, and the fourth by 125. Sum the answers.

Each number will correspond to a different one of the 32 answers.

This requires 4 guess to determine the answer but doesn't state it.

This works by making inclusion omission patterns for each letter such that none are duplicated nor can be written as the sum of another 2.

Only 4 non-interacting patterns exist for only 3 guesses. This means that if you want to know the answer after 3 guesses, there needs to be fewer letters to chose from.

Update

I'd like to improve this slightly to make it easy to find the answer from the data without math skills. Instead of $1,5,25,125$ multiply by $1,3,9,27$. They work equally well but I prefer the former usually.

• Call your numberic result $N_o$ and give me an number I can manipulate $N$ that starts as $N=N_o$

• As only $E$ uses an odd number of entry's, if you result is odd then "S" contains an "E". If it does, write it down and $N-27 \rightarrow N$

• No matter what number you have (it should be even now) perform $N/2 \rightarrow N$

• If $N$ is now odd, then you have a $B$. If it does, write it down and $N-5 \rightarrow N$

• No matter what number you have (it should be even now) perform $N/2 \rightarrow N$

• If $N=0$, no more a present. If $N=1$, an $A$ is in $S$ but not $C$
  or $D$. If $N=3$, an $D$ is in $S$ but not $C$ or $A$. If $N=7$, an
  $C$ is in $S$ but not $A$ or $D$.

• The remaining $4$ options are the obvious combinations of these:
  $N=4$ means $AD$ no $C$. $N=8$ means $AC$ no $D$. $N=10$ means $CD$ no $A$. $N=11$ means $AC$ and $D$ are all in $S$.

Answer 2

Here's an alternative formulation that proves that it can't be done with three (non-adaptive) guesses:

Let $U=\{A,B,C,D,E\}$ be the 'universe' here, with the subset we're guessing at then being $S\subseteq U$. Label our three guesses as $T_0$, $T_1$, and $T_2$ (and note that this formulation assumes that we've made these choices beforehand; i.e., that $T_1$ is chosen without any knowledge of the value of $\left|T_0\cap S\right|$). For each of the five elements $e\in U=\{A,B,C,D,E\}$ associate a 3-bit 'inclusion code' $I_e$ that says which of our three subsets of $U$ the element is in: for instance, if our guesses are $T_0=\{A,B,C,D\}$, $T_1=\{B,C\}$ and $T_2=\{C,D\}$ then the inclusion codes are $I_A=\langle1,0,0\rangle$ (since $A\in T_0$, $A\not\in T_1$, and $A\not\in T_2$), $I_B=\langle1,1,0\rangle$, $I_C=\langle1,1,1\rangle$, $I_D=\langle1,0,1\rangle$, and $I_E=\langle0,0,0\rangle$. We'll call the number of 1s in an inclusion code its weight; in this example, the weight of $I_A$ is 1, the weight of $I_C$ is 3, etc. (Note that for our guesses to have any chance of succeeding then every $I_e$ must have positive weight; otherwise we'll never be able to detect the presence/absence of $e$. This leaves seven possible values of $I_e$, from which we'll be choosing five.)

Then the 'winning condition' that we can successfully determine any subset of $U$ based on our guesses is exactly the condition that the 32 vector sums $\displaystyle\{\sum_{e\in E}I_e : E\subseteq U\}$ are distinct (since if any two of them are the same, then the corresponding subsets of $U$ are indistinguishable).

Now, we can knock off the rest with some case-based analysis using the pigeonhole principle. First, as noted above, we trivially can't have any of the $I_e=\langle0,0,0\rangle$. Now, suppose we had e.g. $I_A=\langle1,1,1\rangle$. Then we have four other $I_e$ to distribute amongst the weight-1 and weight-2 slots. But any way you distribute those four, one of the weight-1 inclusion codes will be complementary to one of the weight-2 inclusion codes, and so they'll sum to $\langle 1,1,1\rangle$. This means that there's no solution with a weight-3 inclusion code, and so the five inclusion codes must be distributed among the six possibilities of weight 1 or 2; but however this is done, either all the weight-one slots will be used (in which case some pair of them will add to one of the used weight-two slots) or all the weight-two slots will be used (in which case the pair of weight-one slots that are used will add to one of them).

There may be a more direct way to show this based on linear algebra; another formulation of the 'all sums distinct' condition is that there's no linear combination $\sum_{e\in U}a_eI_e=\langle 0,0,0\rangle$ with the coefficients $a_e\in\{-1,0,1\}$. Now, since we have five distinct vectors in $\mathbb{N}^3$ they're clearly linearly dependent, but it's not immediately clear to me that the usual proofs for linear dependence (e.g., Gram-Schmidt orthogonalization) won't lead to coefficients larger than 1. If that hole can be patched, though, it's obviously a much cleaner proof.

Answer 3

Here is the proof, if I understood the task correctly.

Subset $S$ either includes or doesn't each letter, so there are $2^5=32$ possible subsets. So you have $32$ combinations to chose between.

If guess $T$ includes $N$ letters it allows to chose between $N$ groups of combinations.
One guess may include all 5 letters (this is the best situation from information point of view). It gives nothing to guess $T=\{A,B,C,D,E\}$ two times, so another guess must include 4 or less letters. In total you can chose between 20 or less combinations in two guesses. Therefore you will need 3rd guess to get additional information. Plus you will need 4th one $T=S$ to guess $S$ correctly.

P.S Of course, you get guess the number correctly in 3 guesses, even in 1 guess, but you have to be lucky for this.