Another Pirate Riddle
Posted by Rob Herman at September 19th, 2007
A variation of the Pirate Riddle from intrepid reader John Rhoadhouse, on honor of Talk Like A Pirate Day. Arrrr.
First, the pirates have a new constitution. The first pirate makes a proposal. regarding the distribution of treasure. If half or more of the pirates vote for a proposal, it succeeds. Otherwise the proposer is executed and the next pirate down the list makes a proposal. Pirates vote based on the following priorities:
- Life–a pirate will vote for whatever will save his or her skin.
- Treasure–the more, the better
- Bloodlust–life and treasure being equal, pirates will vote in the way that will see as many of their fellows killed as possible.
So, the riddle: Our salty pirate crew of 10 has fallen upon hard times and has a meager treasure of only one gold coin, which cannot be cut or split up. How many pirates will die? In general, for n pirates, how many will die?
Hint: Solve the case where there is no treasure at all.
Ahh… our favorite greedy, bloodthirsty, piratical logicians. I do not have time to post my full reasoning.
All ten pirates live, with 2,3,5, or 6. I have not tried to calculate for N pirates.
With no coins: x pirates live where x is is the highest power of two less than than total number of n pirates.
You’re right about no coins except for a fencepost error (it’s less-than-or-equal).
You’re on the right track for one coin except that with 4, all live (the one that proposes and the one that gets the coin) whereas with 5, one dies. If the pattern isn’t clear with 1, 2, 3, 4, 6, 10, it’ll be very clear once you see what the next number of pirates where all live is.
ARRGG. I tried to fix my post and I ended up double posting.
It should have read “with 2,3,5, or 6 GETTING THE COIN”
I also tried adding the “or equals to” language.
Lets see 18 and then 34. The series Looks like powers of two plus two. That is just pattern recongnition though. I do not understand why, and it seems counter intuitive. Also it does not explain the safety on the numbers 1 and 2 pirates.
Basically, there need to be enough pirates directly after the current pirate who will die for certain and thus will vote yes to any proposal to get to N/2 - 2. Then the active pirate votes for his own proposal, and he pays off another pirate who otherwise gets nothing to get to N/2 “yes” votes. Thus:
Given a particular pirate who is able to survive, number K > 3, the next pirate will die with K-1 votes against, as will all succeeding pirates until pirate N where N-K 1 = K-1 or N = 2K - 2. Thus the increment between each pirate who can live doubles, starting with 4-3=1. Best I can do offhand for explanation of the why. As to the degeneration (first two pirates), all I can say is that what we really want is N >= 2K-2 and N>K, and for K