The Rope Bridge (Easy) Four people need to cross a rickety rope bridge to get back to their camp at night. Unfortunately, their only flashlight has just 17 minutes of juice left. The bridge is too dangerous to cross without a flashlight, and it’s only strong enough to support two people at any given time. Each of the campers walks at a different speed. One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slowpoke takes 10 minutes to cross. How do the campers make it across in 17 minutes?
Five pirates discover a chest full of 100 gold coins. The pirates are ranked by their years of service, Pirate 5 having five years of service, Pirate 4 four years, and so on down to Pirate 1 with only one year of deck scrubbing under his belt. To divide up the loot, they agree on the following:
The most senior pirate will propose a distribution of the booty. All pirates will then vote, including the most senior pirate, and if at least 50% of the pirates on board accept the proposal, the gold is divided as proposed. If not, the most senior pirate is forced to walk the plank and sink to Davy Jones’ locker. Then the process starts over with the next most senior pirate until a plan is approved.
These pirates are not your ordinary swashbucklers. Besides their democratic leanings, they are also perfectly rational and know exactly how the others will vote in every situation. Emotions play no part in their decisions. Their preference is first to remain alive, next to get as much gold as possible, and finally, if given a choice between otherwise equal outcomes, to have fewer pirates on the boat.
The most senior pirate thinks for a moment and then proposes a plan that maximizes his gold, and which he knows the others will accept. How does he divide up the coins? And what plan would the most senior pirate propose if the boat had 15 pirates instead of just five?
Michael Pryor is the co-founder and president of Fog Creek Software. He runs a technical interview site at techinterview.org.
Illustrations by Roy Doty
References:
Archives