Playing Mastermind against an angel and the devil

Question

This puzzle is based on a card game. There are 7 suspects and 3 of them committed a crime. The game contains 35 cards that contain the 35 possible choices of 3 out of the 7 suspects. One card is drawn at random and hidden from you, these are the 3 criminals you are supposed to identify. You are then shown some of the other cards and told for each of them how many of the criminals are on the card. You then need to deduce from this information which of the 7 suspects are the 3 criminals. If you don't have enough information you can ask for another card.

Example (label the suspects A, B, .., G for convenience) :

Suppose the actual criminals are B, D and G, you don't know this, this is what you have to find out.

You are shown the card A, D, F and are told that 1 of these 3 suspects is a criminal. Next you are shown the card B, D, F and are told that 2 of these 3 suspects are criminals. You can already draw some conclusions but you cannot yet identify the 3 criminals without guessing so you would need another card.

In the original game the cards you are shown are drawn at random and so the number of cards you need to see to identify the 3 criminals depends on the cards drawn.

For this puzzle you first play a round against an angel. The angel wants you to deduce the criminals with as few cards as possible and chooses which of the remaining cards they are going to show you. How many cards do they have to show you at minimum so that you can deduce the correct 3 criminals (no guessing)?

Second you play a round against the devil. The devil wants to show you as many cards as they can without allowing you to deduce the three criminals. But after seeing enough (distinct) cards eventually you will be able to deduce the answer. What is the maximum number of cards the devil can show you so that you cannot uniquely deduce the three criminals?

One can brute-force this on a computer but there is no need for that. This can be solved with pen-and-paper.

Answer 1

For the angel:

Two cards are minimal.

They can show you two cards containing the four innocent people, and you know the three unshown people are the criminals.

For the devil:

I believe fifteen cards are maximal.

As long as there are a pair of suspects (one innocent, one criminal) where you always see both or neither of them, you will never be able to tell which is which.

E.g. If the devil shows you the following cards, you know A and B are criminal, but cannot tell if C or D is the third criminal:

 A,B,E   2
 A,B,F   2
 A,B,G   2
 A,C,D   2
 A,E,F   1
 A,E,G   1
 A,F,G   1
 B,C,D   2
 B,E,F   1
 B,E,G   1
 B,F,G   1
 C,D,E   1
 C,D,F   1
 C,D,G   1
 E,F,G   0 

Answer 2

I don't know if it's optimal, but the devil can show at least

15 cards without allowing a definitive deduction.

I determined this by

assuming an alternate scenario where one of the criminals was different (e.g. the criminals are ABD (assumed) instead of ABC (actual). Then I looked at every card that would provide the same answer for both scenarios. There are 15 of them: ABE, ABF, ABG, ACD, AEF, AEG, AFG, BCD, BEF, BEG, BFG, CDE, CDF, CDG, EFG.
After showing these 15 cards, it is still impossible to determine whether the solution is ABC or ABD.

Answer 3

I used integer linear programming to show that the maximum for the devil is

$15$

Rename the suspects $0,1,\dots,6$ instead of $A,B,\dots,G$. The following SAS code solves the problem:

proc optmodel;
   /* declare parameters */
   num numSuspects = 7;
   num numCriminals = 3;
   num numSuspectsPerCard = 3;

   /* declare sets, using bitwise and (BAND) function for subsets */
   set SUSPECTS = 0..numSuspects-1;
   set CARDS = {c in 0..2^numSuspects-1: card({i in SUSPECTS: band(2^i,c)}) = numSuspectsPerCard};
   set SCENARIOS = 1..2;

   /* ShowCard[c] = 1 if card c is shown; 0 otherwise */
   var ShowCard {CARDS} binary;

   /* IsCriminal[s,sc] = 1 if suspect s is a criminal in scenario sc; 0 otherwise */
   var IsCriminal {SUSPECTS, SCENARIOS} binary;

   /* IsDifferent[s] = 1 if suspect s is a criminal in exactly one of the two scenarios; 0 otherwise */
   var IsDifferent {SUSPECTS} binary;

   /* devil's objective is to maximize the number of cards shown */
   max NumCardsShown = sum {c in CARDS} ShowCard[c];

   /* choose the right number of criminals */
   con Cardinality {sol in SCENARIOS}:
      sum {s in SUSPECTS} IsCriminal[s,sol] = numCriminals;

   /* the two scenarios must differ for at least 2 suspects */
   con DifferentLB {s in SUSPECTS}:
      IsCriminal[s,1] + IsCriminal[s,2] >= IsDifferent[s];
   con DifferentUB {s in SUSPECTS}:
      IsCriminal[s,1] + IsCriminal[s,2] <= 2 - IsDifferent[s];
   con SomeDifferent:
      sum {s in SUSPECTS} IsDifferent[s] >= 2;

   /* for each card shown, the number of criminals on the card must be the same in both scenarios */
   con SameCount {c in CARDS}:
      ShowCard[c] = 1 implies
      sum {s in SUSPECTS: band(2^s,c)} IsCriminal[s,1]
    = sum {s in SUSPECTS: band(2^s,c)} IsCriminal[s,2];

   /* call the MILP solver */
   solve;

   /* print the solution */
   for {c in CARDS: ShowCard[c].sol > 0.5} put c binary7.;
   print IsCriminal IsDifferent;
quit;

The shown cards ($3$-subsets expressed as binary numbers) are:

0001101
0001110
0010011
0011100
0100011
0101100
0110001
0110010
1000011
1001100
1010001
1010010
1100001
1100010
1110000

The other decision variables in the optimal solution take the following values:

\begin{matrix} \text{suspect} & \text{IsCriminal[suspect,1]} & \text{IsCriminal[suspect,2]} & \text{IsDifferent[suspect]} \\ \hline 0 &1 &1 &0 \\ 1 &1 &1 &0 \\ 2 &1 &0 &1 \\ 3 &0 &1 &1 \\ 4 &0 &0 &0 \\ 5 &0 &0 &0 \\ 6 &0 &0 &0 \\ \end{matrix}