Blogosophy

The Perspicacious Pirate Puzzle

Here's the second puzzle (which I was able to solve):

There's a group of pirates who have the following scheme for dividing booty: The pirates are ranked by ferocity. Starting with the most ferocious pirate, the pirate will propose a division of the loot (specifying exactly which pirate gets how much) and the pirates take a vote. If the majority vote for that division, it passes. In case of ties, it also passes. If it fails, then the pirates overpower the proposer and make him walk the plank, then repeat the whole process with the new most ferocious pirate proposing a division.

Suppose there are 100 pirates and the booty consists of 100 pieces of gold. What will be the winning proposal?

Again, start with the simplest case (let's number the pirates 1-100, with 100 being the most ferocious):

If there was only one pirate, he would propose that he keeps all 100, and that passes. Not too interesting.

What if there were two pirates? Well, since ties go to the proposer, the pirate 2 would propose the division 0 for 1, 100 for 2, and it would pass. Still not too enlightening.

How about 3 pirates? Well, pirate 3 knows that if his proposal doesn't pass, he walks the plank, and the pirate 2 will get 100. So pirate 2 will always vote against pirate 3's proposal if it gives him less than 100. But the pirate 1 gets 0 if pirate 2 has his way, so he'll vote in favor of anything that gives him more. So if 3 proposes, 1-0-99 it will be two votes to 1, and will pass. Now we're getting somewhere.

With four pirates, 1 and 3 will want the division 1-0-99 and won't accept less, but 2 will take anything better than 0, and since ties go to the proposer, 4 will win with the division 0-1-0-99.

5 will thus propose 1-0-1-0-98 to secure three votes, etc.

So with 100 pirates, the winning proposal will look like:

0-1-0-1-....-1-0-50

This result is, I think, pretty surprising. Not only is the distribution wildly uneven, but it depends on the parity of the number of pirates (which pirates benefit depends completely on whether there are an odd or even number of pirates). Which just goes to show that when you consider these sorts of I know that you know puzzles (the less ferocious pirates are only willing to accept piddling amounts like 1 because they can see that if they force a second vote it will go even worse), even simple rules can lead to complex outcomes.