# Clever Danes

Image: Cloe Liane Shasha

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.

Warm-Up:

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

Solution to warm-up:

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.

Problems:

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?

Hint: You don't need many more.

Courant Institute of Mathematical Sciences, New York University. Dennis's most recent puzzle book, Puzzles for Programmers and Pros, was published this past May by John Wiley and Sons/Wrox.

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• News | 2 hours ago | 2

### Mercury Is Shrinking More Than Thought

• Plugged In | 3 hours ago

### Air pollution stretches from Beijing to Shanghai, as seen from space

• Observations | 4 hours ago

### Are Genes Really Selfish? [Video]

• News | 4 hours ago | 1

### Unraveling the Mystery of How Antidepression Drugs Work

• News | 5 hours ago | 4

## Latest from SA Blog Network

• ### Blast from the Past: A Few Science Highlights from 1994

Cocktail Party Physics | 1 hour ago
• ### Public Domain Day: January 1st

Compound Eye | 2 hours ago
• ### Air pollution stretches from Beijing to Shanghai, as seen from space

Plugged In | 3 hours ago
• ### Are Genes Really Selfish? [Video]

Observations | 4 hours ago
• ### Conversation on Daydreaming with Jerome L. Singer

MIND
Beautiful Minds | 5 hours ago

## Science Jobs of the Week

Clever Danes

X

Give a 1 year subscription as low as \$14.99

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

No, I would like to create a new account with my profile information.

X

Are you sure?

X