Pirates Gold
Five pirates discover 100 gold coins.
They decide on a process for dividing the coins as follows:
The most senior pirate proposes an allocation. All the pirates vote.
If at least half agree, this becomes the allocation, and the process
ends. If not, the most senior pirate is executed, and the same process
is carried out with the four remaining pirates.
If only one pirate remains, he/she gets the lot.
All the pirates are very clever logicians.
They have the following priorities, in order:
(1) to remain alive,
(2) to get as many coins as possible,
(3) to execute as many pirates as possible.
Preliminary Notes
Priority (3) merely says that a pirate will not vote for a plan if
he/she is going to get the same from the next (successful) plan down.
In fact, the one-pirate stage will never be reached.
The Basic Solution
Denote the pirates by P1, P2, ... starting with the senior pirate.
(a) If P4 gets to propose a division of the coins, he can't be outvoted,
since his vote itself constitutes half the remaining votes. Thus he
will propose: (P4 100, P5 0).
(b) P3 needs one vote in addition to his own. He cannot buy the vote
of P4. (Even if he offered P4 100 coins, P4 would vote against him
based on priority 3.) He can, however, obtain the vote of P5 for 1
coin, which is more than P5 will get under (a). So he will propose:
(P3 99, P4 0, P5 1).
(c) P2 also needs one vote in addition to his own. He could buy the
vote of P3 for 100 coins, but will get the vote of P4 for just 1.
His proposal: (P2 99, P3 0, P4 1, P5 0).
(d) P1 needs two votes in addition to his own. P2's vote would be far
too expensive, but the others' are far more reasonable. His maximum
share would be obtained by: (P1 98, P2 0, P3 1, P4 0, P5 1).
This outcome is counter-intuitive. P1 can only hope that his fellow
pirates really have been clever enough to work this out for themselves.
More Pirates
In fact, this solution can be generalized for n pirates (n <= 202). Each
odd-numbered pirate should assign one coin to the odd-numbered pirates
below him (nothing to the others); each even-numbered pirate, to the
even-numbered pirates below him. Surprisingly this does not depend on
the oddness or evenness of n, essentially because, whether there are 2p
or 2p + 1 pirates below him, the current senior pirate requires p of
their votes in addition to his own.
Note that for 201 or 202 pirates, P1 actually gets no gold, but does get
his life. (He buys 100 votes with gold, plus his own.)
For n > 202, there are not enough coins to employ the preceding rule,
and the situation changes. Up to this point, coin is paramount and no
pirate is executed. Now, for the pirates near the top, their life is the
key factor.
For n > 202, number the *last* 202 pirates P1, P2, ..., P202 as before;
number the more senior pirates P0, P[-1], P[-2], ... *upwards*.
Note that, if the process gets that far, P1 simply carries out the earlier
rule.
So what about P0? No division that he puts forward will save his life.
The best he can do is to buy the votes of the P4, P6, ..., P202, who
will lose if the process gets down to P1. (Coins are used for the votes
of the lower pirates; lives, for the upper ones.) But this gives him
only 101 votes, including his own, out of 203. His plan will save P2's
life, but so will P1's, and the "greater number dead" rule will seal
P0's fate. So P0 must vote for P[-1]'s plan to save his own life.
By giving one coin to P4, P6, ..., P202, P[-1] will get 100 votes plus
his own and P0's: 102 out of 204, and his plan will be accepted.
Is that the end of the story? No. Neither P0 nor P[-1] need vote for
P[-2] to save their own lives, so he will garner only 101 votes out of
205. He must vote for P[-3]. (Note, by the way, that the coins must now
switch back to P3, P5, ... P201, who will get nothing from P[-1].)
P[-3] will get only 102 votes out of 206, P[-4] 103 out of 207. P[-5],
however, with the votes of P[-2], P[-3], P[-4] and his own to go with
the hundred, will get 104 votes out of 208.
But now none of these need vote for P[-6], and so we go round the loop
again, building up an even longer string until the extra senior pirates
counteract the extra total number. (Of course, they always do, because
each vote gained counteracts two extra pirates. The string lengths are
successive powers of 2.)
The senior pirates who are "safe" are P[-1], P[-5], P[-13], ..., that
is, P[-k] where k is (power of 2) - 3.
In the case of 500 pirates mentioned by Ian Stewart, the pirates will
be numbered from P[-297] to P202. P[-253] is safe, but the first 44
pirates will be executed, as Stewart notes.
And that really is the end of this variation.
A Variant
What if we change the rules so that a plan requires MORE THAN half the
votes to succeed, instead of at least half?
With five pirates, P4 now can't avoid being outvoted by P5. So he must
vote for P3's plan in order to survive. Thus P3's division will be (P3
100, P4 0, P5 0).
P2 needs two votes with his own: (P2 98, P3 0, P4 1, P5 1).
P1 also needs two of P3, P4 and P5, presumably P3 and either of the
others: (P1 97, P2 0, P3 1, P4 2, P5 0) or (P1 97, P2 0, P3 1, P4 0,
P5 2).
With a sixth, more senior, pirate (P0), a new twist appears. He needs
four votes: his own, P2's for 1 coin, P3's for 2, and either P4 or P5.
Unfortunately neither he nor they know which plan P1 will choose. 1 coin
each would benefit one of them, but they don't know which, and each
might each be prepared to chance the "double or quits" odds. So P0 must
presumably offer one or the other 3.
The rest is left to the reader.