As we saw in our discussion of The Tolls of Elsinore, shippers could increase their profits by understating their cargoes' value strategically. Some shippers figured out that they could do even better by bribing the two inspectors who came on board. The King heard that among his eight inspectors at least three were corrupt. The King reasoned that the corrupt inspectors knew one another and that only if both inspectors entering a ship were corrupt would they take the bribe.

So the King arranged with some shippers he trusted to put the inspectors to the test. The trusted ship captains would offer bribes to the inspectors and would then report the cheating pairs to the King. The King thought he would first figure out who was cheating, before punishing anyone.

To that end, however, the King needs some mathematical help. He first asks you to instruct the inspector general to arrange the inspection teams such that a different pair visits each ship. For example, Nils and Bjorn might go to the first ship, Nils and Anders to the second and Bjorn and Anders to the third. Besides those three, the inspectors are Dagmar, Ejnar, Gudrun, Harald and Christofferson.

How many different ships would be needed to ensure that each ship received a distinct pair of inspectors?

The number of distinct pairs that can be created from eight people is "8 choose 2" or 28. One way to figure this out from first principles is to observe that if there were two people, then there is only one pair. With three people, the third person could be paired with either of the first two so there is 1 + 2. With four people, the fourth person could be paired with any of the first three, so 1 + 2 + 3. With 8 people, we have 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

The King decides that this approach would require too many honest captains. He asks you whether fewer ships might be sufficient to detect any number of cheating inspectors from three on up.

1. How much better can you do (that is, what is the fewest number of ships needed to guarantee finding all the cheaters) if there are at least three cheaters?

Hint: As you'll see, it's easier to find cheaters when there are more of them.

2. Suppose that the cheaters realize they are being put to the test. Each cheater resolves to cheat if and only if he is with another cheater and neither he nor the other cheater took a bribe on the previous ship either of them visited (which may or may not be the same). How many ships would you need then?

Comments