Let's Play A Game

Here is an algorithm which can guess any subset in 4 guesses.

• A = #({Sue, Arron, Pete} $\cap$ S)
• B = #({Pete, Dan, Calvin} $\cap$ S)
• C = #({Sue, Pete} $\cap$ S)
• D = #({Pete, Calvin} $\cap$ S)

You should be able to reason out the chosen subset.

Now here is a list of the answers you can get for every possible subset.

$\left( \begin{array}{cc} \left (A,B,C,D\right) & S \\ \left (0,0,0,0\right ) & \{\} \\ \left (1,0,1,0\right ) & \{\text{Sue}\} \\ \left (1,0,0,0\right ) & \{\text{Arron}\} \\ \left (1,1,1,1\right ) & \{\text{Pete}\} \\ \left (0,1,0,1\right ) & \{\text{Dan}\} \\ \left (0,1,0,0\right ) & \{\text{Calvin}\} \\ \left (2,0,1,0\right ) & \{\text{Sue},\text{Arron}\} \\ \left (2,1,2,1\right ) & \{\text{Sue},\text{Pete}\} \\ \left (1,1,1,1\right ) & \{\text{Sue},\text{Dan}\} \\ \left (1,1,1,0\right ) & \{\text{Sue},\text{Calvin}\} \\ \left (2,1,1,1\right ) & \{\text{Arron},\text{Pete}\} \\ \left (1,1,0,1\right ) & \{\text{Arron},\text{Dan}\} \\ \left (1,1,0,0\right ) & \{\text{Arron},\text{Calvin}\} \\ \left (1,2,1,2\right ) & \{\text{Pete},\text{Dan}\} \\ \left (1,2,1,1\right ) & \{\text{Pete},\text{Calvin}\} \\ \left (0,2,0,1\right ) & \{\text{Dan},\text{Calvin}\} \\ \left (3,1,2,1\right ) & \{\text{Sue},\text{Arron},\text{Pete}\} \\ \left (2,1,1,1\right ) & \{\text{Sue},\text{Arron},\text{Dan}\} \\ \left (2,1,1,0\right ) & \{\text{Sue},\text{Arron},\text{Calvin}\} \\ \left (2,2,2,2\right ) & \{\text{Sue},\text{Pete},\text{Dan}\} \\ \left (2,2,2,1\right ) & \{\text{Sue},\text{Pete},\text{Calvin}\} \\ \left (1,2,1,1\right ) & \{\text{Sue},\text{Dan},\text{Calvin}\} \\ \left (2,2,1,2\right ) & \{\text{Arron},\text{Pete},\text{Dan}\} \\ \left (2,2,1,1\right ) & \{\text{Arron},\text{Pete},\text{Calvin}\} \\ \left (1,2,0,1\right ) & \{\text{Arron},\text{Dan},\text{Calvin}\} \\ \left (1,3,1,2\right ) & \{\text{Pete},\text{Dan},\text{Calvin}\} \\ \left (3,2,2,2\right ) & \{\text{Sue},\text{Arron},\text{Pete},\text{Dan}\} \\ \left (3,2,2,1\right ) & \{\text{Sue},\text{Arron},\text{Pete},\text{Calvin}\} \\ \left (2,2,1,1\right ) & \{\text{Sue},\text{Arron},\text{Dan},\text{Calvin}\} \\ \left (2,3,2,2\right ) & \{\text{Sue},\text{Pete},\text{Dan},\text{Calvin}\} \\ \left (2,3,1,2\right ) & \{\text{Arron},\text{Pete},\text{Dan},\text{Calvin}\} \\ \left (3,3,2,2\right ) & \{\text{Sue},\text{Arron},\text{Pete},\text{Dan},\text{Calvin}\} \\ \end{array} \right)$

Since, for every possible subset, (A,B,C,D) is unique as in the list, the algorithm works

Let S, A, P, D, and C represent Sue, Arron, Pete, Dan, and Calvin. We can get enough information to know who all is in the subset by guessing (S,A,P,D,C), (P,D), (A,D), (S,D), which is four guesses.

To prove that this works, consider 3 cases: if there are 5 people in the subset, if there are 4 people in the subset, and if there are 3 people in the subset. The 0, 1 and 2 people in the subset will all be inverses of the 5, 4, or 3 cases, so we can ignore those without loss of generality.

