mathematics classics

Chapter 2 The Problem of Pirates' Money Distribution
problem
Pirates, everyone has heard of it.This is a group of desperadoes who rob people's money and lives at sea, and they make a living by licking blood on the blade of a knife.In our impression, they are usually blind in one eye, and cover the bad eye with a black cloth or a black leather blindfold.They also have a good habit of burying treasures underground, and they always draw a treasure map for future generations to dig.But do you know that they are the most democratic group in the world.Those who participated in the piracy were rebellious men who did not want to obey orders, and all matters on board were usually resolved by voting.The captain's only privilege was to have his own set of cutlery—but other pirates could borrow it when he wasn't using it.The only punishment on board was being thrown overboard to feed the fish.

Now there are several pirates on board, and they want to share the stolen gold coins.Naturally, such issues are resolved by voting.The voting rules are as follows: first the most ferocious pirate proposes a distribution plan, and then everyone votes for one vote. If 50% or more of the pirates agree with the plan, then the plan will be distributed. If less than 50% of the pirates agree , then the pirate who proposed the plan will be thrown into the sea to feed the fish, and then the most ferocious pirate among the remaining pirates will propose a plan, and so on.

Solution
We'll start by making some assumptions about the pirates.

(1) The ferocity of each pirate is different, and all pirates know the ferocity of others, that is to say, each pirate knows the position of himself and others in the sequence of the proposal.Plus, each pirate is good at math and logic, and sane.Finally, private deals between pirates do not exist, because pirates trust no one but themselves.

(2) A gold coin cannot be divided, you can't have half of it and I have half of it.

(3) Of course every pirate does not want to be thrown into the sea to feed the fish, this is the most important thing.

(4) Of course every pirate hopes to get as many gold coins as possible.

(5) Every pirate is a realist. If he gets 1 gold coin in one plan, and in the next plan, he has two possibilities, one is to get many gold coins, and the other is to get no gold coins. Will agree to the current plan, and there will be no fluke.All in all, they believe that a bird in the hand is worse than two birds in the bush.

(6) In the end, every pirate loved other pirates being thrown overboard to feed the fish.As long as it doesn't harm his own interests, he will vote for his companions to feed the fish as much as possible.

Now, what if 10 pirates want to share 100 gold coins?

To solve these kinds of problems, we always work backwards from the last situation so that we know what were good and bad decisions at this last step.Then using this knowledge, we can get what decision should be made in the final second step, and so on and so on.If we tackle the problem directly from the beginning, we can easily get blocked by the question: "If I make this decision, what will the next pirate do?"

以这个思路，先考虑只有2个海盗的情况（所有其他的海盗都已经被丢到海里去喂鱼了）。记他们为P1和P2，其中P2比较凶猛。P2的最佳方案当然是：他自己得100枚金币，P1得0枚。投票时他自己的一票就足够50%了。

往前推一步。现在加一个更凶猛的海盗P3。P1知道——P3知道他知道——如果P3的方案被否决了，游戏就会只由P1和P2来继续，而P1就一枚金币也得不到。所以P3知道，只要给P1一点点甜头，P1就会同意他的方案（当然，如果不给P1一点甜头，反正什么也得不到，P1宁可投票让P3去喂鱼）。所以P3的最佳方案是：P1得1枚，P2什么也得不到，P3得99枚。

P4的情况差不多。他只要得两票就可以了，给P2一枚金币就可以让他投票赞同这个方案，因为在接下来P3的方案中P2什么也得不到。P5也是相同的推理方法只不过他要说服他的两个同伴，于是他给每一个在P4方案中什么也得不到的P1和P3一枚金币，自己留下98枚。

By analogy, the best plan for P10 is: he gets 96 coins himself, and gives a gold coin to each of P9, P2, P4 and P6 who can get nothing in the P8 plan.

Here is a table of the above reasoning (Y means agree, N means disagree): P1P2
0100
NY
P1P2P3
1099
YNY
P1P2P3P4
01099
NYNY
P1P2P3P4P5
101098
YNYNY
……

P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
01010101096
NYNYNYNYNY
Now we generalize the pirate money problem:
（1）改变一下规则，投票中方案必须得到超过50%的票数（只得到50%票数的方案的提出者也会被丢到海里去喂鱼），那么如何解决10个海盗分100枚金币的问题？

(2) Without changing the rules, what will happen if 500 pirates divide 100 gold coins?
(3) If each pirate has a savings of 1 gold coin, he can use this gold coin in the distribution plan, if he is thrown into the sea to feed the fish, then his savings will be included in the gold coin pile to be distributed What about this time?

By making small changes to the rules, the pirate gold distribution problem can have many variations, but the most interesting ones are probably (1) and (2) (the rule is still 50% of the votes), and this post is only for these two cases have a discussion.

首先考虑（1）。现在只有P1和P2的情形变得对P2其糟无比：1票是不够的，可是就算他把100枚金币都给P1，P1也照样会把他丢到海里去。可是P2很关键，因为如果P3进行分配方案的话，即使他一枚金币也不给P2，P2也会同意，这样一来P3就有P2这张铁票。P3的最佳方案就是：独吞100枚金币。

