Thursday, April 15, 2010
5 Pirates Fight for 100 Gold Coins
Five pirates discover a chest containing 100 gold coins. They decide to sit down and devise a distribution strategy. The pirates are ranked based on their experience (Pirate 1 to Pirate 5, where Pirate 5 is the most experienced). The most experienced pirate gets to propose a plan and then all the pirates vote on it. If at least half of the pirates agree on the plan, the gold is split according to the proposal. If not, the most experienced pirate is thrown off the ship and this process continues with the remaining pirates until a proposal is accepted. The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 5 devises a plan which he knows will be accepted for sure and will maximize his gold. What is his plan?
Subscribe to:
Post Comments (Atom)
This is an example of greedy algorithm.
ReplyDeleteConsider pirates 5,4 and 3 have been thrown overboard, and only 1 and 2 remain. Since 2 has the casting vote, he can keep all coins for himself, and give none to 1.
Now, consider 5 and 4 are thrown overboard, and 1,2,3 remain. While making the decision about distribution, 3 knows that if he is overthrown, 1 will not get any coins. So he offers a single coin to 1, and keeps the rest to himself, giving none to 2.
Now, consider 5 is thrown overboard, and 1,2,3,4 remain. 4 makes the decision, and he knows that if he is killed, 2 will not get anything. So to get 2's vote, he gives 0 coins to 1, 1 coin to 2, 0 to 3 and keeps 99 for himself.
In the same way, when 5 is making a decision, he knows that he needs to get votes from 1 and 3, since they will not get anything if he is killed. So he gives 1 coin each to 1 and 3, no coins to 2 and 4, and keeps 98 for himself.
The distribution is -
1 - 1
2 - 0
3 - 1
4 - 0
5 - 98