Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Pirates and the division of 100 gold coins

Puzzle: Five pirates discover a chest full of 100 gold coins.
The pirates are ranked by their years of service.
Pirate 5 having five years of service, Pirate 4 having four years and so on.
To divide up the loot, they agree on the following:

The most senior pirate will propose a distribution of the treasure.
All pirates will then vote, including the most senior pirate.
If at least 50% of the pirates on board accept the
proposal, then the gold is divided as proposed.
If not, the most senior pirate is killed by others.
Then the process starts over with the next most senior
pirate until a plan is approved.

How does the most senior pirate save his life and gets as
much coins for himself as possible ?

Solution: Let us break this problem into simpler parts first.

1) If there were only one pirate, he would keep all the gold for himself.

2) If there were two junior most pirates, the senior one would
keep all the gold for himself and his junior would have to agree
because the senior's vote would make 50% of the vote.

3) If there were 3 pirates, then the senior most of these, the 3rd pirate
gets to make the decision. He knows that if he is killed,
the junior most would get nothing. So he gives one
coin to him and gets his vote to make more than 50% vote.
He keeps 99 for himself and gives 0 to the 2nd one.

4) For 4 pirates case, 4th pirate knows the situations above.
He knows that the best junior-most traitor can get is 1 coin and the best 2nd pirate can get is 0 coins.
So if he gives just 1 coin to the 2nd pirate, then 2nd one would always agree.
So he keeps 99 for himself, gives zero to 3rd and 1st pirates and 1 coin to the 2nd pirate.
This gets him 50% votes and he wins.

5) Now coming to 5th pirate (huff !)
He has his own vote on whatever decision he makes offcourse and needs two more votes.
He knows that in case of his death, 1st and 3rd would get nothing.
So he buys their vote by offering them 1 coin each and keeps 98 for himself.

What if the number of pirates were 15?
For a larger number, a pattern needs to be observed here:

```No of Pirates(n)      No of coins got by each (nth, n-1 th ... )
1                                          100
2                                       100, 0
3                                     99, 0, 1
4                                  99, 0, 1, 0
5                               98, 0, 1, 0, 1
6                            98, 0, 1, 0, 1, 0
7                         97, 0, 1, 0, 1, 0, 1
```

Which means that to get the 50% votes, the senior most pirate needs to
give (n-1)/2 coins to his juniors.
So 15th pirate would get 100-(15-1)/2 = 100-7 = 93 coins.
And from the pattern, 14th pirate would not get any coin.
13, 11, 9, 7, 5, 3 and 1th pirates would get 1 coin each.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: