Wednesday, June 30, 2010

Pirates

I've seen this one before and haven't solved it.  Go ahead and comment answers in the blog, but not on Buzz or else  people will see them.  I quote this one from folj.com, but I've seen it before in other places as well. 



Five pirates have obtained 100 gold coins and have to divide up the loot. The pirates are all extremely intelligent, treacherous and selfish (especially the captain).

The captain always proposes a distribution of the loot. All pirates vote on the proposal, and if half the crew or more go "Aye", the loot is divided as proposed, as no pirate would be willing to take on the captain without superior force on their side.
If the captain fails to obtain support of at least half his crew (which includes himself), he faces a mutiny, and all pirates will turn against him and make him walk the plank. The pirates start over again with the next senior pirate as captain.

What is the maximum number of coins the captain can keep without risking his life?





Solution: See the "Solutions" page: link is at the top of the sidebar on the right. 

9 comments:

  1. I think 34. He needs 3 votes so he can ignore the other two. Captain, First Mate and whoever is 3rd in command split the 100 coins and the last two are SOL.

    ReplyDelete
  2. Although there is absolutely no incentive for the First Mate to go along. If he votes with the 2 lowest then he can propose a deal for 50 coins with the new First Mate. I say he splits it with the two lowest ranking members because they're far down the chain of command to captain. So 34 split Captain, 4th in command, 5th in command.

    ReplyDelete
  3. I worked it backwards. Let's say the top 3 pirates have walked the plank. Now the deal is easy:
    #4: 100
    #5: 0

    Ok, back up one step and there are three pirates left. #5 knows if he votes down the offer, he will get 0 as above so he has to accept whatever is offered. If he votes with #3, then it doesn't matter what #4 says, so he gets nothing:
    #3: 99
    #4: 0
    #5: 1

    Back up to 4 pirates left. Same deal as above except #2 needs to sweeten the deal for #5:
    #2: 98
    #3: 0
    #4: 0
    #5: 2

    Finally, back to the original situation. I consider the 4 pirate scenario to be a stable situation, and all the pirates know that it will never get past that. Therefore, #1 only has to offer either #3 or #4 1 coin to have them go along with the plan. He has to offer #5 more in order to keep him. Therefore, the final situation is like this:
    #1: 96
    #2: 0
    #3: 0
    #4: 1
    #5: 3

    #2 and #3 get totally screwed, but what are they going to do about it?

    ReplyDelete
  4. Wait, I am rethinking it a little bit. I realize that you don't need to sweeten the deal for #5, you just offer his coin to #4. Here is the new situation:

    2 pirates:
    #4: 100
    #5: 0

    3 pirates:
    #3: 99
    #4: 0
    #5: 1

    4 pirates:
    #2: 99
    #3: 0
    #4: 1
    #5: 0

    5 Pirates:
    #1: 98
    #2: 0
    #3: 1
    #4: 0
    #5: 1

    ReplyDelete
    Replies
    1. Not so. in the situation with 3 pirates, if you offer 5's 1 coin to 4 when 5 says no, 4 gets 1 coin if he says yes but 100 coins if he says no and kills you. So, you can't do that... you do have to incentivize 5.

      In 4 pirate situation, if you offer coin to 4 (instead of 5 if 5 downvotes), and 4 says no, captain dies and 3 has to worry about 4 and 5 disagreeing with him in exchange for a larger pot. Since 3 is more likely to make a deal with 4 and 5 if they all kill 2, 2 has to offer 5 enough to go along with him.

      In 5 pirates, 1 needs 2 people on his side. The laws of attrition tell everyone that if they kill him they each have a better chance of getting a larger sum... thus 5 has to offer 2 people more than they would get with an even split, to ensure he can safely take a larger cut.

      I like your creative solution, it's just not sound.

      Delete
  5. Ok, last solution:

    The captain poisons everybody and keep all 100 coins. I think that is the most likely.

    ReplyDelete
  6. Every Pirate knows he deserves 20 coins in fair play. So to win their trust captain must give them 21 coins at least, else he will be vetoed out. So here's my solution:

    #1 21
    #2 00
    #3 21
    #4 00
    #5 or Captain: 58

    This minimum markup (of 1 coin) theoretically prevents mutiny on the ship!

    Thanks

    ReplyDelete
    Replies
    1. This is also the solution I arrived at.

      Delete
  7. He has to avoid mutiny, so he should offer something that if mutiny happens and everybody gets fair shares at least two pirates lose money.
    In the case of fair share after mutiny everybody gets 25 coins. So the captain needs to give two pirates 26 coins each to avoid mutiny:
    #1 26
    #2 26
    #3 0
    #4 0
    Captain 48

    ReplyDelete