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).