Pirate Riddle
Posted by Rob Herman at July 23rd, 2006
Another riddle for today. I may have already shared this with some of my readers. This is one of my favorites and was supposed to go up earlier today, but something with my computer or WordPress ended up flaking out…
Five pirates have to divide a treasure of 1000 coins. The pirates have a ranking from highest to lowest. This is the system the pirates use to see who will get how much treasure:
- The lowest ranked pirate proposes a way to divide up the treasure.
- The pirates vote on the distribution scheme.
- If more than half of the pirates vote yes, the treasure is divided as planned.
- Otherwise, the pirate who proposed the scheme is forced to walk the plank, and the next lowest ranked pirate proposes a scheme.
The pirates have the following traits:
- They are perfectly logical.
- They are greedy and will vote to maximize their own treasure regardless of all other considerations.
- They are bloodthirsty and, all other things being equal, will vote against a proposal.
What should the lowest ranked pirate suggest?
Hint 1: Usually I would say something like “Now generalize the solution to any number of pirates.” But for this riddle, the solution is trivially generalizable once you have it.
Hint 2: The solution makes sense, but the distribution that it gives is pretty startling.
Other Notes: Someone asked me how the pirates came up with such a system. I wasn’t there, of course, but here are some speculations:
- There was grog involved?
- Or maybe an ancient curse?
- This is the way all pirates distribute treasure; it works better for non-perfectly-logical pirates?
I am assuming none of the pirates wants to walk the plank and will therefore place not walking the plank as the highest value. That being the case I think that the lowest pirate should offer 1 piece of gold to the Third pirate and two pieces to either the First or Second Pirate and keep the other 997 for himself.
If my assumptio about not wanting to walk the plank is wrong, I will have to rethink this.
Yaarrrr! Ye be close, but if ye be the scurvy dog that suggest this scheme - ye walk the plank!
Pirates four and five vote Aye! because they value their booty, but the rest say Nay!
What the scurvy dog should do is keep 500 pieces o’eight to himself, and then split the rest between the Captain and First Mate. Any less, and the Cap’n and First Mate will vote for blood. Any more would be dangerously generous, the scallywag would be givin up too much swag!
The generalization of this buccaneer riddle is that the low pirate on the totem pole gets to keep half, and then just enough more to get a majority get to split the rest.
Rob, let me know if I’m wrong, but beware! I may send you down to Davy Jones’ Locker either way!
Fuleng … please explain your logic, I believe that Beaker is correct.
Why would Pirate four vote Aye if he recieves no treasure from the distribution? Why will the Cap’n and first mate vote down any plan where the low man gets more than half? How much gold can the third pirate expect to get if he votes Nay as you suggest.
The only thing to say is that the two pieces have to go to the second-ranked pirate, as the captain will always vote down any proposal at all, since he gets all the booty once he votes down the first mate, as will each odd-ranked pirate. Even-ranked pirates receive gold incremented +1 per even-rank, beginning with 1 for the 2nd-lowest (in this case, 1 for P4, 2 for P2).
WARNING: I put the answer in this puzzle, so don’t read it if you’re still thinking about it.
Let’s work backwards:
If it gets down to only 1 pirate, he gets all the gold and maximum bloodthirstiness.
Therefore, if it is ever down to 2 pirates, #2 has no way to save himself. Even if he offers all 1000 gold to #1, #1 will still vote against it because he is bloodthirsty.
Think about what that means if it is down to 3 pirates. #2 knows that he is dead if #3’s proposal gets turned down, so he will vote for anything. #3 would then take all 1000 for himself, and both he and #2 would vote in favor of it.
So when Pirate #4 makes his proposal, the others are aware that if he turns them down, #1 and #2 get nothing and #3 gets all the gold. So #4 will propose to give 1 gold each to #1 and #2, and take 998 for himself. All pirate but #3 would be best off voting for it.
That brings us back to #5. Since all the pirates are perfectly logical and predictable, they know that #4’s proposal will be 1-1-0-998 if #5 walks the plank. So #5 should propose 2-0-1-0-997 (or 0-2-1-0-997) to get get himself and two others to feel that they are best off with this offer.
I’m surprised to see that Beaker is right. I just figured this out as I typed it up, and I didn’t expect to get anything so un-intuitive.
I went through the same reasoning, I just decided not to post the whole thing. My wife and I were having problems extending this to more pirates though. We did not know how a pirate would value a 50% chance to get 2 gold pieces.
And HEY!!!! What do you mean you are surpised to see that Beaker is right?!?!
Oops. Less-than sign bit me.
It looks like you can make one of several assumptions:
–Pirates will value an X% chance at Y coins at X*Y.
–Pirates will never value an X% chance where X LT 100 for anything at all.
–Pirates will value any chance at Y coins at Y.
–All other things being equal, pirates will preferentially give money to the lowest (or highest, WLOG) pirate.
The solutions differ slightly but I think all can be solved as long as you and both all the pirates are aware of it. I prefer the last one.
Yeah, spoiler here, too. At some point this devolved into solution discussion, so here goes everything. If you’re thinking about any variation whatsoever, disregard me.
Ultimately, I suppose it’s a question of interpretation of hope. I took the specification of greed to imply a vigorous hope, solving more or less option 3 as Rob puts it.
PART 1: solution for “Pirates value any chance at Y coins at Y”
For 2n+1 pirates, distribute k gold pieces to pirate # 2(n-k+1), for integral 0 LT k LTE n and keep the rest.
(LT being less-than, LTE being less-than-or-equal)
If the fact of an imminent proposal which could be passed is weighted, the solution looks close to what Beaker posts, though I re-address it here, with a detail of disagreement. I consider the stated bloodthirst to imply that a pirate in a position of choosing to die and kill someone or to live and earn no booty would choose the former option. This forces pirate#3 to pay off #2 with a single coin, and propogates that detail through the later calculations.
*-Now looking at the next part as I have written it, compared to its solution under a will-to-live assumption, it is actually simpler to state in the latter instance. I will post both now.
PART 2: solution for “Pirates will never value a chance LT 100%, and will preferentially give money to the lowest-ranked pirate, all other things being equal”
Looking at the three remaining assumptions, we now have choices. Taking #2 and #4 (biasing toward paying off lowest-ranked pirates, as these are the closer associates of the chooser), extension to more pirates comes out as follows. It is important to note, of course, that all pirates are aware of the friend-preference, in addition to being certain of the proposal which will follow the current one.
The pattern emerges clearly beginning with pirate #7. The first six proposals are as follows: (1000); (1000,0); (0,1,999); (1,2,0,997); (2,0,1,0,997); (0,1,2,1,0,996). For pirate #2n+7 we have (1,0,0,{1,0}xn,2,1,0,996-n). For pirate #2n+8 we have (0,1,1,0,{0,1}xn,2,1,0,995-n).
On the assumption of preference to life over death, we begin with the first four proposals only: (1000); (1000,0); (0,0,1000); (1,1,0,998). After this, for pirate #2n+5: ({0,1}xn,0,2,1,0,997-n) and for pirate #2n+6: ({1,0}xn,1,0,2,1,0,996-n).
Inverting assumption #4 kicks the 2 up the line, but leaves the solution fundamentally intact.
PART 3: solution for “Pirates will never value a chance LT 100%” with no predictable choice to break ties.
Basically, the process is going to begin similarly to part 2, except that where there is a payment of 2 with a choice of who to pay it to (beginning with plan #7 or #5, depending on will-to-live), either potential recipient will be accept a payment of 1 prior to and in lieu of a chance at a payment of 2. This winds up letting the active pirate sometimes keep more of his booty (if he is an even-indexed pirate).
For each variation, the proposals first listed are the same; only the extension formula changes. In all cases, only one of the payments of 2 is actually made, but all possibilities are listed simultaneously.
Assuming full bloodthirst, for pirate #7: (1,2,0,2,1,0,996); for #2n+8: (0,1,1,1,{0,1}xn,0,1,0,996-n); for #2n+9: (1,2,2,2,{1,2}xn,1,2,1,0,995-n)
Assuming will to live, for #2n+5: (2,2,{1,2}xn,1,0,997-n); for #2n+6: (1,1,{0,1}xn,0,1,0,997-n)
PART 4: solution for “Pirates value X chance at Y coins at X*Y”
This one appears at first glance to be perhaps the most tricky, especially to extend for arbitrary pirates. For certain, the active pirate will be taking home a somewhat reduced pile of coins as compared to the other calculation styles.
As it turns out, apart from the increased cost, this system is still generated relatively simply. We begin with the will-to-live variation. Previously printed proposals are unchanged again through pirate #4. For #2n+5, choose exactly one-half of pirates #1 through 2n+2 to give 2 coins to, ending with 1,0,(997-2n) for 2n+3,4,5. For #2n+6, choose n+2 among the first 2n+3 to give 2 coins to, again ending with 1,0,(995-2n). As the odds of getting 2 coins in any given next-scenario is either (n+1)/(2n+2) = 1/2 or (n+2)/(2n+3) LT 1, a pirate will always accept a certainty of 2 coins over gambling with the next pirate. In the bloodthirst over life variation, the later pirates (#9 and on) wind up in the same pattern, once the extra zeroes clear through. Pirates #6-8 keep an extra coin, while as previously seen, pirates #3-4 give up one more.
PART 5: solution for “Pirates value any chance at Y coins at Y”, alternate interpretation.
If we interpret this statement without the implication of deeper hope (knowing and accounting for the fact that the next solution will be taken, but counting a certainty of Y coins as no more valuable than a chance at Y coins) , the solution again, of course, changes. Surprisingly, after pirate #6, no one is required to give away more than 2 coins to any other pirate, assuming will-to-live. I don’t have time here to finish the pattern assuming bloodthirst over life, but I’m increasingly disillusioned with that theory, except for general entertainment value, as the patterns are prettier allowing for the first mate to preserve himself for no profit. Anyway, the will-to-live pattern goes as follows:
(1000); (1000,0); (0,0,1000); (1,1,0,998); (2,2,1,0,997); (3,3,2,1,0,994); (0,0,3,2,1,0,994); (1,1,0,0,2,1,0,995); (2,2,1,1,0,2,1,0,995)
As above, the highest value-paid is not paid to all designated pirates, but only enough to secure the appropriate number of votes. The value retained reflects this correctly (in theory).
For pirate #6n+10: (0,0,2,2,1,0,{2,1,0}x2n,2,1,0,992-4n)
#6n+11: (1,1,0,0,2,1,0,{2,1,0}x2n,2,1,0,994-4n)
#6n+12: (2,2,1,1,0,{2,1,0}x2n,2,1,0,2,1,0,992-4n)
#6n+13: (0,0,2,2,1,0,{2,1,0}x2n,2,1,0,2,1,0,991-4n)
#6n+14: (1,1,0,0,2,1,0,{2,1,0}x2n,2,1,0,2,1,0,991-4n)
#6n+15: (2,2,1,1,0,{2,1,0}x2n,2,1,0,2,1,0,2,1,0,991-4n)
The 2,1,0 pattern rolls over in threes, and the difference in even-odd parity requires differing numbers of the 2’s to be used, thus the need for six instances. As two nonzero values are added per three total pirates added, the total votes acquirable will never drop to 50%. The loss of 4 coins per 6 pirates is seen from the need to use both the added 1s plus one of the two added possible-2s to add 3 votes per 6 pirates.
Hooray for something to do at work. Time to go home. Enjoy.
does the pirates own vote count as a vote or does it need to be 75% of the other four pirates votes