2
$\begingroup$

Three witnesses of a crime did not want to directly report the criminal to a detective. The offender is one of six suspects (not the witnesses) found in the crime scene. A detective then proposed a game to the witnesses:

  • All combinations of 4 names chosen from the 6 suspects are written in different cards.

  • The first witness W1 selects a card containing the name of the criminal, then witness W2 selects another card also containing the name of the criminal, then W3 does the same, then W1 chooses again, and so on until the detective is able to discover the criminal by elimination.

What are the least number and greatest number of card selections that could be needed for the criminal to be revealed?

$\endgroup$
1
$\begingroup$

The least number of cards that can be needed is:

Three. It cannot be done with two or fewer cards, because any pair of cards contains at least two names in common, so two cards can only reduce the number of possibilities to 2.

The greatest number of cards that can be needed is:

Seven. A set of cards chosen does not determine the criminal only if there are at least two names common to all selected cards. For any given pair of names, there are $6 = {4 \choose 2}$ cards which contain both names, so it is possible that a set of six cards might not determine the criminal. The seventh card must possess one of these names and not the other, uniquely determining the criminal.

$\endgroup$
0
$\begingroup$

First note that

there are $\binom{6}{4}$ cards in total, and each card selection reveals the names of two innocent people among the suspects.

If there's replacement of cards, then the greatest possible number would be infinity, since all witnesses could just keep choosing the same card again and again. So let's assume no replacement; then

each card selection reveals a different pair of innocent people.

Least number

Three

because

in the best case, the innocent pairs revealed should be as close to disjoint as possible. First W1 eliminates two suspects, then W2 eliminates two other suspects, then W3 eliminates one of the final two reminaing (plus one that's already been eliminated). Then the answer is known.

Greatest number

Seven

because

in the worst case, witnesses continue giving no extra information for as long as possible.

After the first selection by W1, we know two innocent people. Then after W2, we must know at least three innocent people. It's then possible for W3's selection to give us no extra information: e.g. the innocent pairs selected are $AB$ then $AC$ then $BC$. But among those three innocent people there are only three ways of selecting two, so with the fourth card selection (by W1 again) we must have a fourth innocent name.

In the worst case, all witnesses could continue giving us innocent names from those same four for as long as possible. But there are only $\binom{4}{2}=6$ possible pairs to choose from four names, so the seventh card selection must give us a fifth innocent name. Which is enough to identify the criminal.

$\endgroup$

Your Answer

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