The pirate game with 100 gold coins, where a proposal passes when at least half the living pirates approve, counting the proposer, and a rejected proposer is thrown overboard. Pirates want to survive first and take coins second. Up to what crew size does the most senior pirate always survive his own proposal, and which larger crews still let him survive?

The pirate game with 100 gold coins, where a proposal passes when at least half the living pirates approve, counting the proposer, and a rejected proposer is thrown overboard. Pirates want to survive first and take coins second. Up to what crew size does the most senior pirate always survive his own proposal, and which larger crews still let him survive?

Approach: Count the votes a proposer must buy as a function of the crew size, and compare that count against the number of coins available to buy them with.

202. With p pirates alive the proposer needs at least ceil(p/2) votes, his own plus ceil(p/2) - 1 bought from others. The same backward induction as the five pirate case prices a vote at 1 coin, since a pirate who would get nothing under the next proposal accepts a single coin. With 100 coins the proposer can buy at most 100 votes, so survival requires ceil(p/2) - 1 <= 100, that is ceil(p/2) <= 101, which holds up to p = 202. At p = 202 he gives all 100 coins away and keeps nothing for himself, and he survives. At p = 203 he needs 101 bribes with only 100 coins, so he dies. Above that the pattern stops being monotone. A pirate who is doomed under every proposal that follows will approve anything that saves him, so his vote costs nothing, and the proposer survives again at 204, then 208, 216, 232 and in general at 200 plus a power of two, which continues without bound. There is therefore no largest surviving crew, only a last unbroken run, and it ends at 202.

Follow-up: At 204 pirates, how many coins does the proposer keep, and which pirates vote for him?

Key concepts: backward induction, vote counting, bribe budget.