Cartoon: interesting [pirate] question

————— the second day —————

Pirates share gold coins ：

Yes 5 A pirate , To obtain the 100 Gold coins , So they have to work out a way to distribute the gold coins . The way of negotiation is as follows ：

1. from 5 The pirates took turns to come up with a distribution plan .

2. If more than half of the pirates （ Including the proposer ） Agree to the plan , According to the scheme .

3. If the number of people who agree to the plan （ Including the proposer ） Less than or equal to half , The proposer will be thrown into the sea to feed the fish , The rest of the pirates went on to discuss the distribution .

4. Pirates are absolutely rational , To get as many gold coins as you can . But in the case of equal returns , Will tend to throw the proposer into the sea .

ask ： What kind of distribution plan should the first pirate propose , To ensure that you are not thrown into the sea , And maximize your own interests ？

Take a chestnut ：

At this point, the first pirate came to propose a distribution plan , He said ：

I want to 100 Gold coins , The rest of you don't have a single coin ！

obviously , The rest of the kids are against it , As a result, the first proposer was thrown into the sea .

Next, it's the second pirate's turn to come up with a distribution plan , He said ：

I just 1 Gold coin , be left over 3 A little friend, each of you 33 Gold coin ！

The third pirate is against , The other two agreed , More than half agreed （4 : 1）, So the allocation is performed according to this method .

————————————

How to use recursion to simplify the problem ？ Let's analyze in detail , Later, the five pirates are called Laoyi for short 、 The second 、 Old three 、 Three old four 、 ite .

When the old one put forward the distribution plan , Think about it this way ：

If I'm thrown into the sea , be left over 4 A pirate , What is the optimal allocation scheme for the second child at this time ？

I just need to add a little bit to the distribution plan for the second child , To win more support .

When the second one came up with the distribution plan , I think the same way ：

If I'm thrown into the sea , be left over 3 A pirate , At this time, what is the optimal allocation plan for the third person ？

I just need to add a little bit to the third year's distribution plan , To win more support .

Third, when he put forward the distribution plan , Still think like this ：

If I'm thrown into the sea , be left over 2 A pirate , At this time, what is the optimal allocation plan for the fourth ？

I just need to add a little bit to the old four's distribution plan , To win more support .

The whole recursive process , Just like the picture below ：

When does this recursive process end ？ Until there are two people left .

think about it , When there are two people left , What's the situation ？

At this time, old four There is no choice ！ No matter how he allocates , Even if 100 Five gold coins , Old five can still oppose , The fourth was thrown into the sea , All the gold coins belong to Lao Wu .

thus , The third thought ： The fourth has no optimal decision , So whatever I ask for , All four will agree , And five must disagree .

As long as more than half of the people agree, the distribution can be carried out , So the best strategy for the third is as follows ：

Next , The second thought to himself ： Without me , The third can get 100 Gold coins , So I won't agree with you anyway . But I can try to “ Entrapment ” Fourth and fifth , formation 3 : 1 The situation of .

In the third “ Obscene power ” Next , They didn't get a single gold coin . I gave them a gold coin for each , It's better to let the third one distribute it , So they will definitely agree .

therefore , The optimal strategy of the second is as follows ：

Finally, it's the elder's turn , Lao Yi thought in his heart ： Without me , The second can get 98 Gold coins , I can't give him more than 98 gold , Just give up on him , Only two of the three left , formation 3 : 2 The situation is just .

Who do you want to win over ？ With the second strategy , The third one doesn't get gold , So third best “ Wait on ”. I'll give it to the third 1 gold , The third one must agree .

As for fourth and fifth , Could have gotten 1 gold , So I have to give more than the second , To win support . But I don't have to win them both at the same time , Or give old four two gold coins , Give up five , Or give old five two gold coins , Give up old four .

therefore , The optimal strategy of the old one is as follows ：