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.)
 Scenarios where nobody needs to die | Comment 3 of 5 |
As we have just seen, if 75% vote is required to force a vote, then much blood is spilled.  Either 744 pirates die, one a day, until the final 256 split the treasure, or a mutiny occurs (the luckless 744 vastly outnumber the lucky 256).

However, consider a slight change in the required majority, reducing it to 74.7% instead of 75%.  A slight change in the required majority, but a dramatic effect.  Now, no blood is spilled.  The top 64 still hold out for a 64-way split (or better), but it no longer takes 192 to outvote them.  Instead 189 can outvote the 64 and force a split, so a split would occur if the number of pirates ever goes down to 253.  (253, by the way, is 64/(1-.747), rounded up to the next highest integer.  Not a coincidence.  That's an example of the general calculation.)

But the split will occur long before we are down to 253.  On day 1, pirates 254 - 1000 will vote for a split, and prevail against the top 253.  Everybody gets 1/1000 of the treasure, and nobody dies!

Of course, there are many other percentages which lead to nobody dying.  For example, if a minority vote of 44.66% is all that is required to force a split, then the bottom 447 will vote on day 1 to split, overcoming the bloc of the top 553 who are holding out for a 553-way split (or better).  Working our way up, with a 44.66% required vote, splits could occur with blocs of 2,4,8,15, 28,51,93, 169, 306, 553 and 1000.

 Posted by Steve Herman on 2013-04-20 23:34:02

 Search: Search body:
Forums (1)