—————? 第二天? —————

海盜分金幣問題：

有5個海盜，獲得了100枚金幣点额，于是他們要商量一個方法來分配金幣舔株。商議方式如下：

1. 由5個海盜輪流提出分配方案。

2. 如果超過半數(shù)海盜（包括提出者）同意該方案还棱，則按照該方案分配载慈。

3. 如果同意該方案的人數(shù)（包括提出者）小于等于半數(shù)，則提出者要被扔到海里喂魚诱贿，剩下的海盜繼續(xù)商議分配娃肿。

4. 海盜們都是絕對理性的咕缎，以自己盡可能多獲得金幣為目的珠十。但是在收益相等的情況下，會傾向把提出者扔到海里凭豪。

問：第一個海盜應(yīng)該提出怎樣的分配方案焙蹭，才能保證自己既不被扔到海里，又能使自己利益最大化嫂伞？

舉一個栗子：

此時第一個海盜來提議分配方案孔厉，他說：

我要100枚金幣拯钻，你們其他人一個金幣也沒有！

顯然撰豺，其他小伙伴一致反對粪般，結(jié)果第一個提出者被扔到了海里。

接下來輪到第二個海盜提出分配方案污桦，他說：

我只要1個金幣亩歹，剩下3個小伙伴每人33個金幣！

第三個海盜反對凡橱，剩下兩個小伙伴同意小作，同意者超過了半數(shù)（4 : 1），于是按照這個方法執(zhí)行了分配稼钩。

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

如何利用遞歸思想來簡化問題呢顾稀？讓我們來詳細分析一下，后文把五個海盜簡稱為老一坝撑、老二静秆、老三、老四绍载、老五诡宗。

老一在提出分配方案的時候，不妨這樣思考：

如果我被扔到海里了击儡，剩下4個海盜塔沃，此時老二的最優(yōu)分配方案是什么呢？

我只要在老二的分配方案上稍微增加一點阳谍，就能贏得更多的支持蛀柴。

老二在提出分配方案的時候，也會這樣思考：

如果我被扔到海里了矫夯，剩下3個海盜鸽疾，此時老三的最優(yōu)分配方案是什么呢？

我只要在老三的分配方案上稍微增加一點训貌，就能贏得更多的支持制肮。

老三在提出分配方案的時候，還是會這樣思考：

如果我被扔到海里了递沪，剩下2個海盜豺鼻，此時老四的最優(yōu)分配方案是什么呢？

我只要在老四的分配方案上稍微增加一點款慨，就能贏得更多的支持儒飒。

整個遞歸過程，就像下圖一樣：

這個遞歸過程到什么時候截止呢檩奠？剩下兩個人為止桩了。

想想看附帽，當剩下兩個人的時候，是什么情形井誉？

此時老四沒有任何選擇蕉扮！無論他如何分配，哪怕把100枚金幣都給老五颗圣，老五仍然可以反對慢显，導致老四被扔到海里，金幣全歸老五所有欠啤。

由此荚藻，老三心想：老四沒有最優(yōu)決策，所以無論我提出什么要求洁段，老四都一定會同意应狱，而老五一定不同意。

由于只要超過半數(shù)同意就可以執(zhí)行分配祠丝，所以老三的最優(yōu)策略如下：

接下來疾呻，老二暗自尋思：如果沒有我，老三能獲得100枚金幣写半，所以無論如何不會同意我岸蜗。但我可以設(shè)法“籠絡(luò)”老四和老五，形成 3 : 1 的局面叠蝇。

在老三的“淫威”下璃岳，他們原本一個金幣都得不到。我給他們一人一枚金幣悔捶，好過由老三來分配铃慷，所以他們肯定會同意。

因此蜕该，老二的最優(yōu)策略如下：

終于輪到老一了犁柜，老一心里琢磨：如果沒有我，老二能獲得98枚金幣堂淡，我總不能分給他多于98枚馋缅，索性放棄他，只要剩下三人中籠絡(luò)到兩人绢淀，形成 3 : 2 的局面即可萤悴。

