Solution to the Pirate Problem
The problem
A group of 7 pirates has 100 gold coins. They have to decide amongst themselves how to divide the treasure, but must abide by pirate rules:- The most senior pirate proposes the division.
- All of the pirates (including the most senior) vote on the division. If half or more vote for the division, it stands. If less than half vote for it, they throw the most senior pirate overboard and start again.
- The pirates are perfectly logical, and entirely ruthless (only caring about maximizing their own share of the gold).
So, what division should the most senior pirate suggest to the other six?
The solution
The solution involves looking at what happens with only 2 pirates, and working up from there.(We assume that the most senior pirate has the
letter A. Others
will be B, C, D etc, depending on how many there are in the group.)
2 Pirates
Pirate A suggests he gets all the gold. He votes for it, so
it carries.
Pirate A gets 100 coins, pirate B gets 0.
3 Pirates
Pirate A knows that if he’s thrown overboard, pirate C would
get nothing (as the situation would revert to the two pirate example
above, with pirate C promoted to pirate B). So if pirate A bribes
pirate C with 1 coin, pirate C will vote in favour.
Pirate A gets 99
coins, pirate B gets 0, pirate C gets 1.
4 Pirates
Pirate A
knows that if he dies, then pirate C gets nothing (again, it will become
the 3 pirate case, and pirate C will be promoted to pirate B), so he
needs 1 coin to bribe him.
Pirate A gets 99 coins, pirate B gets 0,
pirate C gets 1, pirate D gets 0.
5 Pirates
Now pirate A
needs 3 votes, so he must bribe each of the pirates who would get 0
coins if he dies with 1 coin each.
Pirate A gets 98 coins, pirate B
gets 0, pirate B gets 1, pirate D gets 0, pirate E gets 1.
6 Pirates
Same story: bribe pirate B and pirate D.
Pirate A gets 98
coins, pirate B gets 0, pirate C gets 1, pirate D gets 0, pirate E gets
1, pirate F gets 0.
7 Pirates
In this final stage (although you can continue indefinitely!) the senior pirate has to get 4 votes, so must bribe 3 pirates… might as well bribe the 3 that have the most to lose if he dies (i.e., pirates C, E and G). Pirate A gets 97 coins, pirates C, E and G get 1 coin each, and the others get nothing.