I regularly enjoy the weekly puzzles from FiveThirtyEight’s riddler, Oliver Roeder. Here’s a good one from this week:
The Puzzle Of The Pirate Booty:
Ten Perfectly Rational Pirate Logicians (PRPLs) find 10 (indivisible) gold pieces and wish to distribute the booty among themselves.
The pirates each have a unique rank, from the captain on down. The captain puts forth the first plan to divide up the gold, whereupon the pirates (including the captain) vote. If at least half the pirates vote for the plan, it is enacted, and the gold is distributed accordingly. If the plan gets fewer than half the votes, however, the captain is killed, the second-in-command is promoted, and the process starts over. (They’re mutinous, these PRPLs.)
Pirates always vote by the following rules, with the earliest rule taking precedence in a conflict:
- Self-preservation: A pirate values his life above all else.
- Greed: A pirate seeks as much gold as possible.
- Bloodthirst: Failing a threat to his life or bounty, a pirate always votes to kill.
Under this system, how do the PRPLs divide up their gold?
Extra credit: Solve the generalized problem where there are P pirates and G gold pieces.
___________
I think I got it—click below to expand and read my solution:
[expand title=”SOLUTION“]Think of it from the view of the lowest-ranked pirate and work up from there.
The lowest ranked pirate (we’ll call him P10 and work our way up to the captain, who’s P1) would love to have every other pirate die so he can take all 10 gold pieces for himself. He also has no threat to his life, because by the time he’s promoted to captain, it means everyone else is dead.
P9 would also love to have all pirates above him killed, because if it gets down to just himself and P10, he can allot all 10 gold pieces to himself and none to P10. The vote will end up 1-1 (P9 will vote in favor and P10 will vote against), and since half of the members voted for the plan, it’ll be enacted and P9 will not be killed. So he, too, has no threat to his life.
P8 knows all this. He knows that if it gets down to the final two pirates, it’ll end up as:
P9: 10 pieces
P10: 0 pieces
And he knows that P10 and P9 know this, so if it ends up getting to the point where there only three pirates left and he’s captain, he’ll have that in mind. He could allot the gold pieces like this:
P8: 10
P9: 0
P10: 0
That’s much worse for P9 than the outcome if P8 is killed, so P9 will vote against the plan. But P10 is in the same position as he’ll be if P8 is killed: zero gold pieces. This is when rule #3 kicks in: the pirates are bloodthirsty. If it won’t put either a pirate’s life or bounty at stake, “a pirate always votes to kill.” In this case, P10 will vote to kill because it won’t affect his life or bounty either way. So if P8 wants to win P10’s vote, he needs to give him one gold piece. Then rule #2 kicks in—greed. P10 will understand that he should vote in favor of the plan, because if he doesn’t, he’ll get nothing after P8 is killed, so he’ll vote for the plan and it’ll be enacted. P8’s life will be spared and he’ll make off with an awesome nine gold pieces. So P8 will allot the pieces like this:
P8: 9
P9: 0
P10: 1
In the case where there are four pirates left and P7 is captain, P7 knows all of the above and he knows that the other three pirates all know all of the above—and he only needs one of the three other pirates to vote in favor of his plan for it to be enacted in order to spare his life. So he’ll allot them like this:
P7: 9
P8: 0
P9: 1
P10: 0
He knows P8 and P10 will vote against it, because if he dies, they’ll be in the above situation where P8 gets nine pieces and P10 gets one, and his plan has them both getting zero. But he’ll get P9’s vote, because P9 knows that if he votes against it, P8 will enact his plan and P9 will get nothing. One piece is better than zero pieces, so P7’s plan will be enacted.
You can continue this logic upwards through the ranks. In each case, if the highest-ranked pirate allots one piece to all pirates who will be getting zero pieces should he be killed, his plan will be enacted, so it’ll go like this:
If it gets down to the final five pirates, the plan will be:
P6: 8
P7: 0
P8: 1
P9: 0
P10: 1
If it gets down to the final six pirates, the plan will be:
P5: 8
P6: 0
P7: 1
P8: 0
P9: 1
P10: 0
If it gets down to the final seven pirates, the plan will be:
P4: 7
P5: 0
P6: 1
P7: 0
P8: 1
P9: 0
P10: 1
If it gets down to the final eight pirates, the plan will be:
P3: 7
P4: 0
P5: 1
P6: 0
P7: 1
P8: 0
P9: 1
P10: 0
If it gets down to the final nine pirates, the plan will be:
P2: 6
P3: 0
P4: 1
P5: 0
P6: 1
P7: 0
P8: 1
P9: 0
P10: 1
But no one will die at all, because the original captain will allot them like this:
P1: 6
P2: 0
P3: 1
P4: 0
P5: 1
P6: 0
P7: 1
P8: 0
P9: 1
P10: 0
He’ll get votes from P3, P5, P7, P9, and himself to create a 5-5 split—and his plan will be enacted.
So the solution is: 6, 0, 1, 0, 1, 0, 1, 0, 1, 0
___________
Note about collusion: Collusion at first seems like it could provide an interesting wrinkle. For example, P9 and P10 could collude and decide that instead of P9 voting to enact P1’s plan (which would give him one gold piece and P10 zero gold pieces), they could both vote no, and then continue to vote no again and again, preventing a majority vote until they’re the only two left. This would be great for P9, because he’d get ten gold pieces instead of one, and also good for P10 because, despite ending up with zero pieces in both cases, he’d have killed more people in the latter case, and as per rule #3, pirates are bloodthirsty, so he’d rather do that than P1’s plan. But this fails, because P10 would rather have one gold piece than kill those other pirates (since rule #2, greed, trumps rule #3, bloodthirst). So if they went with this collusion, once they got to the final three, P10 would break the agreement and vote yes to P8’s plan to snatch his last chance at one gold piece. Knowing this would happen, P9 would vote yes to P7’s plan. This would continue upwards until the top, so P9 would ultimately vote yes to P1’s plan, as described in the original solution.
P9 could try to thwart this problem by promising P10 two gold pieces if he agrees to vote no each time until they’re the only two left—but that fails too, since once there are only the two of them left, P9 has no incentive to honor the plan and will take all ten for himself. This is why all collusion inevitably fails.
___________
Extra Credit
The extra credit challenge is: Solve the generalized problem where there are P pirates and G gold pieces)
The second in command always gets 0, the third in command always gets 1, and that alternates—0, 1, 0, 1…—all the way down. Then the first in command gets whatever’s leftover.
This works fine as long as there are enough gold pieces for the first in command to dole out one piece to just under half of the other pirates. If not, he’s in trouble, and so will be every pirate below him until enough pirates are killed off that the first in command has enough gold pieces to use to buy the votes he needs. Or, until G ≥ P/2 – 1 (if P is even) or G ≥ (P-1)/2 (if P is odd).
Extra Credit add-on:
Shit. As commenter gpsimms pointed out, the extra credit is more complicated than I gave it credit for. In the case that there’s enough gold to cover the requisite votes (G ≥ P/2 – 1 (if P is even) or G ≥ (P-1)/2 (if P is odd), as described above), what I said in the first extra credit section is correct. But when there’s not enough gold, things get more complicated.
Let’s say there’s only one gold piece. Here’s what happens (I bolded those who will vote “yes”):
If there’s only one pirate (P = 1):
P10: 1 (He takes the gold piece.)
Outcome: No one dies.
If P = 2:
P9: 1
P10: 0
Outcome: No one dies.
If P = 3:
P8: 0
P9: 0
P10: 1
Outcome: No one dies.
If P = 4:
P7: 0
P8: 0
P9: 1
P10: 0
Outcome: No one dies.
If P = 5:
P6: 0
P7: 0
P8: 0
P9: 0
P10: 1
Outcome: P6 dies, plan fails, moves onto the next round.
If P = 6:
P5: 0
P6: 0 (votes yes because he’ll die in the next round if he doesn’t)
P7: 0
P8: 0
P9: 0
P10: 1
Outcome: No one dies.
So the interesting thing is that because of what would happen here when P = 6, P5 and P6 are safe. They have no chance of dying—something they’ll be aware of when voting in P ≥ 6 situations.
If P = 7:
P4: 0
P5: 0 – votes no because they’ll survive in the P = 6 round and he’d rather kill P4 first.
P6: 0 – votes no because they’ll survive in the P = 6 round and he’d rather kill P4 first.
P7: 0
P8: 0
P9: 1
P10: 0
Outcome: P4 dies.
If P = 8:
P3: 0
P4: 0 – knows he’ll die in the next round if P3 is killed
P5: 0 – knows he’ll be saved when P = 6
P6: 0 – knows he’ll be saved when P = 6
P7: 0
P8: 0
P9: 1
P10: 0
Outcome: P3 dies.
If P = 9:
P2: 0
P3: 0 – knows he’ll die when he’s captain if P2 is killed
P4: 0 – knows he’ll die when he’s captain if P2 and P3 are killed
P5: 0 – knows he’ll be saved when P = 6
P6: 0 – knows he’ll be saved when P = 6
P7: 0
P8: 0
P9: 1
P10: 0
Outcome: P2 dies.
If P = 10:
P1: 0
P2: 0 – knows he’ll die when he’s captain if P1 is killed
P3: 0 – knows he’ll die when he’s captain if P1 and P2 is killed
P4: 0 – knows he’ll die when he’s captain if P1, P2 and P3 are killed
P5: 0 – knows he’ll be saved when P = 6
P6: 0 – knows he’ll be saved when P = 6
P7: 0
P8: 0
P9: 1 – votes yes because if he doesn’t, it’ll whittle down to P = 6 and he’ll get no gold pieces when that plan is enacted
P10: 0
Outcome: No one dies.
Once we get to P > 10, all of the above 10 pirates know they’re safe. P1 – P5 will all be saved when P = 10. So they’ll stop voting yes unless there are gold pieces allotted to them. So P11 – P17 are all screwed until we get to the point where P = 18. Then, P11 – P18 will all vote yes to save themselves, along with one lower pirate who P18 gives the gold piece to.
So when there’s one gold piece, no one dies when P = 1, 2, 3, 4, 6, 10, 18, 34, 66…
The pattern, starting at P = 4, is the last safe number times two, minus two (2n – 2).
That’s for G = 1. Increasing the number of gold pieces changes the “safe pattern.” You could create a generalized formula for P and G, but that sounds very icky, so I’ll pass.
[/expand]_______
If you like Wait But Why, sign up for our unannoying-I-promise email list and we’ll send you new posts when they come out.
To support Wait But Why, visit our Patreon page.
___________
More puzzles on Wait But Why:
The Infinite Checkerboard Quandary
And one very big puzzle:
