Here's the scenario. Five pirates, call them A through E for simplicity, have each stolen 20 gold coins from a treasure chest and each hidden them in a place where only they can find them. The five have come together to divide up the loot. They agree to do it as follows. Each in turn (from A to E) will make a proposal as to how to divide up the gold. The proposal will be voted on by all the pirates. If a majority vote yes, the gold will be divided in that manner. But if there's not a majority saying yes, the pirate that proposed the scheme will be killed. His gold is presumed lost (because he hid it) and (obviously) he will not be allowed to vote in any later decisions. Your challenge is to determine how the gold will be divided up, assuming that all the pirates make the smartest division possible and vote in the smartest way possible. Remember that nobody wants to die, and so the worst thing a pirate can do is propose a scheme that gets voted down. Assume that a pirate will vote for a scheme only if voting for the scheme gives him more gold than voting it down and then adopting the next one. (If the two are equal, assume the pirate votes NO, just because pirates are mean and enjoy killing each other) So, how much will each pirate get?
Pirate A makes the following offer: We get this by working backwards. Assume everyone but D and E are dead. D must offer at least D-19, E-21, or else E might as well vote no, kill D, and just keep his own 20 gold. Now say C is still alive. His best offer is C-40 D-20 E-0, because he will vote yes, as will D (because if he votes no, he only gets 19), and this is adopted. Bring B back to life. His best bet is to go: B-58 C-0 D-21 E-1. It is obvious that B and D will go for this. But E will, also, because getting 1 gold is better than the 0 gold he gets if he votes no and C's 40-20-0 division passes. Lastly, to conclude the problem, bring A back to life. He offers: A-97 B-0 C-1 D-0 E-2, and this passes, and A walks off a rich man. (Remember, C and E can not afford to vote no, cause if they do, B's plan or C's plan will pass and they will do even worse.)
