In May of 1999, Ian Stewart issued the article “A Puzzle for Pirates” in that month's edition of *Scientific American* (pp.98-99). This mathematical game then went on to become a worldwide hit, especially for puzzlers who like a good challenge. The rules of the pirate game are described below:

*Five rational pirates have found 100 gold coins on an island and need to decide how to distribute them. They are a democratic bunch and they ask the fiercest pirate to propose a plan of distribution. Then, all of the living pirates (including the proposer) vote on whether to accept the distribution plan. If the majority (50% or more) accepts that proposal, then coins are dispersed and the game ends. Otherwise, the proposer is thrown overboard and killed, then the procedure is repeated with the next fiercest pirate until a proposal is accepted or only one pirate is left. If there is a tie vote, then the proposer (say, the fiercest pirate) has the casting vote.*

At first glance, the proposer may offer the most favorable terms to all voters to pass the proposal, but this is not the case. The pirates are not only rational but also greedy and want to maximize their personal gain. Due to the game's rules and how the order of pirate fierceness is known to all in advance, these rational pirates prioritize surviving first, then maximizing gold coins for themselves. They would love to kill off as many pirates as possible to make more coins for themselves through future distribution proposals. This logic may become surprisingly complicated due to the changes in the numbers of pirates and coins.

Suppose ** N** is the number of pirates, and

**is the number of gold coins. We number the pirates in order from meekest to fiercest, the greater the number, the fiercer the pirate. So**

*G**P1*is the least fierce pirate, and

*PN*is the fiercest pirate. Due to there being too many branches from the beginning, we can think of the problem backward from the end, that is, starting from the game results to reverse the entire distribution process.

If there are only two pirates (*N*=2), then obviously the fierce pirate is going to propose *G* coins for himself, and none for the meek pirate (*P1=0, P2=G*). Any proposal will pass no matter what it is for this case, so the fierce pirate would take all the coins while the meek pirate has no choice but to accept it. The fierce pirate doesn’t need to please meek pirate at all!

If there are three pirates (*N*=3), and all of them are aware of an inevitable positive result, then the fiercest pirate *P3* is going to make a proposal pass to guarantee his own survival first, so he needs at least one vote from *P1* or *P2*. Due to *P2* having the possibility of getting *G* coins, so he can’t be bribed with gold coins; *P1* knows he is going to get 0 coins if the game goes onto the next round, and *P3* knows what *P1* is thinking, so P3 can offer the least amount of coins, e.g., just 1 coin to buy the vote of *P1*, and *P1* also would love to support P3 accordingly as he can get a better result: survival plus coins. So, the final proposal by *P3* is *P1=1, P2=0, P3=G-1, *where *G*>1.

From the two trial calculations above, we can conclude the following decision-making patterns or rules for a player of the pirate game. The rules apply to all pirates and it is the rationality of a pirate, that is the pirate game recursive solving algorithm (click here to download the precompiled code).

- For any
*N*,*G*, both*N*and*G*must be greater than zero for game, to avoid the possibility of unlimited bribing, we usually define them as both integer and*2*G < N*, but this is not required. - If the number of pirates
*N*is 2, then proposal is*P1=0, P2=G*. - Otherwise, count the proposer’s vote out and let the rest of the pirates (
*N-1*) to distribute*G*gold coins. For its trial result proposal, count the number of votes supported:- The fiercest pirate whose proposal is impossible to pass in the next round. Because this pirate is going to die in the next round, he is the inevitable supporter of the current proposal to avoid making a proposal and being killed in the next round.
- The pirates who are going to receive 0 coins in the next round. Try to buy this kind of pirate as a supporter with the least coins (e.g., 1 coin) from total G coins. For those pirates who received coins in the trial calculation, take their coins away!

- Check if the current proposal is going to pass the vote and return that flag.
- If the number of votes supported plus 1 vote of the current proposer is equal to or greater than the
*N/2*, then the proposal is passed. So the current proposer takes all the remaining gold coins after buying supporters in 3.b and make all those pirates going to die in the next round alive because they avoid the further distribution process. - If the current proposal cannot be passed, then throw the current proposer overboard, marking
*PN*as a must-die pirate.

- If the number of votes supported plus 1 vote of the current proposer is equal to or greater than the

Please note step #3, we're calling the pirate game-solving algorithm recursively, so it would reach the game-over condition. The following proposal plan table is generated by upper algorithm implementation by SAS for pirate games with* N<=20 *and *G=100*. You can see the best solution is, the fiercest pirate chooses the pirates with the same parity as him in the list ordered by fierce as his supporter. E.g., *P3* would choose *P1* as his supporter for a *N=3* pirate game, and *P5* would choose *P3, P1* as his supporter for a *N=5* game.

Will this pattern continue for any *N* pirate games with constant *G* gold coins? The answer is no because we have limited gold coins (*G*) to buy supporters. Anyway, it is true for *N<= 2*G* game, e.g., The P200 can take 1 coin and buy 99 supporters with another 99 coins, the detailed proposal plan for *N=200* pirate game is show as below:

