Posted August 06, 2011
pirate solution time:
We know that in the last round (that is, the (n-1)th round), the nth and (n-1)th pirate have a 0 and 10 split respectively, because in the case of a tie the proposal passes, and this is (n-1)'s proposal, everyone else being thrown overboard.
By backward induction, in the (n-2)th round, (n-2)'s proposal takes this into account, knowing that if the proposal fails, nth pirate gets 0 coins, so he offers him 1 coin instead. (n-2) only needs 2 votes to win, so that's it. Note that (n-1)th pirate cannot credibly commit to beating that offer, given the assumptions of the game. So the (n-2)th round is 9, 0, 1.
By the same process, the (n-3)th round: 9, 0, 1, 0.
(n-4)th: 8, 0, 1, 0, 1.
(n-5)th: 8, 0, 1, 0, 1, 0.
So generalizing, if c is the number of coins, the (n-x)th round is an (x+1) digit sequence with c-(x-1)/2 rounded down for the first digit, and repeating 0s and 1s for the remaining x digits. In the case where n>=c, that (x+1) sequence has an upper limit of 2c digits. (prove this?)
By extrapolation, the first round, where x = n-1, is an n digit (bounded by 2c if n>=c) sequence starting with c-(n-2)/2 rounded down.
Not as proofy as it should be, but good enough I think.
We know that in the last round (that is, the (n-1)th round), the nth and (n-1)th pirate have a 0 and 10 split respectively, because in the case of a tie the proposal passes, and this is (n-1)'s proposal, everyone else being thrown overboard.
By backward induction, in the (n-2)th round, (n-2)'s proposal takes this into account, knowing that if the proposal fails, nth pirate gets 0 coins, so he offers him 1 coin instead. (n-2) only needs 2 votes to win, so that's it. Note that (n-1)th pirate cannot credibly commit to beating that offer, given the assumptions of the game. So the (n-2)th round is 9, 0, 1.
By the same process, the (n-3)th round: 9, 0, 1, 0.
(n-4)th: 8, 0, 1, 0, 1.
(n-5)th: 8, 0, 1, 0, 1, 0.
So generalizing, if c is the number of coins, the (n-x)th round is an (x+1) digit sequence with c-(x-1)/2 rounded down for the first digit, and repeating 0s and 1s for the remaining x digits. In the case where n>=c, that (x+1) sequence has an upper limit of 2c digits. (prove this?)
By extrapolation, the first round, where x = n-1, is an n digit (bounded by 2c if n>=c) sequence starting with c-(n-2)/2 rounded down.
Not as proofy as it should be, but good enough I think.