## Dividing up the loot… again!

**This blog has been split in three and all content moved to the new blogs – Qua Locus Life, Qua Locus Tech and Qua Locus Puzzle – comments are disabled here.**

Last week, we met 5 pirates with 76 gold coins. Here’s an interesting tweak on the same puzzle…

Now there are 32 pirates, still strictly ordered from most senior to most junior, but this time they have uncovered a stash of only 10 indivisible gold coins that they must divide amongst themselves.

Exactly as in the previous puzzle, these pirates are rational and want to survive, know that the other pirates are rational too, and each wants as much gold for themselves as possible. Also, being pirates and not very nice, they will always prefer a fellow pirate die if they still get as much gold.

Also as in the previous puzzle, the pirates have agreed to divide the coins using the following method:

- The most senior pirate alive proposes a split, and all the pirates vote on it
- If 50% or more of the pirates vote for the proposal then the gold is split as proposed
- If less than 50% of the pirates vote for the proposal then woe betide the most senior pirate who proposed the split, because he must walk the plank and the newly most-senior pirate begins the process again
- The pirates will abide by this agreement
- The pirates will make no other agreements

Which is the most senior pirate that will survive, what will he propose and why will it work?

(Hint: The most senior pirate of all the pirates that can survive is a lucky man – there are several possible proposals that he can make which will keep him alive)

No answers posted yet… I’ll post mine on Sunday… 🙂

Christo FogelbergJune 8, 02012 at 17:16

Here is my full solution to this puzzle, with a generalisation to n coins at the end.

As a first step, let’s consider the strategy of the 20th pirate. Using the same logic as the solution to http://wp.me/p2hwZ1-3f we see that the 20th pirate will propose {1, 0, 1, 0, …, 1, 0}. Therefore we know that pirate 20 can survive and gets 1 gold coin using the above strategy.

But we can do better. In particular, pirate 21 can propose: {0, 0, 1, 0, 1, 0, 1, 0, …, 0, 1}. Because none of the ten odd-numbered pirates get gold if the 20th pirate divides the coins, they are better off under this arrangement and will vote for it. Since pirate 21 does not want to die, he will also vote for his own proposal, giving him the 11 votes that he needs.

Pirate 22 can follow the same strategy, but this time offering gold to the other ten even-numbered pirates who get nothing if pirate 21 makes a proposal: {0, 0, 1, 0, 1, 0, …, 1, 0}. Pirate 22 will also vote for his own proposal and so he squeaks in with the 11 votes he needs.

Unfortunately pirate 23 is doomed. He needs 12 votes. He can offer gold to any of the 10 odd-numbered pirates 1-21 who get nothing under pirate 22, and pirate 23 will also vote for his own proposal, but this will give him only 11 votes and so he must walk the plank.

So far, so good – this is all (relatively) straight forward and it looks like 22 is the most senior pirate who will survive. But there is only one proposal that pirate 22 can make which will pass. In combination with the hint (above), this suggests we can do better.

Pirate 23 will walk the plank if he has to make a proposal. Therefore, pirate 23 will vote for any proposal of pirate 24’s just to avoid this fate – even if he does not get any gold in pirate 24’s proposal. If pirate 24 offers 1 gold to any ten of the eleven odd-numberd pirates who get nothing when 22’s proposal is accepted and after adding his own vote and 23’s, pirate 24 gets the 12 votes he needs.

Rolling this logic forward, pirate 25 will only get his own vote and the ten bribes (23 will not vote for him because he knows 24 has a winning proposal with his vote). Similarly, pirate 26 is also doomed, although he will get 12 votes (his own, the ten bribes and 25’s), and pirate 27, who needs 14 votes, is also doomed (although he can get 13 – his own, ten bribes, 25’s and 26’s).

On the other hand, pirate 28 will survive. Pirates 25, 26 and 27 will vote for him regardless so that they don’t have to make a proposal, and he can buy 1 vote with each gold coin that he allocates to 10 of the other even-numbered pirates (who would get nothing under the next proposal to be accepted, 24’s). This gives him the 14 votes that ne needs.

Finally, continuing to roll this logic forward, we can see that pirates 29, 30, 31 and 32 are also doomed. Therefore 28 is the most senior pirate that can survive in this situation. Note also that he has 10 gold coins to allocate amongst 12 other even-numbered pirates, therefore he can make 12C10 = 66 different proposals, any one of which will be accepted.

Generalisation for n coins:

The k’th pirate will survive iff k<=n or iff k=(2^i)-n for some positive integer i.

Christo FogelbergJune 10, 02012 at 11:14