P4要3张票，而P3是一定反对他的，而如果不给P2一点甜头，P2也会反对，因为P2可以在P3的方案中得救，目前为什么不把P4丢到海里呢？所以要分别给P1和P2一枚金币，这样P4就有包括他自己1票的3票。P4的方案为：P1，P2每人1枚金币，他自己98枚。

The situation of P5 is more complicated, and he also needs 3 votes. P4 will oppose him, so there is no need to give it. Giving P3 a gold coin can make him support his plan, because he will get nothing in the next P4 plan.The problem is P1 and P2: as long as one of them supports it, it's fine.But it is not enough to give only 1 gold coin. In the P4 plan, they must have 1 gold coin, so just choose one of them at random and give 2 gold coins, and the other will be sorry and not given.In this way, the plan for P5 is: 97 coins for yourself, 3 coin for P1, and 1 coins for P2 or P2.

The P6 plan is based on the P5 plan, as long as each pirate who does not benefit from the P5 plan is given 1 gold coin.It should be noted that both P1 and P2 should be regarded as unprofitable in the P5 plan: they may get 2 gold coins, but they may not get 1 gold coin, so as long as P6 gives them 1 gold coin, according to "two birds in the forest, it is better to The principle of "one bird in hand" allows them to support the P6 plan.So P6's plan is unique: P1, P2, and P4 each get 1 gold coin, and P6 gets 97 gold coins for himself.

Going on like this, P9's plan is: P3, P5, and P7 each get 1 gold coin, and then choose one of P1, P2, P4, and P6 to give 2 gold coins, and P9 gets 95 gold coins.Finally, P10's plan is unique: P1, P2, P4, P6, and P8 each get 1 gold coin, and P10 gets 95 gold coins for himself.

(2) is the funniest (reminder: we're back to the 50% vote rule).The reasoning process in the original solution is valid until there are 200 pirates: P200 gives each even-numbered pirate 1 gold coin, including himself, and other pirates get nothing.Starting from P201, it becomes a little difficult to continue reasoning: in order not to be thrown into the sea, P201 must keep nothing for himself, and give all the odd-numbered pirates from P1 to P199 1 gold coin each, so as to win 100 votes, plus his own 1 vote, escaped unharmed. P202 can't get anything, he must use the 100 gold coins to buy 100 pirates who can get nothing from the P201 plan. It should be noted that this plan is not the only one: no gold coins can be obtained in the P201 plan Pirates are all odd-numbered pirates, there are 101 (including P201), so there are 101 schemes.

P203 has to get 102 votes, he only has 1 gold coins besides his own 100 vote, so he can only buy 100 votes, so the poor guy is thrown into the sea to feed the fish.However, P203 is a very important role, because P204 knows that if his plan is not approved, P203 will also be finished, so he has an iron ticket for P203.So P204 can breathe a sigh of relief: one vote for himself, one vote for P203, and 100 votes bought with 100 gold coins, and he is saved! The 100 pirates who are lucky enough to get 1 gold coin can be any 1 from P202 to P100: because the even-numbered ones can get nothing from the plan of P202, if P204 gives one of them 1 gold coin, the Pirates will definitely agree with this plan; as for pirates with odd numbers, they are only likely to benefit from the plan of P202 (probability is 100/101), so according to "two birds in the bush are worse than one bird in the hand" In principle, if he can get 1 gold coin, he will also agree with this plan.

接下去P205是不能把希望放在P203和P204这两张票上的，因为就算他被丢到海里去，P203和P204还可以通过P204的方案机会活下来。P206虽然可以靠P205的铁票，加上自己1票和100枚金币搞到的100票，只有102票，所以他也被丢到海里喂鱼。P207好不了多少，他需要104票，而他自己以及P205和P206的铁票加上100枚金币搞到的100票只有103票——只好下海。

P208 is lucky, he also needs 104 votes, but P205, P206, and P207 will all vote for his plan!Adding his own 1 vote and the 100 bought votes, he finally escaped the fate of being a fish food maker.

This way we have a new logic that can be pushed all the way down.Pirates can keep nothing for themselves, buy 100 tickets, and then rely on the iron tickets of some pirates who will definitely be thrown into the sea, so as to pass their plan.The pirates who had such luck were P201, P202, P204, P208, P216, P232, P264, P328 and P456... We see that such numbers are 200 plus a power of 2.

哪些海盗是受益者呢，显然铁票是不用（不能）给金币的。所以只有上一个幸运号码及他以前的那些海盗才有可能得到1枚金币。于是我们得到500海盗分100枚金币的结论是：前44个最凶猛的海盗被丢进海里，然后P456给P1到P328中的100个海盗每人1枚金币。

In this way, the most ferocious pirates were thrown into the sea, and the more ferocious pirates got nothing, but only the most gentle pirates could get 1 gold coin.As the Gospel of Matthew says: "Blessed are the meek, for they shall inherit the earth!"

(End of this chapter)