On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
1. Conceptually separate the inspectors into two groups:
Dagmar, Ejnar, Gudrun and Harald
Nils, Bjorn, Anders and Christofferson
Try every pair of the first group. That much requires six ships (and honest captains).
If you find a cheating pair, then take one member of that pair and combine him on successive ships with Nils, Bjorn, Anders and Christofferson. This approach requires only (6 + 4) = 10 ships altogether to find all the cheaters.
If you don’t find a cheating pair in the first group, try every pair of the second group. There has to be a pair that cheats in this second set because there are at least three cheaters in total and the first group had at most one.
In the worst case, you will find a cheating pair only after trying all the pairs in the second group. So, this takes an additional six ships.
Take one of the cheaters and put him together with each inspector in the first group—an additional four ships.
Altogether, you need a maximum of 16 ships (6 + 6 + 4).
2. Again separate the inspectors into two groups:
Dagmar, Ejnar, Gudrun and Harald;
Nils, Bjorn, Anders and Christofferson
Try every pair of the first group, starting with all three combinations of the triplet Dagmar, Ejnar and Gudrun.
If the first cheating pair you find involves Harald (after at most six ships), then send that pair to a new ship on which, by the rules, neither will cheat. (This step “resets” them, however, so that each can potentially cheat next time.) Then match the first cheater with Nils on one ship and the second cheater with Bjorn on another ship. If there is cheating, then match the first cheating pair again on a new ship (resetting them again). Then match the first cheater with Anders on one ship and the second with Christofferson on another ship. You will have identified all the cheaters and, in the worst case, it will have taken 12 inspections altogether (six for the first four, then possibly six for the last four).
If the first cheating pair you find is in the initial triplet of Dagmar, Ejnar and Gudrun, then there are five more inspectors to check and that takes at most eight more ships using the same kind of protocol. The total number of inspections is then 13.
If you haven't found a cheating pair in the first group, there is at most one cheater there. Try every pair of the second group, in which there has to be a pair that cheats because we know there are at least three cheaters and the first group had at most one.
In the worst case, you will find a cheating pair only after trying all the pairs in the second group. So, this takes an additional six ships.
As before, send that pair to a new ship on which, by the rules, neither will cheat. Then match the first with Dagmar on one ship and the second with Ejnar on another ship. If there is cheating, then you have found the single cheater (we know this group has no more than one). If not, then match the first with Gudrun on one ship and the second with Harald on another ship. In the worst case, you will have needed 17 inspections (6 for the first four, 6 for the second four, and 5 more for the first four, given the pair of cheaters found in the second four).
