Pug’s Place

Never gonna give you up…

The Pirate Problem

January 25th, 2006 | Category: ideaspace

I spent last night at the Swamp with a team of folks from Ultimate Software, a group from Weston, FL, and a few other prospective hires. They… read this blog (Hi!) and I have an interview with them in a few hours. At any rate, the last things we talked about last night were various logic puzzles and riddles. I offered to bring an entertaining one along to my interview with them this afternoon and I thought I’d post it here for your entertainment.

I’ll put up solutions in a few days. Note that “political” solutions aren’t valid answers since these are “logic” puzzles. ;) Also, googling for the answer isn’t a valid solution method, either.

These were given to the ACM Programming Team last year by Dave Small.

The Hard Problem

You have 1000 pirates who are all extremely greedy, heartless, bloodthirsty and perfectly rational. They’re also aware that all the other pirates share these characteristics. They’re all ranked by the order in which they joined the group, from pirate one down to a thousand.
They’ve stumbled across a huge horde of treasure and they have to decide how to split it up. Every day the lowest ranked pirate proposes a (not necessarily equal) way to divide the booty and then the other pirates vote on whether to follow this method. If more than 50% of them vote to split it the treasure gets split. Otherwise, they kill the lowest ranking pirate and repeat the process until more than half of the pirates decide to split the treasure.
The question is: if you are pirate N, what solution do you propose to ensure that you do not walk the plank?

The Easier Problem

You have 1000 pirates who are all extremely greedy, heartless and perfectly rational. They’re also aware that all the other pirates share these characteristics. They’re all ranked by the order in which they joined the group, from pirate one down to a thousand.
They’ve stumbled across a huge horde of treasure and they have to decide how to split it up. Every day they will vote to either kill the lowest ranking pirate or split the treasure up among the surviving pirates. If 50% or more of them vote to split it the treasure gets split. Otherwise, they kill the lowest ranking pirate and repeat the process until half or more of the pirates decide to split the treasure.
The question is: at what point will the treasure be split and what will the precise vote be?

2 Comments so far

  1. Alejandro Rivero September 19th, 2006 5:51 am

    did you put solutions, or link to these, somewhere? Also, any idea about how old the problems are? the oldest link I have found was yet from XXIth century, 2001.

  2. Pug September 19th, 2006 6:35 am

    No, I neglected putting solutions online as I specified I would in the post.

    Hard Version

    Pirate N’s goal is to appease more than 50% of the other pirates thus ensuring her survival. Since pirate N is greedy, she also wants to save as much of the booty as she can, so the solution is… (for brevity I’ll assume coins, but this works with shares of rubies, interests in vorpal scimitars, idols of flying spaghetti monsters and other loot)

    1. Give no coins to pirate N-1 since they’re a schmuck and pirate N is greedy
    2. Give one coin to pirate N-2 since that’s the best offer pirate N-2 can get
    3. Give two coins to an arbitrary set of the remaining pirates to ensure more than 50% of the vote will be in favor of the split.
      • This works because the pirates who are chosen to receive 2 coins know that if pirate N dies, pirate N-1 may not offer them any coins and will never offer more than 2.
      • Additionally, since they are perfectly rational, the pirates know that if they are not near the end of the line, they have effectively no chance of getting more than 2 coins – some other group of pirates will accept a 2-coin deal long before they become pirate N. So they vote in favor.
    4. Take the rest. Arr!

    There are actually several other solutions for any arbitrary pirate N which are more optimal, but I believe this is the only general solution for N > 4.

    The Easier Problem

    488 pirates will die.
    Looking at the problem in the reversed direction…

    1. When there are only two pirates left, pirate #2 will outvote #1 and they will split the booty.
    2. When there are 3 pirates, pirate #3 will vote to split but pirate #2 and #1 will see step #1 coming and will thus kill pirate #3.
    3. When there are 4 pirates, pirate #4 will vote to split, so will pirate #3 since #3 sees step #2 coming.
    4. When there are 5 pirates, pirate #5 will vote to split yet pirates #1-4 will vote against to maximize their individual shares.
    5. When there are 8 pirates, pirates #5-8 will vote to split since they see step #4 coming.
    6. When there are 16 pirates, pirates #9-16 will vote to split since they otherwise die.
    7. And so on for powers of 2. Since the largest power of 2 less than 1000 is 512, 488 pirates die.

Leave a reply