Yo-ho-ho and a democratic vote
"Shiver me gudgeons and caulk the dogwatch, but here's plunder to cringle any man's futtock-plate!" Short Jim Pewter poured gold coins from hand to hook in glee. He was captain of the pirate ship Pretty Polly, and the nine other crewmembers knew that he was the fiercest pirate on board. In fact, they all knew exactly who was fiercer than whom, and no two pirates were equally fierce, so there was a precise pecking-order. The Pretty Polly had just completed a successful attack on a schooner bound from C?diz, and their haul was 100 gold pieces, each a single gleaming coin.
"Ahaargh, lads," snarled Pewter with an evil grin. "You all knows I keeps a tight ship, an' a fair one, ahaargh!" He brandished his cutlass. "So we'll split the loot in our usual democratic piratical way, right mates?" The crew cheered- Pewter was, after all, the fiercest pirate, and they always cheered anything he said.
"As Cap'n, I opens the bidding. I'll make a perposal about 'ow we does the division, and then we all votes on it, ahaargh-one vote each, including me. If half of us or more say 'aye,' the perposal passes, and that's 'ow we split the loot. Otherwise you lads toss me overboard to feed the sharks-and the next fiercest pirate is elected Cap'n and makes a new perposal... and so on until somebody's perposal passes."
The crew cheered again. They all liked throwing people overboard, but they liked hard cash even better. Naturally, they were not keen to be thrown overboard themselves. All the pirates were rational, knew that the other pirates were rational, knew that they knew that... and so on. They also knew that the gold pieces must be considered indivisible, and that there was no point in making agreements to share pieces, because no pirate could trust his shipmates to stick to the bargain.
What division of spoils should Pewter propose, to avoid becoming shark-bait and secure himself as much loot as possible?
Hint: work backwards from the last two pirates, assuming that the voting ever gets that far. All pirates can work out what this scenario implies. Here are the first few steps. Call the pirates P1, P2, ..., P10 in increasing order of ferocity, so P10 = Pewter. If the voting ever gets to the point where only P1 and P2 are left on board, then P2 can (and will) propose to keep all the loot for himself, and P1 can't outvote him. Next, suppose that only P3, P2, and P1 remain on board. Now P1 knows-and P3 knows that he knows-that if P3's proposal is voted down, P1 will get nothing. So P1 will vote in favour of anything that P3 proposes, provided it yields P1 more than nothing. P3 therefore bribes P1 by proposing that P1 gets one gold piece, P2 gets nothing, while P3 gets the other 99. Now suppose that the voting gets down to just P4, P3, P2, and P1...
ANSWER
Pewter (P10) should propose to keep 96 gold pieces for himself, to give one gold piece to each of P8, P6, P4, and P2, and none to the odd-numbered pirates.
To explain: if only P1-P4 remain, then P4 needs 50 per cent of the vote, so again he needs to bring exactly one other pirate on board. The minimum bribe he can use is one gold piece, and he can offer this to P2 since P2 will get nothing if P4's proposal fails and P3's is voted on. So P4's proposed allocation is
P1 P2 P3 P4
0 1 0 99
P5 needs to bribe two pirates. The minimum bribe he can use is one gold piece to each of them, and the only way he can succeed with this number is to propose the allocation
P1 P2 P3 P4 P5
1 0 1 0 98
The analysis proceeds in a similar manner, with each proposal being uniquely prescribed by giving the proposer the greatest possible number of coins, subject to enough bribes to ensure a favourable vote, until we get to P10:
P1 P2 P3 P4 P5
0 1 0 1 0
P6 P7 P8 P9 P10
1 0 1 0 96
