4
$\begingroup$

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)

$\endgroup$
4
  • $\begingroup$ 1. You mean minimum number to guarantee that it is enough? 2. So you do not know that 4 is minimum? 3. Does the last guess (where T=S) count? 4. Where did you take this problem? $\endgroup$
    – klm123
    Jul 16 '14 at 17:28
  • 1
    $\begingroup$ I get that you need 5 guesses assuming that it ends only if $T=S$. Does it end if I only know for a fact what $S$ is? $\endgroup$
    – kaine
    Jul 16 '14 at 18:00
  • $\begingroup$ I think it ends for the fact that you know what $S$ is. Otherwise I don't think you can do it in 4 guesses. And it's said "until he can exactly determine $S$". $\endgroup$
    – justhalf
    Jul 17 '14 at 9:53
  • $\begingroup$ This would almost do better on math.se - there's a 'puzzle' element to it, but it's a relatively pure math question (and a pretty good one). $\endgroup$ Jul 18 '14 at 18:33
4
$\begingroup$

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

$\endgroup$
10
  • 1
    $\begingroup$ If you want to understand how it works try multiplying by $1,10,100,1000$ instead. $\endgroup$
    – kaine
    Jul 17 '14 at 14:52
  • $\begingroup$ Sorry I keep coming back to this but {ABCDE},{AB},{AC},{AD} might be a more intuitive set of 4 guesses that can simularly find this answer. $\endgroup$
    – kaine
    Jul 17 '14 at 20:02
  • 1
    $\begingroup$ Why do you need to condense them into a single number? An ordered tuple works just as well. $\endgroup$
    – user88
    Jul 18 '14 at 12:59
  • $\begingroup$ Because it is easy to understand and to show that each set end up with a single distinct integer to describe it. I think most people who don't go on Stackexchange for fun might not even know what a tuple is. $\endgroup$
    – kaine
    Jul 18 '14 at 13:04
  • 1
    $\begingroup$ What I mean is, I'm not sure there's any distinct advantage to representing the answers you receive as $(4, 2, 1, 2)$ as compared to $557$. $\endgroup$
    – user88
    Jul 18 '14 at 13:05
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Hmm, I don't see how this proves that 4 is the minimum (what if the 3rd guess can cover all the remaining possibilities?) or how this tells us how to guess correctly in 4 guesses. $\endgroup$
    – justhalf
    Jul 17 '14 at 9:44
  • $\begingroup$ @justhalf, it proves that in 3rd guess you can't always tell $T$, which is the same as $S$, because you do not know $S$ after 2 guesses, so you will need 4th guess. It doesn't tell how to guess correctly in 4 guesses, the OP didn't asked for it!! $\endgroup$
    – klm123
    Jul 17 '14 at 9:55
  • $\begingroup$ And btw when you guess 5 letters, you have $6$ combinations. And by trial and error, I think if you start by guessing 5 letters, you won't be able to determine (let alone guess) $S$ in 4 guesses in the case $|S|=2$ $\endgroup$
    – justhalf
    Jul 17 '14 at 9:59
  • $\begingroup$ @justhalf, this just improves my estimation, this doesn't contradict to it. $\endgroup$
    – klm123
    Jul 17 '14 at 10:13
  • 1
    $\begingroup$ "One guess make include all 5 letters." Do you mean, one guess must include all 5 letters? If so, why? Seems like you're making an assertion without proving that it must be so. $\endgroup$
    – Kevin
    Jul 17 '14 at 16:38

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.