|
5 Pirates
Five ferocious pirates sacked Shanghai and escaped with 100
gold sovereigns. It's now time to divide the booty between them. In
decreasing order of seniority, they are: Able Ahab, Barnacle Bill,
Crusty Chris, Dangerous Dave, and Eloquent Ed. Whatever they do, in
dividing the loot, they must obey the Pirate's Code.
The Pirate's Code: The most junior pirate begins by suggesting a distribution of the gold coins then all the pirates take a vote. If at least half of the pirates reject the offer then the junior pirate is executed and the bargaining continues with the next most junior pirate. Otherwise, the offer is accepted. The Puzzle: Assume that the pirates are clever logicians, so that they can analyze this problem completely. Also assume that the pirates have the following priorities (in order): to protect their own lives, to maximize their profits, to kill their fellow pirates. What distribution of the gold sovereigns should Ed propose? Post your comments and solutions to the blog. Further thoughts: If you manage to solve this problem, think about what would happen if there were 6 pirates. To start with, we need to clarify one of the conditions. Rather than saying that the pirates try 'to maximize their profits' (a somewhat vague notion), we'll insist that each pirate tries to maximize their minimum profit. For example, Ahab may be faced with two choices. Following the first path, he may win 90 gold coins or 10 gold coins, depending on the choices of the other pirates. However, let's suppose that following the second path he could win 50 gold coins or 11 gold coins. According to our principle, he'd choose the second path. The reason is that the minimum winnings are 10 coins and 11 coins respectively. So the second path maximizes his minimum profit. Using this idea, you should be able to solve the 6 pirates problem, then solve the n-pirate problem for arbitrary n. Can you write a computer program that simulates the arbitrary problem?  Stumble It!
Hints will appear here! It may seem intuitively obvious that Ed should distribute the coins equally. However, Ed can actually do much better than this and as he's greedy, he will! Remember that the other pirates will vote for Ed's proposal only if they know that they would be worse off if they didn't. In particular, if they expect the same financial outcome whether or not they vote for Ed, then they will choose to have him executed (because they are bloodthirsty!) Suppose there were only four pirates, Ahab, Bill, Chris, and Dave. Suppose we also knew the solution to the corresponding four pirates problem. Then we'd be able to deduce the answer to the five pirate problem. Recursively, we need to know the solution to the three (and hence two) pirate problem. In the two pirate problem, with just Ahab and Bill, there's only one, rather unfortunate, consequence for Bill no matter what the distribution. Using this, work forwards to find the solution to the five pirate problem Due to Ahab's bloodthirstiness, if there's only him and Bill, Ahab will always choose to execute Bill and then take all the money (even if Bill offers him all the money). This means Bill will never vote for a situation in which only he and Ahab are left. Now suppose Ahab, Bill, and Chris are the only pirates. Chris needs to convince one other pirate to vote for him (to get a majority). He knows that Bill will vote for him no matter what, so he chooses to take all the coins.
Let's introduce Dave. We know Ahab and Bill will accept any positive offer of coins and Chris will reject any offer. So we offer Ahab and Bill one coin each.
Finally, for the original problem, we know that Dave won't accept an offer of less that 99 coins, Chris will accept any positive offer and Ahab and Bill will each accept any offer of at least 2 coins. In this case, there are two possible optimal solutions:
and:
|
|