Welcome to techInterview, a site for technical interview questions, brain teasers, puzzles, quizzles (whatever the heck those are) and other things that make you think!
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, and 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? What plan would the most senior pirate propose on a boat full of 15 pirates?
If there were three pirates, Pirate 3 needs one other person to vote for his plan. The trick to this puzzle is understanding that if Pirate 3’s plan is voted down, he would die and then there would be only two pirates on the boat. We already figured out what happens when there are only two pirates on the boat. In the case of two pirates, Pirate 1 receives nothing. So Pirate 3 can simply offer Pirate 1 a single gold coin and ensure his vote. As a perfectly rational pirate knows, one coin is better than no coins at all!
If there were four pirates, Pirate 4 needs to convince one other person to guarantee 50% of the vote. He could give Pirate 1 two gold coins, but his greed makes him realize that if his plan is scuttled, there will only be three pirates on the boat. When there are three pirates left, Pirate 2 knows he will get nothing; so Pirate 4 buys Pirate 2’s vote with one gold coin.
Finally when there are five pirates, Pirate 5 needs two other cohorts. He realizes that if he dies, Pirate 1 and Pirate 3 will get zero gold. So he offers each of them one doubloon and makes off with the other 98 pieces o’ eight.
The pattern should be evident now. When 15 pirates are on board, Pirate 15 needs 7 other people to vote for him. He recruits pirates 13, 11, 9, 7, 5, 3 and 1 with one coin each, leaving 93 coins for Pirate 15. Those pirates will all vote for Pirate 15’s plan because if they don’t, they’ll be stuck with Pirate 14’s plan in which they all get nothing.