要籠絡(luò)誰呢？以老二的策略更啄，老三得不到金幣稚疹，所以老三最好“伺候”居灯。我給老三1枚，老三一定同意。

至于老四和老五蹋偏，本來可以得到1枚铅鲤，所以我必須比老二給的多，才能贏得支持跃赚。但我又沒必要同時籠絡(luò)他倆，要么給老四兩枚金幣，放棄老五赂鲤，要么給老五兩枚金幣，放棄老四柱恤。

因此数初，老一的最優(yōu)策略如下：

由于海盜數(shù)目增加到7人，原本的老大順延成為老三梗顺，原本的老二順延成為老四......大家注意這里不要混淆泡孩。

如何把兩種分配結(jié)果進行聚合呢？

在剩余5個海盜的情況下寺谤，要么老六得到兩枚金幣仑鸥，老七沒有金幣；要么老六沒有金幣变屁，老七得到兩枚金幣眼俊。從概率學的角度來分析，這兩種情況發(fā)生的幾率各占50%粟关，所以老六和老七的平均收益都是1枚金幣疮胖。

這樣一來，老二就變得容易分析了闷板。老二想要形成 4:2 的局面获列，他該怎么分配呢？

如果沒有自己蛔垢，老三可以得到97枚击孩，所以老三直接放棄掉。

剩余5個海盜時鹏漆，老四得不到金幣巩梢，所以給老四一枚就可以拉攏，很好伺候艺玲。

剩余5個海盜時括蝠，老五、老六饭聚、老七的平均收益都是1枚忌警，但我們只要拉攏其中兩人就行。所以其中一人沒有金幣秒梳，另外兩人各自給兩枚法绵。這樣就形成了一個排列組合：

2箕速， 2， 0

2朋譬， 0盐茎， 2

0， 2徙赢， 2

因此字柠，老二自己保留的金幣數(shù)量是 100 - 2 - 2 - 1 =?95。完整的分配方案有3種狡赐，如下圖所示：

接下來窑业，為了分析老大的策略，我們?nèi)匀恍枰焉厦嫒N情況聚合一下枕屉。

對于老五数冬、老六、老七搀庶，他們各自有三分之二的幾率得到兩枚金幣拐纱，有三分之一的幾率得不到金幣。所以他們的收益平均值是 2 * 2/3 =?1.33?枚金幣哥倔。

這樣一來秸架，老大也變得容易分析了。老大想要形成 4:3 的局面咆蒿，他該怎么分配呢东抹？

如果沒有自己，老二可以得到95枚沃测，所以老二直接放棄掉缭黔。

剩余6個海盜時，老三得不到金幣蒂破，所以給老三一枚就可以拉攏馏谨，很好伺候。

剩余6個海盜時附迷，老四的收益是1枚惧互，老五、老六喇伯、老七的平均收益是1.33枚喊儡，但無論1枚還是1.33枚，給他們兩枚金幣都是可以拉攏的稻据。我們只要拉攏其中兩人就行艾猜，所以其中兩人沒有金幣，另外兩人各自給兩枚。這樣又形成了一個排列組合：

2匆赃， 2淤毛， 0，?0

2炸庞， 0， 2荚斯，?0

2埠居， 0， 0事期， 2

0滥壕， 2， 2兽泣，?0

0绎橘， 2， 0唠倦， 2

0称鳞， 0， 2稠鼻， 2

因此冈止，老一自己保留的金幣數(shù)量是 100 - 2 - 2 - 1 =95。完整的分配方案有6種候齿，比較復(fù)雜熙暴，這里就不用圖片表示了，直接列出表格：

喜歡本文的朋友們慌盯，歡迎關(guān)注公眾程序員小灰周霉，收看更多精彩內(nèi)容

渴望知識交流和學習的小伙伴們，也歡迎加入小灰的知識星球