All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Elegantly Greedy Pirates (Posted on 2013-04-20) Difficulty: 3 of 5
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, of course, is at what point will the treasure be split, and what will the precise vote be?

After that, consider solving the problem when a two-thirds or three-fourths majority is required. Try to generalize the result.

No Solution Yet Submitted by Danish Ahmed Khan    
Rating: 3.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Power of the majority (spoiler) | Comment 1 of 5
Working backwards.

Pirate 1 is always safe.  He will never vote for a split.  

If there are two pirates, pirate 2 votes to split and pirate 1 votes against.  They split and each gets 50%.  Pirate 2 will never vote for any split less than 1/2.

If there are three pirates, only pirate 3 votes for a split.  He would lose the vote and die.  

If there are 4 pirates, pirates 3 and 4 vote for a split, and they get 25%.  They will never vote for a split less than 25%.

That means that the next largest group that will vote for a split is 8 pirates.  Pirates 5 - 8 vote for the split, and win.

It is becoming clear that this is a power of two situation.  The treasure will be split by 512 pirates, with pirates 1-256 voting no and pirates 257 - 512 voting yes.  This will occur on day 489, after 488 pirates have been killed.



  Posted by Steve Herman on 2013-04-20 12:59:29
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information