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? 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 shipmentif 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 shipmentif 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.
- 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:
- 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?
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?
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 shipmentif 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 shipmentif 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.
- 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:
- 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?
