Interview Question – Pirate and the Gold Chest

Interview Question – Pirate and the Gold Chest :

Once there were five pirates, each of them equally rational, intelligent and greedy. The pirates can be numbered as P1, P2, P3, P4 and P5 such that P5 has 1 years of service experience, P4 has 2 years of experience, P3, P2 and P1 has 3, 4 and 5 years of experience respectively.

One day they find a chest of 100 gold coins and they decided to divide it among themselves. Everyone being equally greedy wanted maximum profit, so they decided for the following solution:

1) Each pirate will get a chance to propose a distribution rule, and then a poll will be conducted where all the pirates will vote on the proposal
2) If the proposal get 50 % or more votes then the proposal will be accepted and the distribution will take place, else the pirate will be killed and the other pirate will get a chance to propose a distribution rule, so on and so forth.
3)The senior most pirate gets the first chance to propose the rule.

Given that all the pirates are greedy as well as rational, and you being the senior most pirate, what will be the proposal of distribution so that you get maximum profit and you are not killed as well.

Solution

These kind of questions really need a different thought process, you will never get to the problem if you straight way just into finding proposal rules and divide the gold equally and any other brute force method.

Case 1:

Let us assume that there is just one pirate P1,and he found the chest of 100 gold, how does he propose the rule of distribution.
He can just say he owns the 100 gold, votes himself and keeps the gold. Pretty simple and easy.

Case 2:

Let us now assume that there are two pirates P1 and P2 and they found the chest of 100 gold, how does P1 propose the rule of distribution.
He can just say he owns the 100 gold, and P2 get 0 , at the time of voting P1 votes in favor of the rule and P2 votes against it. so P1 gets 50% and wins, he keeps 100 gold coins and P2 accepts 0.

Case 3:

Let us now assume that there are three pirates P1, P2 and P3, and they found the chest of 100 gold, how does P1 propose the rule of distribution. Here is the trick:

Let us find out, what will happen if P1 loses ? I believe P2 gets a chance to propose a rule and P2 will propose a rule as in Case 2, he will keep all the gold and P3 gets nothing. P3 and P1 are well aware of this fact as they are rational and intelligent. So P3 will support P1 even if he is getting any thing greater than 0.

Hence, P1 proposes a rule saying as below:

P1 – 99 coins,
P2 – 0 coins and
P3 – 1 coin.

Now as P3 knows this is the best he can get, so he votes in favor of P1 and P1 votes for himself. He gets 66% vote and wins. Distribution is done.

Case 4:
Let us now assume that there are four pirates P1, P2, P3 and P4 and they found the chest of 100 gold, how does P1 propose the rule of distribution.The trick is same as Case 3.

Let us find out, what will happen if P1 loses ? P2 gets a chance to propose a rule and P2 will propose a rule as in Case 3, he will keep 99 gold for himself give 1 gold to and P4, P3 gets nothing. P1 and P3 are well aware of this fact that if P2 gets a chance he will give 1 coin to P4, so P1 will take P3 to his side and P3 knows that he can at at least get 1 coin if he votes for P1

Hence, P1 proposes a rule saying as below:

P1 – 99 coins,
P2 – 0 coin,
P3 – 1 coin and
P4 – 0

Now as P3 knows this is the best he can get, so he votes in favor of P1 and P1 votes for himself. He gets 50% vote and wins. Distribution is done.

Case 5:
Similarly, let us assume that there are five pirates P1, P2, P3, P4 and P5 and they found the chest of 100 gold, how does P1 propose the rule of distribution.The trick is same as Case 4.

P1 proposes a rule saying as below:

P1 – 98 coins,
P2 – 0 coin,
P3 – 1 coin,
P4 – 0 coin and
P5 – 1 coin.

Answer

This reveals a pattern that if N is the total number of pirates and total number of gold coins is G where N is sufficiently smaller than G then P1 will propose a rule where he gets G – N/2.
If N is odd then all the pirates at odd indexes excepts for P1 will get 1 coin each and P1 get G – N/2.
If N is even then all the pirates at even indexes except for P1 will get 1 coin each and P1 still gets G-N/2

Conclusion

We must try to understand and break down the problem to a simpler version to reach the solution.

Hope this helps, happy reading. Stay connected and stay Subscribed

  • Anshuman

    Nice and rational explanation

  • Miguel

    “If N is even then all the pirates at even indexes except for P1 will get 1 coin each and P1 still gets G-N/2”

    This is incorrect, as seen when N = 4. In that case, P1 gets 99 and P3 gets 1 gold coin. So, it’s always odd indexes.

    • dharam

      Thanks for the comment, the way you see it will change my statement…

      The assumption I made was “if there are N pirates then ” Pn is at index 1 , Pn-1 is at index 2 and so on … By the way thanks for pointing it out.

      According to me, it is something like below:
      index : 1 2 3 4 5

      pirate: P5 P4 P3 P2 P1
      coins : 1 0 1 0 98

      pirate: P4 P3 P2 P1
      coins : 0 1 0 99

      • Miguel

        I see, I didn’t think that way. Following the question statement and that P1 is the first to propose the distribution, I think it would make sense for P1 to be at index 1. Anyway, this is not a big deal regarding the solution.

        Nice post by the way 🙂

        • dharam

          Thanks, and I am glad to know that you liked it.