Interesting things happen while the number of pirates *N* exceed the *2*G*. e.g., *P201* and *P202* pirates still can survive if he is taking no gold coins for himself and offering 1 gold coin each to 100 pirates with the same parity in the list ordered by fierceness. The detailed proposal for *N=201, N=202* cases is show as below:

Unfortunately, *P203* has no coins to buy supporters anymore in the pirate game (*G=100, N=203*), so *P201* and *P202* in this round would love to throw *P203* overboard to earn more coins through future distribution proposals. In other words, *P203* must die for this case (We use -1 to indicate death in detailed proposal).

*P204* is a lucky guy who can survive. Since *P203* must die in the next round, *P203* is going to support any proposal made by *P204* in the current round. *P204* will apply the same strategy as *P202* used in the *N=202* pirate game above, so *P204* takes no coins, and he gets support from *P203* in this current round. So, *P201*, *P202, P203* and *P204* all survive with no coins. The detailed proposal is shown as below:

Accordingly, *P205, P206* and *P207* are all unlucky and doomed to die in their round, just like *P203* in pirate game (*G=100, N=203*). The key reason is that they cannot get sufficient votes to make their proposals pass. The four rational pirates (*P201 to P204*) know they can survive and would love to throw these three pirates (*P205 to P207*) overboard to earn more coins through future distribution proposals. The detailed proposal for the game (*G=100, N=207*) is shown below:

Just as lucky as *P204* in pirate game (*G=100, N=204*), *P208* is also lucky enough to make a proposal pass because he can get sufficient support from *P205*, *P206* and *P207* who are doomed to die. *P205*, *P206* and *P207* must support *P208* to avoid making a proposal and getting killed in the next round. The detailed proposal for the game (*G=100, N=208*) is shown below:

In general, suppose the number of the pirate I-*th* (*I<= N*) is *PI* in a pirate game (*N, G*), we have the following conclusion based on the recursive solving algorithm result:

- When
, all pirates will survive, and they also have 50% possibility to get 1 or more gold coins.**I<=2*G** - When
and*I >2*G*, the pirate**I=N**(*PI**=PN*, proposer) is going to survive only when**(N - 2*G**is the power of 2, otherwise they will die. - When
and**I>2*G**, all pirates with number**I<N**will survive but will receive no coins, all pirates whose number**I <= (2*G + M)**will die, where M is the highest power of 2 that does not exceed**I>(2*G+M)****N - 2*G.**Please note that the survival for the*PI*is a possibility related to*N*value, those*PI*will survive again If*N*exceed.*2*G + 2*M*

e.g., *G=100, N=(205, 206, 207)*, *N-2*G=(5, 6, 7)*, the *M=4 (2^2<=4)*, so *2*G+M=204*, so *P201, P202, P203* and *P204* will survive in pirate games *N=(205, 206, 207)*. *P205* must die in pirate game *N=(205, 206, 207)*, and *P206* must die in pirate game *N=(206, 207)*, and *P207* must die in pirate game* N=207*. But *P205, P206, P207* will survive again if *N* is equal to or greater than 208.

In fact, there is no unique solution to distribute gold coins if a pirate already guarantees his survival. This means that the fiercest pirate has some freedom of selection when *I>=2G+2*, but the simplest solution is to select those pirates with the same parity by order of fierceness.

From the proposer’s perspective (*I=N*), if he attends a pirate game with different *N*, then his personal interest is different. For a game with a number of pirates that is less than or equal to *2*G*, the proposer will always survive with coins. For games with greater than *2*G* pirates, most proposers can’t survive except whose number minus *2*G* happens to be an integer power of 2. We can visualize the solution for pirate game(*N=500, G=100*) with SAS as seen below.

Accordingly, we also can calculate the possibility of survival of a pirate game with *N* pirates (*N<=500*) and constant *G=100*. The survival curve below indicates how likely a pirate (proposer) is to survive if he participates in a game with *N* pirates. As expected, the curve is a non-linear line.

For the least fierce pirate, he has no chance to distribute gold coins, but he has most chances to vote on proposals. In other words, he can survive longer than other pirates. For the fiercest pirate, the survival rate appears as a cliff-like fall at some points for the pirate whose number *PI* is greater than *2*G*. The survival curve below indicates how likely a pirate *PI* is to survive if he participates in a game with *N* pirates (*N<=500*).

e.g., For a game with 500 pirates, the first 44 pirates are doomed to be thrown overboard (*P457 to P500*), so the blue survival line falls to 0 at *P456 (2*G+2^Y=2*100+2^8=456*), accordingly the death rate(red) is suddenly increased to 100%.

**Summary**

We have figured out how to solve the pirate game with a recursive solving algorithm in SAS, and how to analyze and visualize the law behind the complex logic of the pirate game. Now the next time you join a pirate game, you will know your destiny ahead of time and reap the benefits while avoiding getting thrown overboard.

Solve "A Puzzle for Pirates" with SAS was published on SAS Users.