“There has not been a king since the first brethren court, and that is not likely to change!”, Captain Chevalle sighed. Elizabeth Swann wondered, “Why not?”. “Because the pirate king is elected by popular vote…”, as Mr. Gibbs started to explain, Captain Barbossa finished the sentence, “…and each pirate only votes for himself.”~Pirates of the Caribbean.
Yesterday I was having lunch with my friends Jocelyn, Johnson, and Adrian. One thing lead to another, we started talking about pirates. In one of her interviews, Jocelyn came across a question about how a senior pirate would divide some gold coins among 4 other pirates so that they would not vote to kill him. It was immediately apparent that the senior pirate would not give any gold to 2 of the pirates, but how much he should give the other 2 pirates was not obvious to me. It was stuck in my mind. I concluded that there must be some missing pieces of the question. It turns out that this problem is of a significant theoretical interest to many people. Let’s define the problem first.
There are 5 pirates of different ranks in a ship and they have a treasure of 100 gold coins. The current highest ranking pirate will divide the coins, and all 5 pirates will vote for or against it. If half or more of the pirates vote for it, then the coins will be divided that way. Otherwise, the pirate proposing the scheme will be killed, and the process is repeated with the pirates that remain. The most important thing for a pirate is his life. After that he wants to get as much coins as possible. As every pirate is bloodthirsty, if voting for or against will give him the same number of coins, he will vote against so that the pirate who proposed the plan will be killed. All 5 pirates are intelligent, rational, and good at math. How will the highest ranking pirate divide the coins?
Let’s name the pirates by their rank, Ayrton of The Mysterious Island (aka A), Barbossa of Pirates of the Caribbean (aka B), Conan the Barbarian of The Phoenix on the Sword (aka C), Dutch Hodgers of The Adventures of Dutch Hodgers (aka D), and an Irish pirate called the Englishman (aka E).
Suppose A, B, and C are killed. Now, D, the higher ranking pirate, will keep all the gold for himself and give none to E. His vote will be the half of the votes and he will not be killed.
Now, suppose A and B are killed. Now, C, the higher ranking pirate, knows that D will vote against him because by killing him D will get all the gold for himself (previous case). So, C will not give any gold to D. However, he will give 1 gold to E because E is bloodthirsty and if this case and the previous case are the same for E, he will vote to kill C.
Suppose A is killed. Now, B, the higher ranking pirate, knows that C will vote against him because by killing him C will get 99 coins for himself (previous case). So, B will not give any gold to C. Now, he needs one more vote. If he wants E on his side, he has to give him at least 2 coins otherwise E knows that he will get 1 coin in the next round and being bloodthirsty, E will vote to kill B. If he wants D on his side, he only needs to give him 1 coin because D knows that he will not get any coin if B is killed. So, the best decision for B will be to give 1 coin to D and none to C and E.
So, for the actual problem, A knows B will vote against him anyway. Giving 1 coin to C will be enough, since if A is killed C will not get any. Needing 1 more vote he will give 1 coin to E, because to get D on his side he has to offer him at least 2 coins (as D will get 1 coin if A is killed anyway). So, A will give 1 coin to C, 1 coin to E, and keep the remaining 98 for himself.
We can see that a pattern emerges and we always generalize when there is a pattern. Let’s write the pattern down:
1 pirate : (100)
2 pirates: (100, 0)
3 pirates: (99, 0, 1)
4 pirates: (99, 0, 1, 0)
5 pirates: (98, 0, 1, 0, 1)
6 pirates: (98, 0, 1, 0, 1, 0)
7 pirates: (97, 0, 1, 0, 1, 0, 1)
Therefore, for n pirates the pattern will be . Now what happens if becomes a negative number, i.e., let’s consider the cases when the number of pirates are 201, 202, and 203. The captain will be able to satisfy 100 pirates with his 100 gold coins. So, he gets 101 votes (including his). For 201 and 202 pirates he will not be killed, but for 203 pirates he will definitely be killed. Now, an interesting phenomenon happens when the number of pirates are 204. The 203rd pirate will vote for the captain without any gold otherwise he will be killed in the next round. So, the 204th pirate (the captain) will survive by getting 102 votes. The 205th pirate will be killed getting 101 votes (including his, 204 and 203 will not vote for 205 since it does not make any difference for them). In fact, 203 and 204 will not vote for any of their senior pirates, since their survival is guaranteed, they rather kill their seniors. When 206 in charge, 205 will not vote for him since it will not make any difference and 206 will be killed. Similarly, 207 will not get vote from 205 or 206, and will be killed. However, 208 will get vote from all 205, 206, and 207 totaling 104 vote, since 208’s survival will ensure 205, 206, and 207’s survival. 208 survives. Similarly, all captains until 216 will be killed. So, will survive.
To summarize, if n is the number of pirates, m is the number of gold coins, , and then the solution for the general case is following,
Case I () : .
Case II ():
- Sub-case II.I (): Pirates higher than 2m will receive no coins and the rest will follow Case I with .
- Sub-case II.II (): Pirates higher than will be killed and the rest will follow Sub-case II.I.