The Piratey Solution
Nov. 7, 2003
It seems no one was able to post a correct solution to the pirate problem, so here it is. The secret to this problem is to look at some cases where there are a small number of pirates. First, suppose we have two pirates. The larger of the two can simply give himself all the treasure and vote "yes." Since he is half the pirates, he isn't thrown overboard.
Now, if there are 3 pirates left, the second pirate knows that he can get it all if he votes "no" on any distribution scheme, but the third pirate would get nothing. Thus, if you give the weakest pirate even 1 gold coin, he will vote "yes." So, the strongest of 3 pirates will assign himself everything except 1 gold coin, and vote "yes."
If there are 4 pirates, the now second pirate knows he will get everything - 1 if he votes "no," so that's what he does. The third pirate gets nothing if the second pirate divides up the treasure, so even 1 gold coin will make him vote "yes." The last pirate's vote doesn't matter, since we have half now.
Its easy to construct a proof by induction from here, and it turns out the solution is to give P/2 coins to the weakest pirate, (P/2)-1 to the next weakest, and so on until you get to the pirate in the middle. He gets nothing along with all the other pirates up to you, and you get everything left over.