Paul's Puzzler: Pirates and Gold Bars - The Answer

If you missed the question, it's in the article that was published in the previous issue of our ezine.  (Read puzzle.)  Here is the allocation that the #10 pirate must propose to ensure for him the maximal share and to allow him to be able to live to enjoy his loot.

#10:     96 bars

#9:       0 bars

#8:       1 bar

#7:       0 bars

#6:       1 bar

#5:       0 bars

#4:       1 bar

#3:       0 bars

#2:       1 bar

#1:       0 bars

To prove this, we need to run through a bit of inductive reasoning.  Suppose we got down to just two pirates, #1 and #2, #3 having been just thrown overboard.  Pirate #2, being the ranking pirate, proposes the following:

#2:       100 bars

#1:       0 bars

Clearly # 2 votes ‘yes’ and # 1 votes ‘no’, so #1, having received 50% of the votes, wins.

Obviously # 3 could do this analysis also, so he would try to “bribe” either #2 or #1 for his vote.  The smaller the bribe, the more is left for him, of course.  Who should he bribe?  One who has the most to lose, and that is #1.  So here is his proposal:

#3:       99 bars

#2:       0 bars

#1:       1 bar

As expected, #3 votes ‘yes’ and #2 votes ‘no’.  So the “control” lies with # 1.  And this is where our intuition can get us into trouble:  it’s the least powerful pirate who has the ultimate control!

Clearly, #1 could vote ‘no’, but then the consequences are that (i) #3 is thrown overboard and (ii) # 1 gets 0 bars.  Since 1 bar is better than 0 bars, he votes ‘yes’.

From this point on, it is a breeze!  Pirate #4 knew all of that before we got to this point.  Therefore, #4 would make the following proposal:

#4:       99 bars

#3:       0 bars

#2:       1 bars

#1:       0 bar

So #4 gets #2 to vote ‘yes’ with him, while #3 and #1 vote ‘no’.

And so on!

Editor: Paul is scheduled to teach the 2-day UMTS seminar scheduled for Nov 5-6, 2007 (Washington, DC).