In this article, I will investigate and explain the Logical Pattern behind (in my opinion) one of the best questions in Computer Science: The Piracy Problem.
For all of you who hoped to find an article about downloading movies or software, I have to disappoint you. This is not about that kind of piracy. It's about one of the best algorithmic riddles that I have found so far. It's quite a read, but I hope you think it's worth it!
To start off, I'm going to send you here. This entire article is based upon that riddle.
Finished? Cool, isn't it? Logic and pattern recognition combined with a funny setting. There's a small extension to it on the same site here.
I thought about this riddle for a long time and decided to discover the logical pattern behind this problem. In the 6 pirates, 1 coin case, pirate number 5 dies if he would have to make the proposal, yet pirate number 6 lives, because he can count on 5's vote even if 5 gets no coins (because he would otherwise die). I was wondering, what other pirates would survive if there was only a single coin? Pirate 7, 8 and 9 would die again, since they can never convince resp. 4, 4 and 5 pirates to vote for them. Pirate 10 however, gets to live! Because 7, 8 and 9 would otherwise die, they vote for 10 even if they get nothing! Combined with 10's own vote and the vote of the pirate who gets the coin, 10 is able to secure 5 votes and gets to live another day.
Note that in this case, pirate 5 would not vote for pirate 10, because he knows he will get nothing anyway and if 10 walks the plank, so will 9, 8 and 7. 6 would then come to power and 5 would then vote for 6. He still gets nothing, but at least 4 other pirates have died. Him being a pirate, only his own life and getting gold pleases him more than seeing others die :-)
So, let's re-iterate the priorities that pirates use to vote, in order of importance:
- Priority 1: Stay alive
- Priority 2: Get as many gold coins as possible
- Priority 3: Get as many other pirates killed as possible (given priority 1 and 2 are equally satisfied)
- Priority 4: If a pirate is a senior and it doesn't matter to whom he gives a coin, he will give it to the LOWEST ranked pirate. So, if pirate number 6 can choose to give a coin to either 1 or 4, he will choose 1.
I then started to make spreadsheets of the number of coins that each pirate would get, when there are c coins available. Below is the spreadsheet of the 1 coin case. The rows represent the situation where there are a certain number of pirates and the columns represent what each pirate would get in those situations. a value of -1 (and a red color) means that the pirate in question dies in that given situation. The green cells represent the pirates who would vote in favour of the proposal. Please click to enlarge.
The 1 coin case
And here are the spreadsheets for 2 and 3 coins:
The 2 coins case
The 3 coins case
A clear pattern emerges! I have defined so-called "life lines": lines on which the most senior pirate is able to survive by counting on the votes of the pirates who would otherwise die. I've marked those rows with a light green color. The patterns that emerge are as follows:
- A life line occurs when the number of pirates is equal to a number in this set: For c number of coins and x > 1: 2x + 2c. So, for 1 coin, the life lines are 4, 6, 10, 18, 34...
- Before the first life line: If the most senior is even, all even pirates get a coin, all odd pirates get nothing. The most senior keeps what's left. When the most senior is odd, it's the odd pirates who get a share of the bounty. Note that the "first" life line fits this pattern as well. It's kind of a transitional line.
- After each life line, the most senior pirate dies and the others get the same as they got on the previous life line, until we get to the next life line.
- On each life line, the most senior pirate gives the coins to the most junior pirates who would otherwise get nothing. Note that these alternate on each subsequent life line, because otherwise, those juniors have no incentive to vote (because they would get the coins anyway).
The 0 coins case
Then, I created an algorithm (in Java). For a certain number of pirates and a certain number of coins, what does a certain pirate get? (Scrolling to the right is possible)
And that's that: The Logical Pattern behind Piracy.
Thanks to: