6 Pirates Fight for 1 Gold Coin

Question: Six pirates discover a chest containing 1 gold coin. They decide to sit down and devise a distribution strategy. The pirates are ranked based on their experience (Pirate 1 to Pirate 6, where Pirate 6 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 6 devises a plan which he knows will keep him alive. What is his plan?

This question was taken from pirates revisited.

Solution: This question is a more complex version of “5 Pirates Fight for 100 Gold Coins”. If you have not read through question, please do so. I am going to explain this solution assuming you know the other solution.

If there is only one pirate, he takes the coin. If there are 2 pirates, pirate 2 takes the coin leaving pirate 1 with nothing.

If there are 3 pirates, pirate 3 needs one more vote. There is no way we can convince pirate 2 since he benefits if pirate 3 dies. Pirate 3 gives the gold coin to pirate 1 to get his vote so he survives.

If there are 4 pirates, pirate 4 needs one more vote. He can’t give it to pirate 1 since pirate 1 will get the gold coin even if pirate 4 dies. He can give it either to pirate 2 or 3 which will get him another vote to ensure his survival.

If there are 5 pirates, pirate 5 needs two more votes. There is no way he can get two more votes since there is only one gold coin to bribe with. Pirate 5 dies regardless of his proposal.

If there are 6 pirates, pirate 6 needs two more votes. He will surely get pirate 5’s vote since pirate 5 will die if pirate 6 dies. If pirate 6 and pirate 5 die, pirate 4 will survive but will not get the gold coin. Pirate 6 can bribe pirate 4 with the gold coin and get his vote. That makes a total of 3 votes allowing pirate 6 to survive. He can also give the gold coin to pirate 1, 2 or 3 although giving it to pirate 2 or 3 is a little confusing since either of them could get the gold coin in the case of 4 pirates.

If you have any questions, please feel free to send me an email at [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it. VF6HD4EH987D

Continue Reading Below
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:

Book Cover

4 Responses

  1. manful says:

    the original question must have contained a third condition as seeing others die as the third priority which they will choose according to.

  2. daya says:

    @Mounia: There is no point in convincing pirates 2 since if pirate 3 dies he will only get the coin because there will be two pirates left and he can show 50%.

  3. Doggie says:

    It does change the reasoning but does it change the solution?

  4. mounia says:

    in the case where there are 3 pirates left, why is it that you say pirate 3 couldn’t convince pirate 2 ?
    > Sure he benefits if pirate 3 dies,
    > but he also benefits if pirate 3 proposes (0;1;0). because in this case, number 2 has no reason to refuse to vote for him since he gets the coin anyway. The only difference is that pirate 3 stays alive too and the question doesn’t say that the pirates have an interest in killing more experienced pirates even if their gain is the same….?
    Am I missing sthg here? Because if I don’t, it changes the whole reasoning 🙂

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>