** **

**Question:** Five pirates discover a chest containing 100 gold coins. They decide to sit down and devise a distribution strategy. The pirates are ranked based on their experience (Pirate 1 to Pirate 5, where Pirate 5 is the most experienced). The most experienced pirate gets to propose a plan and then all the pirates vote on it. If at least half of the pirates agree on the plan, the gold is split according to the proposal. If not, the most experienced pirate is thrown off the ship and this process continues with the remaining pirates until a proposal is accepted. The first priority of the pirates is to stay alive and second to maximize the gold they get. Pirate 5 devises a plan which he knows will be accepted for sure and will maximize his gold. What is his plan?

**Answer:** To understand the answer, we need to reduce this problem to only 2 pirates. So what happens if there are only 2 pirates. Pirate 2 can easily propose that he gets all the 100 gold coins. Since he constitutes 50% of the pirates, the proposal has to be accepted leaving Pirate 1 with nothing.

Now let’s look at 3 pirates situation, Pirate 3 knows that if his proposal does not get accepted, then pirate 2 will get all the gold and pirate 1 will get nothing. So he decides to bribe pirate 1 with one gold coin. Pirate 1 knows that one gold coin is better than nothing so he has to back pirate 3. Pirate 3 proposes {pirate 1, pirate 2, pirate 3} {1, 0, 99}. Since pirate 1 and 3 will vote for it, it will be accepted.

If there are 4 pirates, pirate 4 needs to get one more pirate to vote for his proposal. Pirate 4 realizes that if he dies, pirate 2 will get nothing (according to the proposal with 3 pirates) so he can easily bribe pirate 2 with one gold coin to get his vote. So the distribution will be {0, 1, 0, 99}.

Smart right? Now can you figure out the distribution with 5 pirates? Let’s see. Pirate 5 needs 2 votes and he knows that if he dies, pirate 1 and 3 will get nothing. He can easily bribe pirates 1 and 3 with one gold coin each to get their vote. In the end, he proposes {1, 0, 1, 0, 98}. This proposal will get accepted and provide the maximum amount of gold to pirate 5.

**Bonus:** Think about what would happen if there are 15 pirates or 25 pirates. Post the answer in the comments section.

**If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:**

All even position pirates gets zero gold coins

15 Pirates

————-

7 gold coins for the 7 pirates that will get nothing and 93 for the 15th

1,0,1,0,1,0,1,0,1,0,1,0,1,0,93

25 Pirates

————-

12 gold coins for the 12 pirates that will get nothng and 88 for the 25th

1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,88

Brad’s answer is correct and he’s a genius. Brilliant!

If pirates are completely logical, those pirates who get nothing will go apeshit, blast first and obey democracy later.

I am wondering for the case of 5 pirates… Doesnt it makes more sense for 3 junior pirates to get rid of the 2 most senior pirates? afterall it is just risking 1 gold coin… 1 gold coin is as good as nothing.

I think the proposed solution is correct (98 for Pirate 5), but the reasoning scenario is wrong. You have to start with Pirate 5 and reason from his vantage point. He is really in control (remember also the ordering of the pirates). From his point of view, if he dies, then he knows that Pirates 1 and 2 know that they will get nothing, because Pirate 4 will split it with Pirate 3 (50 each), and they also know Pirate 3 knows he can’t do any better if Pirate 4 dies (i.e., should Pirate 3 refuse and let Pirate 4 die), and moreover they know Pirate 3 does not want to die, because if it gets that far Pirates 1 and 2 will never agree to let Pirate 3 have any. Thus if Pirate 5 proposes 1 gold piece each for Pirates 1 and 2 and none for Pirates 3 and 4, and 98 for himself, then they will agree.

The answer given to the question is correct. No need to say about the bribe which made confusion. (Instead of that, say that pirate 5 has to explain the maths to other pirates 🙂 )

In following explanation Im using P for Pirate.

P1 knows that, if the proposal is made at P2 level, P1 will not get any gold coins. So P1 tries to accept a decision before P2 level.

P2 knows that If decision is made at P3 level, P1 will support P3(provided P1 is getting atleast 1 coin) and P2 is ended with nothing. So P2 try accept a decision before P3 level.

P3 knows that if decision is made at P4 level, P2 will support P4(provided P2 is getting atleast 1 coin) and P1&P3 ended with nothing. So P3 is willing to accept p5 decision(provided P3 is getting atleast 1). P1 will also accept P5 since even if he wait until P3 level, the maximum P1 can get is 1. But P1 also knows that the decision made at P4 level will be accepted by P2 and P1 will end up with nothing.

So the distribution will be (P1-1, P2-0, P3-1, P4-0, P5-98)

Hope this is clear.

Thanks,

AngelS

The solution in the original post is correct. It was fun reading through all the wrong answers though, keep it up guys! 🙂

This motivational criteria of each pirate in the problem statement should be clarified. It currently reads: “The first priority of the pirates is to stay alive and second to maximize the gold they get.”

It is then unclear how pirates behave towards outcomes of equal value (if outcome X and Y both means survival and 1 coin for pirate Z then which of them should Z go for?). If we assume that the are have time-waste-aversion then they’d go for the first possible of several equally good outcomes. If not then I’d assume they would flip a coin. If they are, quite pirate-ly, bloodthirsty, then they might go for last equally good outcome (survive + 1 coin) for the simple joy of seeing some go overboard.

The first pirate proposal (for n total pirates), is:

n=1: 100

n=2: 100, 0

n=3: 99, 0, 1

n=4: 99, 0, 1, 0

n=5: 98, 0, 1, 0, 1

n=6: 98, 0, 1, 0, 1, 0

We can just focus on the proposal value of the most experienced pirate because all others are in the form of 0, 1, 0, 1, …

hence, we can model the proposal for n pirates as the following recursive function:

f(n) = f(n-1) – n%2So, f(15) = 93, that is 91, 0, 1, 0, …

and f(25) = 88, that is 88, 0, 1, 0, …

I believe the answer is flawed. The question clearly states that their first priority is staying alive. Keeping in mind that the given “correct” answer to this question assumes that pirates 3 and 4 realize what will happen if they do not accept pirate 5’s proposal, we must assume that it is in their best interest to accept his proposal, or face the possibility of death. I believe it is safe to assume that both 3 and 4 can be bought at the right price, so as to avoid having to present their own proposals and facing death themselves. However, that price is not 1 coin. Valuing his life before the gold coins, the best choice for pirate 5 is to offer pirates 3 and 4 33 gold coins each, while keeping 34 to himself.

Actually, I jumped to a conclusion above.

Pirate 3 splits the pot into even 1/3’s (and let’s say he keeps the 100th gold piece for himself). I realize I can make more gold by getting him off the ship so I offer Pirate 1 additional gold.

As above, I become indifferent when I offer Pirate 1 67g to vote Pirate 3 off the ship (since I will get 33g by accepting Pirate 3’s offer right now).

But because Pirate 3 will die if we vote against him, he does not want me offering Pirate 1 67g. So he begins to pay me to not do so.

He will not automatically want to pay all of his gold to me, as I incorrectly stated above.

Once he offers me 34g I will hold out for more, hoping to get all of his gold. But Pirate 3 does not care whether he pays me or Pirate 1–only that one of us agrees to his plan.

So Pirate 1 and I should actually agree to settle on 50g each, as anything else will disadvantage one of us at the expense of the other.

So the result for three pirates should be (50, 50, 0), actually, if we are both rational and trustworthy agents.

Interesting.

I, too, feel the answer is incorrect, as it does not fully follow through on the pirate’s priorities to 1) survive and 2) maximize gold.

With only 2 pirates, Pirate 2 gets 100g and Pirate 1 gets 0g. That is plain enough to see.

But with three pirates, things turn out much differently, when we “sit down to devise a distribution strategy” (I’ll be Pirate 2 in this scenario):

Pirate 3: All right, Pirate one. If you vote against my proposal, I’ll get thrown off the ship and you’ll get no gold.

Pirate 1: Yup.

