Wednesday, May 28, 2008

Puzzle: 15 pirates, 100 Coins - how to distribute?

Puzzle: There are fifteen pirates all ranked by their years of service i.e., Pirate 15 is having 15 years of service, Pirate 14 is having 14 years of service, and so on. They find 100 gold coins. To divide these coins they agree on the condition which says "The most senior pirate will propose a way of distributing the coins, and then all the pirates (including the one who proposed) will vote and if he gets at least 50% votes then everyone will accept that proposal otherwise he'll be forced to leave the place without any coin. The next senior most will follow the same... and so on until a proposal gets approved."

Considering that all the pirates are able enough to see which proposal will ensure them the maximum gain. Their prefernces will be in the order to stay alive first, maximize the number of gold coins, and if at all there are equal outcomes in two situations then to have fewer number of pirates left with them.

After thinking for a while, the most senior pirate proposes a solution, which maximizes his share of gold coins, and others also accept that as none could think of any better alternative. What plan did the most senior pirate suggest?

Solution: The key here is to think about the pirates who the most senior pirate needs to take care of while proposing a plan. Okay... what will be the least number of pirates left to divide the gold coins among themselves? The least number will 1 when all other pirates get their plans dumped and hence leave the place. Now, if there is only 1 pirate left then he'll obviously get his own vote which will ensure 100% vote for him and he'll take home all the 100 coins.

Similarly, if there are only 2 pirates left then pirate 2 will be the most senior among them and he'll 50% vote by his own vote only and hence will take home all 100 coins. So, in this case pirate 1 won't get any coins.

If there are 3 pirates then the pirate 3 being the most senior may offer only 1 gold coin to pirate 1 to ensure his vote and will safely take home the rest 99 coins. Pirate 1 knows that if he dumps the plan proposed by pirate 3 then pirate 3 will leave the place and pirate 2 being the senior most will take home all 100 coins. So, pirate 1 will have no ther choice but to accept the plan prposed by pirate 3 in this case.

If there are 4 pirates then pirate 4 being the senior most pirate requires one more vote to ensure 50%. He knows that in case there are only 3 pirates left then pirate 2 gets 0 coins, so he'll offer 1 gold coin to pirate 2 and pirate 2 will have no other option but to accept it. Pirate 4 will take home 99 coins.

If there are 5 pirates then pirate 5 being the senior most requires 2 votes except his own vote to ensure 50%+. So, he will offer 1 coin to pirate 3 and 1 coin to pirate 1, which pirate 3 and pirate 1 will have to accept because in absence of pirate 5, pirate 4 will become the senior most and in that case pirate 1 and pirate 3 will get nothing. So, pirate 5 will take home 98 gold coins.

Similarly, if there are 15 pirates then pirate 15 being the most senior requires 7 other votes except his own vote to ensure 50%+ and hence he'll offer 1 coin each to all the pirates who won't get anything in absence of pirate 15. These pirates will be pirate 13, pirate 11, pirate 9, pirate 7, pirate 5, pirate 3 and pirate 1. All these seven pirates will accept the plan proposed by pirate 15 because they know that if he leaves and pirate 14 becomes the senior most then they'll go home with 0 coins :-)


No comments: