# Pirate puzzle

There are 10 pirates in a rowing boat. Their ship has just sunk but they managed to save 1,000 gold doubloons. Being greedy bastards they each want all the loot for themselves but they are also democratic and want to make the allocation of gold as fair as possible. But how?

They each pick a number, from 1 to 10, out of a hat. Each person in turn starting with number 1, decides how to divvy up the loot among the pirates in the boat. They then vote. If the majority of pirates approve of the allocation then the

loot is divided accordingly, otherwise that particular pirate is thrown overboard into the shark-infested sea. In the latter case, the next pirate in line gets his chance at divvying up the loot. The same rules apply, and either the division of the filthy lucre gets the majority vote or the unfortunate soul ends up in Davy Jones s locker.

Question: how should the first pirate share out the spoils so as to both guarantee his survival and get a decent piece of the action?

Solution

This is obviously one of those questions where you have to work backwards, inductively, to the solution for 10 pirates. Along the way we ll see how it works for an arbitrary number of pirates.

Let's start with two pirates, with 1,000 doubloons to share. Pirate 2 gets to allocate the gold. Unless he gives it all to Pirate 1 the vote will be 50:50 and insufficient to save him. Splash! We are assuming here that an equal split of votes isn't quite enough to count as a majority. So he gives Pirate 1 the entire hoard, and prays that he lives. (Of course, Pirate 1 could say hard luck and dump Pirate 2 overboard and still keep the money.)

Now on to the three-pirate case. In making his allocation Pirate 3 must consider what would happen if he loses the vote and there are just two pirates left. In other words, he should make his allocation so that it is preferred to the next scenario by sufficient numbers of pirates to ensure that he gets a favourable vote.

Pirate 3 allocates 1,000 to himself and nothing to the others. Obviously Pirate 3 will vote for this. And so will Pirate 2, if he votes against in the hope of getting some loot he will find himself in the two-pirate situation... in which case he could easily end up over the side.

 Pirate 3 Pirate 2 Pirate 1 0 1000 1000 0 0

Now to four pirates. Pirate number 3 is not going to vote for anything number 4 says because he wants Pirate 4 in the deep. So there's no point in giving him any share at all. Pirates 2 and 1 will vote for anything better than the zero they'd get from the three-pirate scenario, so he gives them one each and 998 to himself.

 Pirate 4 Pirate 3 Pirate 2 Pirate 1 1000 0 1000 0 0 998 0 1 1

With five pirates similar logic applies. Pirate 4 gets zero. Then Pirate 5 needs to get two votes from the remaining three pirates. What is the cheapest way of doing this? He gives one to Pirate 3 and two to either of Pirates 2 and 1. Pirate 5 gets the remaining 997.

 Pirate 5 Pirate 4 Pirate 3 Pirate 2 Pirate 1 1000 0 1000 0 0 998 0 1 1 997 0 1 2 / 0 0 / 2

Pirate 6 needs four votes to ensure survival, his own plus three others. He'll never get Pirate 5 so he needs three votes from Pirates 4, 3, 2 and 1. Pirate 4 is cheap, he only needs 1 doubloon. But how to get two votes from the remaining Pirates 3, 2 and 1?

There are clearly several options here. And we are going to have to think carefully about the actions of the Pirates when faced with uncertainty.

Imagine being Pirate 2 when Pirate number 6 is allocating the gold. Suppose he gives you zero, what do you do? You may as well vote against, because there is a chance that on the next round you will get two doubloons. If Pirate 6 gives you two doubloons you should vote in favour. Things cannot be improved on the next round but may get worse. If given one doubloon now, what should you do? Next round you will either get zero or two. A tricky choice. And a possibly personal one.

But it is up to Pirate 6 to make sure you are not faced with that tricky decision which may result in his expulsion from the boat.

The conclusion is that Pirate 6 should give two doubloons to any of Pirates 3, 2 and 1. It doesn't matter which.

On Pirate 7's turn he will give zero to Pirate 6, one to Pirate 5 and two to any of Pirates 4 down to 1, again it doesn't matter which two, they will both now vote in his favour.

Now we settle down into a rhythm. Here's the entire allocation table.

This Brainteaser is particularly relevant in quantitative finance because of the backward induction nature of the solution. This is highly reminiscent of the binomial model in which you have to calculate today's option price by working backwards from expiration by considering option prices at different times.

Another of these backward induction types is the famous Brainteaser, the unexpected hanging. In this problem we have a prisoner who has been condemned to be executed in ten days' time and an unusually considerate executioner. The executioner wants the prisoner to suffer as little mental anguish as possible during his last days and although the prisoner knows that sometime in the next ten days he will be executed he doesn't know when. If the executioner can surprise him then the prisoner will be able to enjoy his last few days, at least relatively speaking. So, the executioner's task is to wake the prisoner up one morning and execute him but must choose the day so that his visit was not expected by the prisoner.

Let's see how to address this problem by induction backwards from the last of the ten days. If the prisoner has not been executed on one of the first nine days then he goes to bed that night in no doubt that tomorrow he will be woken by the executioner and hanged. So he can't be executed on the last day, because it clearly wouldn't be a surprise. Now, if he goes to bed on the night of the eighth day, not having been executed during the first eight days then he knows he can't be executed on the last day because of the above, and so he knows that he must be executed tomorrow, day nine. Therefore it won't be a surprise and therefore the execution can't happen on the ninth day either. We have ruled out the last two days, and by working backwards we can rule out every one of the ten days.

On day four the prisoner is awoken by the executioner, and hanged. Boy, was he surprised!

Where did our backward induction argument go wrong? Ok, now I can tell you that this brainteaser is called the unexpected hanging paradox. There have been many explanations for why the prisoner's logic fails. For example, because the prisoner has concluded that he can't be hanged, then to surprise him is rather simple.