Pirate 3: So I’ll give you 1 gold and you vote with me.

Pirate 1: Ok.

Me (Pirate 2): Pirate 1, vote ‘no’ and I’ll give you 2 gold. (I’ll get 98, instead of 0).

Pirate 1: Ok.

Pirate 3: Oh oh. I’ll give you 3 gold!

Pirate 1: Ok!

Me (Pirate 2): 4.

So in this scenario, Pirate 3 will choose to live, and will end up forfeiting all his gold in order to outbid me.

So Pirate 3 votes to give all the gold to Pirate 1, which also isn’t satisfactory to me, so I will then offer to vote with Pirate 3 if he gives me 99g and keeps one for himself, instead of giving it all to Pirate 1.

Of course, Pirate 1 will have none of that, and should (if he is wise) begin to outbid me:

Pirate 1: Pirate 3, give me 98g and I’ll let you keep 2.

Pirate 3: OK!

Me (Pirate 2): 97g & you keep 3.

…

This continues until we get to 1 or 2 gold (depends on who first made the offer to pay Pirate 3. Note that only Pirate 3 has a direct incentive give away his last gold–his survival).

As soon as this occurs, I’ll offer Pirate 1 one more gold than he’s currently getting with his deal from Pirate 3 (I’ll offer either 2 or 3 gold), and the whole cycle will begin again.

As long as either Pirate 1 or 2 gets no gold, it is in their best interest to offer an incentive to participate in a voting bloc against the current proposal.

The strategy would then seem to settle with each pirate getting 1/3 of the gold. That means I am getting 33g (possibly 34g), and Pirate 1 is getting 33g (possibly 34g). Of course, I can do better if Pirate 3 were off the ship, so I’ll offer Pirate 1 one more gold to vote with me. Of course, Pirate 3 will respond. It is only when I have to promise Pirate 1 so much gold that I’d be poorer than I would be by accepting Pirate 3’s proposal would I stop.

So I become indifferent at the point where I promise Pirate 1 66 or 67g–beyond this, I’d end up with less gold than the 33g (or 34g) I’d get with Pirate 3’s proposal.

But with this situation, Pirate 3 dies, so it’s in his interest to pay me more than 33 or 34g. In fact, he should offer me all his share.

So then, Pirate 3 lives, I’d have 67g, and Pirate 1 would have 33g (and the proposal would get unanimous support).

The voting blocs get significantly more complex with 4 or 5 Pirates, but it’s easy to see from the above that the pattern isn’t be anything like (1, 0, 1, 0, … , 100-n).

Most pirates that I work with nowadays use crowdsourcing solutions…. so Mr experienced pirate should split gold equally BUT! Each pirate can only keep half there gold and has to give away their other half to most worthy pirate. As top pirate he should command respect and gain a lot if gold and no pissed off pirates, as would arise in the other ‘optimal’ solution.

Since the site doesn’t show my second function correcty, I only want to display first one. Please disregard my previous comment

//ASSUMPTION: totalGold >= numProrates/2

// Checks are left out intentionally

`//Displays distribution after totalGold distributed to pirates`

void displayDistribute(int numPirates, int totalGold)

{

cout<=0;i-=2)

{

cout<<"1,";

totalGold--;

}

cout<<totalGold<<"}"<<endl;

}

Considering the answer in reverse order:

If pirate 5 offers 1 coin to each pirate 4 and 3, pirate 4 can still vote aganist him and make the same deal himself with other pirates.

So by same continuity only pirate 2 can make a deal like that after voting against everybody.

So obviously pirate 5 will have to offer a larger share to pirate 4 and 3 to convice them to vote for him. so generously he will have to make a 40:30:30:0:0 or else pirate 4 will obviously vote against him and make the deal himself.

There are other alternate answers for more than 3 pirates.

Let’s assume we all agree that the optimal solution for 3 is {1, 0, 99}.

Now what happens with 4 pirates? I offer this as a different solution: {1, 0, 0, 99}.

The best pirate #1 can ever get is 1 gold, so he’ll vote for this. So will pirate #4.

Likewise, {1, 1, 0, 0, 98} is an alternate solution for 5 pirates because pirates 1-3 all know that the best they can get when there are 4 pirates is one gold apiece, so #1 and #2 will vote for this along with #5.

The key is that for n pirates pirate n-1 MUST be offered 0 gold and enough other pirates (1 .. n-2) need to be offered 1 gold to sway the vote. That scales to many many more than one possible solution for 15 or 25 pirates (or more).

Hi Aswin:

We have to assume from the question that all pirates have all information, i.e., pirate 4 can’t make a private deal with pirate 1 without pirate 5’s knowledge. So, if 4 offers 1 99 coins to vote against 5, then 5 will have to offer 99 to stop the betrayal. Pirate 1, as you note, can’t trust 4, but if 5 offers 1 the 99, it’s a done deal. 1 votes yes, and 4 realizes he can never get more than 1 coin after that, so he votes yes too.

Remember: the question is: what will Pirate 5 do to ensure his best advantage. I think we’re agreeing on that, but I’m saying 5 has to offer 99 coins to 1 to ensure his vote, not one coin. What complicates the situation is that getting a proposal rejected doesn’t just mean that someone gets no money–it means dying–so if 5 values his life at all, he has to give the *best* offer, not the least.

Hi mkay, there are a few things to consider here.

“if Pirate 1 votes no, he sends the message to Pirate 4 that he better up the deal or die.”What stops Pirate 4 from agreeing with Pirate 1 to kill Pirate 5 and then backstabbing Pirate 1 by not offering him anything… If Pirate 5 dies, then Pirate 4 is not going to offer Pirate 1 anything and Pirate 1 knows this. It is in the best interest of Pirate 1 to vote in favor of Pirate 5.

Aswin: we’re tripping over each other in the moderation queue. I didn’t propose a (0,1,0,0,99) solution. I proposed (99,0,0,1,0) based on the need to guarantee life first, profit second for Pirate 5.

Actually, it just occurred to me at posting that Pirate 4 can offer 0, 99, 0, 1 too. Pirate 2 would say yes because, while he is the only pirate with a chance to keep 100 coins, if 4 dies, he won’t get any at all.

If I were Pirate 4, I’d give the 99 to Pirate 3, the next most senior, since that will be safer since he outranks 1 and 2.

At no point, though, is he guaranteed safety if he tries to keep 99 coins.

Aswin: I’m assuming your comment was in response to mine. I think you’re situation supports my point: pirates are voting in their own self-interest. The question is framed as what is the best offer Pirate FIVE can make. Staying alive trumps any financial gain. Since we’re talking pirates here, if Pirate 1 votes no, he sends the message to Pirate 4 that he better up the deal or die. The only thing Pirate 1 has to lose is one coin pitted against 4 and 5’s much more dire risk of dying. Pirate 1 is gambling that Pirates 4 and 5 value their lives at 99 coins, not 1.

Assuming Pirate 5 dies, Pirate 4 has only two options to ensure his life (which is part of the problem): 99,0,0,1 or 0,0,99,1. If he goes with the former, he lives since 99 is the most Pirate 1 can ever get and will vote yes. If he goes with the latter, same thing for Pirate 3. And note: it’s the maximum he would have gotten in the Pirate 5 offer anyway which is why he would have voted yes then. Unless he really really hated Pirate 5. 🙂

He could try and reason with 3 to share the money evenly, but since we’re talking pirates here, 3 will say no. Why? Because if 4 dies, 3 can keep 99 coins and offer Pirate 1 only one coin. Only at that point is it in Pirate 1’s favor to vote yes for one coin because if 3 dies, he gets nothing.

Hi mkay,

If Pirate 5 proposes (0, 1, 0, 0, 99), there is no way Pirate 4 is going to agree to this. Pirate 4 will try and get Pirate 5 killed so he can take a big share. Pirates 1-3 in the same situation if Pirate 5 dies so there is no reason why they should only vote for Pirate 5. They can as easily not vote for Pirate 5 thus killing him. You solution might work if 2 out of Pirates 1-3 vote for him. This is based on luck. A guaranteed acceptable solution is preferred in this case.

