## 100 pirates and 1000 gold coins

There are 100 pirates on a ship. They have distinct dates of birth. They find 1000 gold coins. They want to distribute the coins among themselves. The oldest pirate is supposed to propose a distribution of the coins, and then all the pirates, including himself, vote on whether the distribution is acceptable. If at least half of the pirates on the ship vote for it, the coins are distributed according to the proposed distribution. Otherwise, the oldest pirate who proposed the distribution is killed and thrown overboard, and the oldest among the remaining pirates makes a new proposal. This continues until a proposal is accepted.

Each pirate decides his vote after considering three factors. For each pirate, survival is the most important necessity. After ensuring survival, each pirate maximizes the number of coins he gets. He prefers to throw the oldest pirate overboard if it doesn't affect his survival and the maximum number of coins he gets.

Which pirate gets the greatest number of gold coins? How many coins does he get?

[SOLVED]

#### Vikram Agrawal solved this puzzle:

The oldest pirate gets $$1000 - 49 = 951$$ coins. He gives one coin each to the third oldest pirate, the fifth oldest pirate, and so on till he gives one coin to the second youngest pirate.

If all pirates except the youngest two are executed, then the youngest pirate gets nothing, so the youngest pirate must avoid this situation. Taking advantage of this, the third youngest pirate must give a coin to the youngest pirate if all pirates except the youngest three are executed. In this way, he can get the youngest pirate's vote and he doesn't have to give anything to the second youngest pirate. Similarly, if all but the youngest four pirates are executed, the fourth youngest pirate must give a coin to the second youngest pirate to get his vote. Similarly, if all but the youngest five pirates are executed, the fifth youngest priate must give a coin each to the third youngest pirate and the youngest pirate in order to get their votes. Continuing this argument in a similar way, we find that the oldest pirate needs $$49$$ votes apart from his own vote to stay alive. He can get this by giving away $$49$$ coins.

#### Dave Dodson solved this puzzle:

Let $$p_1, p_2, \dots, p_{100}$$ be the 100 pirates where $$p_i$$ is older than $$p_j$$ if $$i \lt j$$. Thus, $$p_1$$ is the oldest pirate and $$p_{100}$$ is the youngest pirate.

Suppose that all but the last two pirates have been thrown overboard. Then pirate $$p_{99}$$ can take $$1000$$ coins and leave $$p_{100}$$ with nothing.

If all but the last three pirates have been thrown overboard, $$p_{98}$$ can take $$999$$ coins, give one to $$p_{100}$$, and leave $$p_{99}$$ with nothing. $$p_{98}$$ will vote 'yes', and so will $$p_{100}$$ because if he votes 'no' he gets one less coin in the next round.

Continuing in the same way, $$p_{97}$$ can take $$999$$ coins and give $$1$$ to $$p_{99}$$, leaving $$p_{98}$$ and $$p_{100}$$ with nothing. $$p_{99}$$ will vote 'yes' because he will get nothing in the next round if he votes 'no'.

Etcetera.

Finally, $$p_1$$ can take $$951$$ coins, by giving one coin each to $$p_3, p_5, p_7, \dots, p_{99}$$, and nothing to the other pirates. The $$49$$ pirates with one coin each vote 'yes', because if they vote 'no', they will get nothing when $$p_1$$ is thrown overboard and $$p_2$$ distributes the coins.

### Credit

This puzzle is based on a puzzle from folklore: