We all know that every mathematical puzzle should have pirates in it. Following is arguably the pirate puzzle:
Five pirates have 100 gold coins that they wish to divide among themselves. In the spirit of honor and fairness among pirates, they divide the coins according to the following rules: the least senior pirate begins by proposing a distribution of the coins. All of the pirates, including the proposer, vote on whether to accept the proposal, or to make the proposer walk the plank. If at least half of the pirates accept the proposal, then the coins are distributed accordingly. Otherwise, the proposer walks the plank, and the next senior pirate proposes a distribution, all remaining pirates vote, etc.
Each pirate is rational, and knows that all pirates are rational. Each pirate wants to survive if at all possible. Each pirate is greedy, meaning that he always prefers more gold as long as it doesn’t get him killed. Finally, each pirate is bloodthirsty, meaning that he will gladly make another pirate walk the plank as long as it doesn’t cost him any gold or his life.
What happens, and how much gold does each pirate get?
This is a very well-known problem, one of many in the long list of “tech interview” problems that are not very useful in that capacity precisely because they are so well-known. However, we can expand on the problem in a few ways that I think still provides some interesting exercise.
First, what happens if there are more pirates than coins? For example, suppose that there are 100 pirates and only 5 coins. Better yet, what if there are p pirates and c coins, where, say, p = 1000 and c = 100?
Also, instead of accepting a proposed distribution with at least half of the votes, suppose that some larger fraction f is required. For example, instead of f = 1/2, what if f = 2/3?
In other words, rather than posing this problem in a way that may be solved with pencil and paper– i.e., as a problem in mathematics or logic– consider it as a computer science problem: write a program to determine how the gold is distributed– and which pirates survive– as a function of (p, c, f). Not only is this a nice programming problem, but the actual answers are interesting as well, particularly when there are way too many pirates and not enough gold to go around.
As usual, solutions are welcome in the comments.