Friday, October 3, 2008

Greedy Pirates solution

Two weeks ago, I presented the Ten Greedy Pirates. This is a very classic puzzle, though the number of pirates may vary, and the bonus problem was my own creation. The solution involves solving a simpler case first, and then progressively moving on to more difficult cases. That is, first we try 1 pirate, then 2, then 3, and so forth up to ten pirates. Because we're treating this as a perfectly deterministic process, every pirate knows how much gold they will get if there is a mutiny, if there is one less pirate.

Here are the first few cases to get you started. Each pirate is numbered from youngest to oldest.

1 pirate:
Pirate 1 gives himself all the gold. Duh.

2 pirates:
Pirate 2 needs only one vote: his own. So he takes all the gold for himself.

3 pirates:
Pirate 3 must buy one vote. Pirate 1's vote cost one coin (because pirate 1 would get no gold in the 2-pirate scenario, while Pirate 2's vote would cost 101 coins (because pirate 2 would get 100 gold in the 2-pirate scenario). So he gives one coin to pirate 1, taking the rest for himself.

And so on...

That's all well and good for the first three pirates, but for ten, I just made a grid of numbers. The Nth column corresponds to the gold received by pirate N, and the Mth row corresponds to the scenario with M total pirates.

Now, I do the same with the bonus problem. Note that the oldest pirate prefers to buy the votes of the youngest pirates possible, insofar as it costs him no extra gold. The X represents death...