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

 Elegantly Greedy Pirates (Posted on 2013-04-20)
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.)
 Power of the supermajority (spoiler) | Comment 2 of 5 |
If 2/3 of the vote are required to split, then there will be a split whenever the number of remaining pirates first reaches an exact power of 3.  The bottom 2/3 will vote for a split, and the top 1/3 will vote against.  For the bottom 2/3, this will be their last chance to force a split with the top 1/3 (who are also a power of 3).
In the case of 1000 pirates, this occurs when there are 729 pirates, on day 272.

If 3/4 of the vote are required to split, then there will be a split whenever the number of remaining pirates first reaches an exact power of 4.  The bottom 3/4 will vote for a split, and the top 1/4 will vote against.  For the bottom 3/4, this will be their last chance to force a split with the top 1/4 (who are also a power of 4).
In the case of 1000 pirates, this occurs when there are 256 pirates, on day 745.  (As a practical matter, it is hard to believe that the first 744 pirates will not figure this out and stage a mutiny on day 1, instead of letting themselves get killed off one day at a time.  The out-of-luck 744 outnumber the top 256 by almost 3 to 1.)

If (n-1)/n are required to split, then there will be a split whenever the number of remaining pirates first reaches an exact power of n.  The bottom (n-1)/n will vote for a split, and the top 1/n will vote against.  For the bottom (n-1)/n, this will be their last chance to force a split with the top 1/n (who are also a power of n).

 Posted by Steve Herman on 2013-04-20 22:42:58

 Search: Search body:
Forums (0)
Random Problem
Site Statistics
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox: