China DOS Union

The Pirates' Problem
Ian Stewart

The logic of mathematics sometimes leads to conclusions that seem very strange. The general rule is that if there is no flaw in the logical reasoning, then the conclusion must stand, even if it contradicts your intuition. In September 1998, Stephen M. Omohundro of Palo Alto, California, sent me a puzzle that belongs exactly to this category. This puzzle had already been circulating for at least ten years, but Omohundro modified it, making its logical issues especially complicated.

First let's look at the puzzle in its original form. Ten pirates have seized a hoard of 100 gold coins and are planning to divide up the loot. These are pirates who believe in democracy (of course, a democracy of their own peculiar kind), and their custom is to distribute it as follows: the fiercest pirate proposes a distribution plan, and then all the pirates (including the proposer himself) vote on it. If 50% or more of the pirates approve the plan, it passes and the loot is divided accordingly. Otherwise, the pirate who proposed it is thrown into the sea, and then the next most powerful pirate repeats the process.

All the pirates are happy to see one of their companions thrown into the sea, but if given the choice, they would still rather get some cash. Naturally they also do not want to be thrown into the sea themselves. All the pirates are rational, and they know that the other pirates are rational too. In addition, no two pirates are equally powerful — these pirates are arranged in a complete hierarchy from top to bottom, and everyone knows both his own rank and everyone else's. These gold coins cannot be divided further, nor can several pirates jointly own a coin, because no pirate trusts his companions to honor any arrangement for sharing a coin. This is a gang in which every man looks out only for himself.
What distribution plan should the fiercest pirate propose in order to get the most gold for himself?

For convenience, let us number the pirates according to how cowardly they are. The most timid pirate is Pirate 1, the next most timid is Pirate 2, and so on. Thus the most powerful pirate gets the largest number, and the proposals are made in reverse order from top to bottom.

The key to analyzing all strategy games of this kind is to work backward from the end. At the end of the game, it is easy to see which decisions are favorable and which are not. Once that is determined, you can apply it to the second-to-last decision, and so on. If you start from the beginning of the game, you will not get very far. The reason is that all strategic decisions amount to asking: "If I do this, what will the next person do?" Therefore, the decisions made by the pirates below you matter to you, while the decisions made by the pirates before you do not, because in any case you can do nothing about them.

Keeping this in mind, we can see that our starting point should be the stage where only two pirates are left — namely Pirates 1 and 2. At that point the stronger pirate is Pirate 2, and his best distribution plan is obvious: all 100 gold coins go to him alone, and Pirate 1 gets nothing. Since he will certainly vote in favor of his own plan, that accounts for 50% of the total, so the plan passes.
Now add Pirate 3. Pirate 1 knows that if Pirate 3's plan is rejected, then in the end only 2 pirates will remain, and Pirate 1 will definitely get nothing — and Pirate 3 also understands that Pirate 1 knows this. Therefore, as long as Pirate 3's plan gives Pirate 1 a little sweetener so that he does not go away empty-handed, Pirate 1 will vote for it no matter what the rest of the plan is. So Pirate 3 needs to split off as little gold as possible to bribe Pirate 1, yielding the following plan: Pirate 3 gets 99 gold coins, Pirate 2 gets nothing, and Pirate 1 gets 1 gold coin. Pirate 4's strategy is similar. He needs 50% of the votes, so like Pirate 3 he also needs to find one ally. The minimum bribe he can offer that ally is 1 gold coin — but whom can he buy with that coin???

The problem of dividing the gold among 10 pirates is relatively easy to solve. Has anyone come up with the correct answer?

Also:
Omohundro's contribution was to extend the problem to the case of 500 pirates, that is, 500 pirates dividing 100 gold coins. Clearly, a similar pattern still holds — at least within a certain range.
In fact, the pattern described above holds all the way up to Pirate 200.
What is more interesting is what happens after Pirate 200, hehe... and it is much more difficult too!!!

Too long~~~~

Just reading this is nothing, the tiring part is thinking it through! Can anyone figure it out?

Pirates 2, 4, 6, and 8 get one coin each; 1, 3, 5, 7, and 9 get nothing; Pirate 10 gets 96 coins.

Brilliant! yiyesong really is brilliant! The way to divide it among 10 pirates is indeed like that...
What if there are 100 pirates?
What if there are 200 pirates?
What if there are 500 pirates?

The pattern is the same up to 200 pirates.
For 100 pirates, 2, 4, 6...98 each get one coin, 1, 3, 5...99 get nothing, and Pirate 100 gets 51 coins.
The same is true for 200 pirates. Even-numbered pirates each get one coin, odd-numbered pirates get nothing.
For 500 pirates, among 1, 3, 5...199, 201, 202, any 100 people can each get one coin; all the other pirates up to No. 456 get no gold, and Pirates 457 to 500 are thrown into the sea.

Impressive, I admit defeat. I didn't expect the kids here to all be so smart~

Who are you calling kids?

Aren't we all kids? We're all still at the stage of liking little animals and comics. Ah, did I say something wrong?

This article was first published in the famous Scientific American magazine.
I read it a long time ago.
I also remember that this question seemed to have appeared in Microsoft's test questions!

Then Shen Jie, is the answer I gave for 500 pirates right or not?

Nope!
The answer isn't just one.
It's a method of calculation!

500 pirates divide 100 gold coins.
Clearly, a similar pattern still holds — at least within a certain range.
In fact, the pattern described above holds all the way up to Pirate 200. Pirate 200's plan would be:
all the odd-numbered pirates from 1 to 199 get nothing, while all the even-numbered pirates from 2 to 198 each get 1 gold coin, and the remaining 1 gold coin goes to Pirate 200 himself.

At first glance, this method of argument seems no longer applicable after Pirate 200, because Pirate 201 cannot produce more gold to bribe other pirates. But even if he gets no gold, Pirate 201 at least hopes not to be thrown into the sea, so he can distribute it this way: give 1 gold coin each to all the odd-numbered pirates from 1 to 199, and keep none for himself. Pirate 202 likewise has no other choice and can only take no gold at all either — he must use all 100 gold coins to bribe 100 pirates, and those 100 pirates must be the ones who would get nothing under Pirate 201's plan.
Since there are 101 such pirates, Pirate 202's plan is no longer unique — there are 101 possible bribery schemes. Pirate 203 must get 102 votes in favor, but clearly he does not have enough gold to bribe 101 companions. Therefore, no matter what distribution plan he proposes, he is doomed to be thrown into the sea to feed the fish. However, although Pirate 203 is doomed to die, that does not mean he plays no role in the course of the game. On the contrary, Pirate 204 now knows that in order for Pirate 203 to save his life, he must avoid a situation in which he himself has to propose a distribution plan, so no matter what plan Pirate 204 proposes, Pirate 203 will certainly vote for it. Thus Pirate 204 finally gets lucky and saves his life: he can get his own 1 vote, Pirate 203's 1 vote, and the votes of another 100 bribed pirates, just enough to reach the 50% needed to stay alive. The pirates who receive gold must belong to the 101 pirates who would definitely get nothing under Pirate 202's plan.
And what about Pirate 205's fate? He is not so lucky. He cannot count on Pirates 203 and 204 to support his plan, because if they vote against Pirate 205's plan, they can gleefully watch Pirate 205 get thrown into the sea to feed the fish, while their own lives can still be preserved. Thus, no matter what plan Pirate 205 proposes, he is bound to die.
The same is true of Pirate 206 — he can certainly get Pirate 205's support, but that is not enough to save his life. Similarly, Pirate 207 needs 104 votes in favor — besides the 100 votes he buys and his own 1 vote, he still needs 3 more votes to avoid death. He can get the support of Pirates 205 and 206, but he still lacks one vote and simply cannot get it, so Pirate 207's fate is also to go into the sea and feed the fish.
Pirate 208's luck turns again. He needs 104 votes in favor, and Pirates 205, 206, and 207 will all support him. Adding his own vote and the 100 bought votes, he gets through and saves himself. The pirates he bribes must be among those who would definitely get nothing under Pirate 204's plan.
Since there are 101 such pirates, Pirate 202's plan is no longer unique — there are 101 possible bribery schemes. Pirate 203 must get 102 votes in favor, but clearly he does not have enough gold to bribe 101 companions. Therefore, no matter what distribution plan he proposes, he is doomed to be thrown into the sea to feed the fish. However, although Pirate 203 is doomed to die, that does not mean he plays no role in the course of the game. On the contrary, Pirate 204 now knows that in order for Pirate 203 to save his life, he must avoid a situation in which he himself has to propose a distribution plan, so no matter what plan Pirate 204 proposes, Pirate 203 will certainly vote for it. Thus Pirate 204 finally gets lucky and saves his life: he can get his own 1 vote, Pirate 203's 1 vote, and the votes of another 100 bribed pirates, just enough to reach the 50% needed to stay alive. The pirates who receive gold must belong to the 101 pirates who would definitely get nothing under Pirate 202's plan.
And what about Pirate 205's fate? He is not so lucky. He cannot count on Pirates 203 and 204 to support his plan, because if they vote against Pirate 205's plan, they can gleefully watch Pirate 205 get thrown into the sea to feed the fish, while their own lives can still be preserved. Thus, no matter what plan Pirate 205 proposes, he is bound to die.
The same is true of Pirate 206 — he can certainly get Pirate 205's support, but that is not enough to save his life. Similarly, Pirate 207 needs 104 votes in favor — besides the 100 votes he buys and his own 1 vote, he still needs 3 more votes to avoid death. He can get the support of Pirates 205 and 206, but he still lacks one vote and simply cannot get it, so Pirate 207's fate is also to go into the sea and feed the fish.
Pirate 208's luck turns again. He needs 104 votes in favor, and Pirates 205, 206, and 207 will all support him. Adding his own vote and the 100 bought votes, he gets through and saves himself. Those he bribes must be among the pirates who would definitely get nothing under Pirate 204's plan (the candidates include all the even-numbered pirates from 2 to 200, as well as Pirates 201, 203, and 204).

Now a new pattern can be seen, one that will continue to hold from here on out: the pirates whose plans can pass

(their distribution plans all use the gold to bribe 100 companions while they themselves get nothing at all) are spaced farther and farther apart, while the pirates in between will be thrown into the sea no matter what plan they propose — therefore, in order to save their lives, they will support any distribution plan proposed by a pirate more powerful than themselves. The pirates who avoid ending up in the fishes' bellies include 201, 202, 204, 208, 216, 232, 264, 328,

456, that is, pirates whose numbers are equal to 200 plus some power of 2.

Now let us see which pirates are the lucky ones who get bribed. The way the bribes are distributed is not unique. One method is to have Pirate 201 distribute bribes to all the odd-numbered pirates from 1 to 199,

have Pirate 202 distribute them to all the even-numbered pirates from 2 to 200, then have Pirate 204 bribe the odd-numbered pirates,
Pirate 208 bribe the even-numbered pirates, and so on, in other words alternately bribing odd-numbered and even-numbered pirates.

The conclusion is: when 500 pirates use the optimal strategy to divide the gold, the top 44 pirates are doomed to die,
while Pirate 456 gives 1 gold coin each to all the odd-numbered pirates from 1 to 199, and the problem is solved. Because of the kind of democratic system these pirates practice, things turn out so that most of the fiercest pirates end up feeding the fish, though sometimes they also feel lucky — although they do not get any of the stolen gold, at least they can avoid death. Only the 200 most timid pirates have any chance of getting a share of the loot, and among them only half can actually get a single gold coin. Truly, it is the timid who inherit the wealth.

Then that means my answer was right after all! That's exactly how I analyzed it.
Shen Jie, go back and take a good look at my answer.
KO: I think those one hundred gold coins don't necessarily have to go to odd numbers 1-199; besides them there are also 201 and 202. So I said that among 1, 3, 5...199, 201, 202, any 100 people each get one gold coin. The other pirates up to No. 456 get no gold, and Pirates 457 to 500 are thrown into the sea.

Interesting. Fun. Seems pretty hard.