If there are 5 people in the subset, your first guess will tell you such, and you will know the exact subset.

If there are 4 people in the subset, of the (P,D), (A,D) and (S,D) guesses, we will have one of the following responses (not necessarily in order of guesses):

-All 3 guesses coming up 1 person, in which case we know that everyone but Dan is in the subset.

-2 guesses coming up with 2 people, the 3rd coming up with 1 person, in which case we know that the person in the guess that only had 1 person in the subset who isn't Dan is the only one not in the subset.

-All 3 guesses coming up as 2 people, in which case we know that Calvin is the only person not in the subset.

If there are 3 people in the subset, we have 2 cases, either:

1. The last 3 guesses all come up with 1 person, in which case we know that Dan and Calvin are the only ones not in the subset.

2. At least one of the 3 guesses comes up either 2 people or 0 people, in which case we can derive the status of Dan, and thus derive the status of Sue, Arron, and Pete, and Calvin would be whatever is left over.

Proving that we cannot do it in 3 guesses is a bit trickier, but here is how (i think, if i haven't made any mistakes, which i very well might have): firstly, look at people as if they are divided into groups with known total (a group being defined as a set of people who we know how many of them are in the initial subset). We want to get all of these groups into groups of size 1. Note that this does not imply that you need 5 guesses: by guessing (S,A,P) followed by (P,D,C) we have divided the people into 3 groups since we know what the group consisting of P's total is.

Firstly, we start by knowing that we need to guess everyone at least once to put everyone in a group. This leads to two cases: you guess everyone as your first guess, or it takes two guesses to put everyone into a group.

In the first case, we have everyone in one group to start with. We need to divide these people into groups of size 1. However, this is impossible in two guesses, as everyone will be divided into one of these groups: -in both the second and third guess -in the second, but not third guess -in the third, but not second guess -in neither the second or third guess Leaving aside the issue that the last group isn't necessarily guaranteed to have a known total, this is still only 4 groups, and we need 5, so guessing all 5 people at the start will not let know for sure who is in the subset.

If we use two guesses to group everyone, we are left with the possibilities of 3 groups of size 1,2,2 or 3 groups of size 1,1,3. We could divide the people into 2 groups, but having one person of intersection between your first two guesses is always better because you can then know wether or not that person is in the initial subset. For example, a guess of (S,A) followed by (A,P,D,C) is always better than (S) followed by (A,P,D,C) since they both provide the same information, except that the first one tells you wether or not Arron is in the initial subset.

Now, if the groups are 1,1,3, there is no way to divide the group of 3 into 3 groups of 1. If the groups are of sizes 1,2,2, then you would need to divide both groups of 2 into two groups of 1. The only way to possibly do this would be to guess one person from each group of 2. However, this does not tell you the answer in the case that both groups have 1 person in the initial subset and the third guess tells you that one of the people you guessed was in the initial subset.

Let be $A=\{a_1, a_2, a_3, a_4, a_5\}$ . Let be $T$ the 'set of decision' such that $T=\{T_1, T_2, T_3, T_4\}$ I choose at first $T_1=\{a_1,a_2\}$ . Than

$1a. \hspace{5pt} \displaystyle |T_1 \cap S|=0 \hspace{5pt} \Longrightarrow \hspace{5pt} a_1 \notin S \hspace{3pt} AND \hspace{3pt} a_2 \notin S$

$2a. \hspace{5pt}\displaystyle |T_1 \cap S|=1 \hspace{5pt} \Longrightarrow \hspace{5pt} a_1 \in S \hspace{3pt} XOR \hspace{3pt} a_2 \in S \hspace{3pt}$

$3a. \hspace{5pt}\displaystyle |T_1 \cap S|=2 \hspace{5pt} \Longrightarrow \hspace{5pt} a_1 \in S \hspace{3pt} AND \hspace{3pt} a_2 \in S$

$1a.$ and $2a.$ tell us whether $\{a_1, a_2\}\in S$ or not. Regarding $2a.$ we don't know which one between $a_1$ and $a_2$ is in $S$ , so we choose $T_2=\{a_2,a_3\}$ :

$1b. \hspace{5pt} \displaystyle |T_2 \cap S|=1 \hspace{5pt} \Longrightarrow \hspace{5pt} a_1 \in S \hspace{3pt} XOR \hspace{3pt} a_2 \in S \hspace{3pt} XOR \hspace{3pt} a_3 \in S$

$2b. \hspace{5pt} \displaystyle |T_2 \cap S|=2 \hspace{5pt} \Longrightarrow \hspace{5pt} a_2 \in S \hspace{3pt} XOR \hspace{3pt} a_3 \in S$

$2b.$ tells us that $\{a_2, a_3\}\in S$ and $a_1 \notin S$ . Regarding $1b.$ we don't know which one among $a_1$ , $a_2$ , $a_3$ is in $S$ , so we choose $T_3=\{a_3,a_4\}$ :

$1c. \hspace{5pt} \displaystyle |T_3 \cap S|=1 \hspace{5pt} \Longrightarrow \hspace{5pt} a_1 \in S \hspace{3pt} XOR \hspace{3pt} a_2 \in S \hspace{3pt} XOR \hspace{3pt} a_3 \in S \hspace{3pt} XOR \hspace{3pt} a_4 \in S$

$2c. \hspace{5pt} \displaystyle |T_3 \cap S|=2 \hspace{5pt} \Longrightarrow \hspace{5pt} a_3 \in S \hspace{3pt} XOR \hspace{3pt} a_4 \in S$

$3c. \hspace{5pt} \displaystyle |T_3 \cap S|=0 \hspace{5pt} \Longrightarrow \hspace{5pt} a_3 \notin S \hspace{3pt} AND \hspace{3pt} a_4 \notin S$

$2c.$ tells us that $\{a_1,a_3,a_4\} \in S$ , and $a_2 \notin S$ . $3c.$ tells us that $a_2 \in S$ . Regarding $1c.$ we don't know which one among $a_1$ , $a_2$ , $a_3$ , $a_4$ is in $S$ , so we choose $T_4=\{a_4,a_5\}$ :

$1d. \hspace{5pt} \displaystyle |T_4 \cap S|=1 \hspace{5pt} \Longrightarrow \hspace{5pt} a_1 \in S \hspace{3pt} XOR \hspace{3pt} a_2 \in S \hspace{3pt} XOR \hspace{3pt} a_3 \in S \hspace{3pt} XOR \hspace{3pt} a_4 \in S \hspace{3pt} a_5 \in S$

$2d. \hspace{5pt} \displaystyle |T_4 \cap S|=2 \hspace{5pt} \Longrightarrow \hspace{5pt} a_4 \in S \hspace{3pt} AND \hspace{3pt} a_5 \in S$

$3d. \hspace{5pt} \displaystyle |T_4 \cap S|=0 \hspace{5pt} \Longrightarrow \hspace{5pt} a_4 \notin S \hspace{3pt} AND \hspace{3pt} a_5 \notin S$

$1d.$ tells us that $S=\{a_1, a_3, a_5\}$ . $2d.$ tells us that $\{a_2, a_4, a_5\} \in S$ and $\{a_1, a_2\} \notin S$ . $3d.$ tells us that $\{a_3, a_1\}\in S$ and $\{a_2, a_4, a_5\} \notin S$ . I didn't list all possible $2^5$ sets $S$ , but just the $\{1,1,1,1,\}$ situation that leads to $S=\{a_1, a_3, a_5\}$ . Each $S$ , infact, could be see as a sequence of $\{d_1,d_2,d_3,d_4\}$ where $d_i=dim(T_i \cap S)$ , $i=1,...,4$ .

There are 5 elements in the set. Any time you guess, he´ll tell you if you are right or wrong. As there are 5 elements, if you guess 4 times, you already know how many elements are in T. That´s the minimum, anymore than that and you are already guessing all the elements, and there´s no game. Less than that, and you could still leave any other combination.

[This is not a solution.]

Clearly, at most 5 guesses are needed, where you make the guesses of {Sue}, {Arron}, {Pete}, {Dan}, {Calvin}. This would tell you which people are in $S$ , and who are not in $S$ , thereby determining $S$ .

However, we can actually do slightly better, and need at most 4 guesses. (See Agnishom's solution)

I'm not sure why 3 guesses is insufficient, and that has yet to be demonstrated.