Bob and Alice send shipments of raw diamonds to one another in envelopes. Each shipment passes through the hands of exactly three of five possible middlemen, known by their numerical pseudonyms M1, M2, M3, M4, and M5. For secrecy, each actor (Bob, Alice, and each middleman) has a mailbox-like strongbox. To transfer goods to X, one puts an envelope in the mail slot of X's strongbox. X will come in when he or she is sure not to be watched and will remove the envelope from the strongbox. Only the owner of the strongbox can remove the envelope.
Whenever an envelope shipment arrives either to Bob or to Alice, the two confer. The receiver tells the sender whether all the diamonds have arrived or not. You can trust Bob and Alice to tell the truth. The two trust one another completely as well.
Warm-Up:
Suppose that at most one middleman is a thief and the thief will always steal. How can Bob and Alice determine who the thief is (if there is one) after at most three shipments?
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.
Solution to Warm-Up:
try using M1 M2 M3 as intermediaries in the first shipment
if something is stolen, then try M3 M4 M5 in
the second shipment
if something is stolen
then the thief must be M3
else (M3 M4 M5 are non-thieves) try M1 M4 M5 in
the third shipment
if something is stolen
then the thief is M1
else the thief is M2
end if
end if
else (nothing is stolen in first shipment)
try M1 M2 M4 in the second shipment
if something is stolen
then M4 is thief
else try M1 M2 M5 in the third shipment
if anything is stolen
then M5 is the thief
else there are no thieves
end if
end if
End of Warm-Up
The reasoning can get involved as you can see. Here's a harder problem.
1. As before, there are still five middlemen and Bob and Alice choose three for each shipment. Now, however, there may be as many as two thieves. As before, a thief will steal every time the opportunity arises. In how few shipments can Bob and Alice determine who the thieves are, whether there are zero, one, or two?
Here is a problem I haven't solved:
2. Suppose that the envelope is sealed at the shipment source. Stealing the shipment requires breaking the seal, but the letter always arrives at the destination even if some or all of its contents have been removed. Suppose further that, on the cover of the envelope, each middleman indicates in pencil whether the envelope arrived in good condition or not. Middlemen can lie and later middlemen can erase and change what other middlemen have written. Only thieves will lie or change anyone else's answers. How many shipments are required then?