Ok let’s say we go with your plan. Pirate 4 ensures Pirates 1-3 that his plan will be more beneficial. All four of them disapprove of Pirate 5’s plan and kill him. After Pirate 5 dies, what prevents Pirate 4 from taking 99 gold coins and screwing everyone else. The fact that these are Pirates makes their word unreliable. Pirates 1-3 are better of going with something they are offered now than to go with a promise of something better later.

I am assuming there was reason why this question was set with “Pirates” and not normal people. 🙂

The only way this solution makes sense is for pirate 5 to explain the math to pirates 1 and 3. When that happens, Pirate 1 realizes his *minimal* best option *mathematically* is to agree, but that assumes the only incentive is to maximize gold. It’s not, according to the premise: the incentive is to maximize the gold AND stay alive. That puts Pirate 1 and 2 in the position of never being at risk of being killed, which puts Pirate 1 in control of the situation. Pirate 5 has to weigh his life over Pirate 1’s risk of losing 1 coin.

In order to maximize gold AND stay alive, Pirate 5 has to propose 99,0,0,1,0. 99 coins are the best Pirate 1 can ever get, so he votes yes. Pirate 4 votes yes because he realizes if Pirate 5 dies, he is in the exact same position, so he votes yes because 1 coin is better than no coin or death.

I agree with Jax,

Since Pirate 4 is offered no gold in Pirate 5’s plan all he (she?) has to do is ensure Pirates 1-3 that his plan will be more beneficial to the remaining Pirates. In reality, I do not think the logic (although sound) behind Pirate 5’s plan will ensure that he will not be thrown off the ship. Why not make an example of Pirate 5 and assume Pirate 4 would bring a better proposal to the table? The fact that the people making the decision are “Pirates” and not say “Investment Bankers” is relevant to the solution.

Sorry, I thought pirate 5 was the lowest in the hierarchy (and I didn’t read the reasoning very carefully, otherwise I’d obviously have noticed, I admit).

Hi Geoff, in your post, you have Pirate 3 suggesting a plan and Pirates 4 and 5 voting on it which should never be the case. If pirate 3 is suggesting a plan, it means pirate 4 and 5 are dead.

This is bollocks. If he cares about his life then there is no way he’s going to make 2 disgruntled pirates by giving them zero gold. Especially since one of those is Pirate 4 which means he is highly ranked. If pirate 4 gets no gold then the chance of him rebelling is high.

Nice question but the mathematical answer does not sit well with the context in which the question is given. Pirates are fun but they also kill. I would not piss off my second in command by giving him zero gold.

I think this is not as straighforward as it seems. It reminds me a bit of the unexpected hanging paradox (see e.g. wikipedia), namely the induction seems to be sound, but then you realise the conclusion doesn’t hold: once they all realise this, if pirate number one proposes all but the last piratate to have 25 (or any other distribution in which at least more than half of the pirates other than the last get more than 0 or 1), they should vote in favour (after which they can throw the last pirate overboard for being such a sneaky bastard).

For anyone who’s curious, I published a solution to this puzzle where the pirates require a majority vote, rather than just half.

http://gcanyon.wordpress.com/2009/11/12/no-really-stop-me-if-youve-heard-this-one-before/

Also, to Philip, the general assumption for puzzles like this is that the participants are all completely logical and infinitely intelligent — so anything you can work out, they can work out.

Hi Philip, the question states that “They decide to sit down and devise a distribution strategy.”. That would mean the pirates can communicate before finally voting.

There is a lot of assumption about the communications which is allowed between pirates, if the pirates cannot talk secretly then this cannot be as there cannot be any secret communication. My first thought was that the pirates are in a group talking to each other publically.

It’s obvious.

15 Pirates

————-

7 gold coins for the 7 pirates that will get nothing and 93 for the 15th

1,0,1,0,1,0,1,0,1,0,1,0,1,0,93

25 Pirates

————-

12 gold coins for the 12 pirates that will get nothng and 88 for the 25th

1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,88