当前位置:网站首页>Cartoon: interesting pirate problem (full version)
Cartoon: interesting pirate problem (full version)
2022-07-05 17:28:00 【Small ash】
This week's cartoon about pirates released by Xiaohui , We have a heated discussion , Thank you very much for your support . This time, , Xiaohui made the following update :
1. Fixed a number error in Xiaohui's interview stage
2. added 6 Two pirates and 7 In a pirate situation , The best way of distribution
————— 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 :
As the number of Pirates increased to 7 people , The old boss was postponed to the third , The original second is postponed to the fourth ...... Please don't confuse here .
How to aggregate the two distribution results ?
In the balance 5 In the case of pirates , Or old six gets two gold coins , Old seven has no gold coin ; Or old six doesn't have gold coins , Lao Qi got two gold coins . From the perspective of probability , Each of these two situations has its own probability 50%, therefore The average income of the sixth and seventh is 1 Gold coins .
thus , Second, it's easier to analyze . Number two wants to form 4:2 The situation of , How does he distribute it ?
If you don't have yourself , The third can get 97 gold , So the third guy just gave up .
The remaining 5 When I was a pirate , Old four can't get gold , So give old four one and you can pull it together , Good service .
The remaining 5 When I was a pirate , ite 、 Old six 、 The average income of old seven is 1 gold , But we just need to woo two of them . So one of them didn't have a gold coin , The other two each gave two . So there's a permutation :
2, 2, 0
2, 0, 2
0, 2, 2
therefore , The number of gold coins the second keeps is 100 - 2 - 2 - 1 = 95. The complete distribution plan is 3 Kind of , As shown in the figure below :
Next , In order to analyze the strategy of the boss , We still need to aggregate the above three situations .
For five 、 Old six 、 Seven , They each have a two-thirds chance of getting two gold coins , There's a one-third chance that you won't get a gold coin . So their average return is 2 * 2/3 = 1.33 Gold coins .
thus , The boss has also become easy to analyze . The boss wants to form 4:3 The situation of , How does he distribute it ?
If you don't have yourself , The second can get 95 gold , So the second one just gave up .
The remaining 6 When I was a pirate , The third one doesn't get gold , So give old three one and you can draw them together , Good service .
The remaining 6 When I was a pirate , The fourth's income is 1 gold , ite 、 Old six 、 The average income of old seven is 1.33 gold , But no matter 1 One or two 1.33 gold , Give them two gold coins, you can win them over . We just need to woo two of them , So two of them didn't have gold coins , The other two each gave two . And then there's a permutation :
2, 2, 0, 0
2, 0, 2, 0
2, 0, 0, 2
0, 2, 2, 0
0, 2, 0, 2
0, 0, 2, 2
therefore , The number of gold coins the old man keeps is 100 - 2 - 2 - 1 = 95. The complete distribution plan is 6 Kind of , More complicated , There's no need to use pictures here , List the tables directly :
边栏推荐
- [binary tree] insufficient nodes on the root to leaf path
- 力扣解法汇总1200-最小绝对差
- C#实现水晶报表绑定数据并实现打印3-二维码条形码
- 独立开发,不失为程序员的一条出路
- 一文了解Go语言中的函数与方法的用法
- easyNmon使用汇总
- 一文了解MySQL事务隔离级别
- 深入理解Redis内存淘汰策略
- MySql 查询符合条件的最新数据行
- WR | Jufeng group of West Lake University revealed the impact of microplastics pollution on the flora and denitrification function of constructed wetlands
猜你喜欢
Embedded UC (UNIX System Advanced Programming) -3
Use JDBC technology and MySQL database management system to realize the function of course management, including adding, modifying, querying and deleting course information.
Complete solution instance of Oracle shrink table space
MySql 查询符合条件的最新数据行
机器学习01:绪论
Summary of optimization scheme for implementing delay queue based on redis
Redis+caffeine two-level cache enables smooth access speed
Example tutorial of SQL deduplication
Read the basic grammar of C language in one article
MYSQL group by 有哪些注意事项
随机推荐
机器学习01:绪论
First day of learning C language
Force deduction solution summary 729- my schedule I
Winedt common shortcut key modify shortcut key latex compile button
深入理解Redis内存淘汰策略
Mysql5.6 parsing JSON strings (supporting complex nested formats)
WR | 西湖大学鞠峰组揭示微塑料污染对人工湿地菌群与脱氮功能的影响
Example tutorial of SQL deduplication
一文了解MySQL事务隔离级别
漫画:如何实现大整数相乘?(下)
一口气读懂 IT发展史
Error in compiling libssh2. OpenSSL cannot be found
High number | summary of calculation methods of volume of rotating body, double integral calculation of volume of rotating body
How MySQL uses JSON_ Extract() takes JSON value
Three traversal methods of binary tree
Check the WiFi password connected to your computer
Flask solves the problem of CORS err
CMake教程Step2(添加库)
ICML 2022 | Meta提出魯棒的多目標貝葉斯優化方法,有效應對輸入噪聲
Tita performance treasure: how to prepare for the mid year examination?