From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

This problem is a famous game-theoretical scenario called the pirate game (http://en.wikipedia.org/wiki/Pirate_game). Assume the senior pirate gets to vote.

Where there is only 1 indivisible dollar: 2 pirates - The senior pirate gets it. 3+ pirates - The least senior pirate gets it.

In general, every 2 + 2^K (k >= 1) pirate will survive, while the others will die

Another Answer : Assume senior pirate also gets to vote.

Based on pirates inherent tendency -

a. They want to kill other pirates even if it does not affect their outcome -

2 pirates: Senior gets it.

3 pirates: Least-senior pirate gets it because the 2nd-least-senior pirate will vote for kill; so in order to live, he/she must give the gold to the least-senior pirate.

4 pirates: 2nd or 3rd-least-senior pirate will get gold (equally likely) because 1st will vote for kill irrespective of whether he/she gets the gold or not, and the 2nd or 3rd-least-senior pirate will vote for the plan if he/she gets the gold respectively.

5 pirates - This pirate is certainly going to die regardless of his/her proposal since there will be at least 3 pirates that don't get the gold and thus vote to kill him/her. This will eventually lead to the above situation where the 2nd or 3rd-least-senior pirate will receive the gold.

6 pirates: The 5th-least-senior pirate will vote for whatever plan the most senior pirate proposes—if the proposal falls down to him/her, then he/she is guaranteed to die as explained above. In order to get the last vote, the most senior pirate can give the gold to any of the remaining four pirates. The reason for each is below—recall, the desire to have the gold surpasses the desire to kill another pirate (e.g., if Pirate A has a 50% chance of getting the gold without killing anyone vs. a 49% chance of getting the gold and killing everyone else, he/she will choose the former):

• 4th-least-senior pirate: would agree to receive the coin, because as mentioned before, if the 5th-least-senior pirate decides, he/she will die. This will eventually result in this pirate having to give away the coin in order to live as described in the "4 pirates" situation.

• 3rd-least-senior pirate: would agree to receive the coin since there would only be a 50% chance he/she would get it as described in the eventually inevitable "4 pirates" situation.

• 2nd-least-senior pirate: same reasoning as above.

• Least senior pirate: the least senior pirate would agree to receive the coin since he/she would have a 0% chance to receive the gold as described in the eventually inevitable "4 pirates" situation.

Thus the result would be that no one dies and either the first, second, third, or fourth-least-senior pirate would receive the coin.

b. They want as many other pirates to live if it doesn't affect their outcome -

Senior most pirate gets the gold.

Back to Chapter 2