海盗分金问题

但凡对趣味数学有兴趣或者接触过数学竞赛的童鞋们很可能听过这个问题。这个问题大约就是m个海盗,编号1-m,从第m个开始,对一些财宝提出分配方案,然后对方案进行表决,通过就分,通不过就把第m个海盗杀掉,让第m-1个海盗分,以此类推。假设所有海盗都极端理智,你是最后一个海盗,你该怎么提出方案才能保命并且收益最高?

大约我就记得这么个规则,然后有些细则记不大清楚了,这样容易出现多重解,于是就又自己加了一些细则(不过加了还是会有多重解,但是没有更合理的细则可以加了):

1.表决方式是过半同意方可通过,即2m个海盗中必须有m+1个同意方可通过

2.海盗们很腹黑,收益不变的情况下总是希望看到死人

3.财宝有相等的n份,这个n足够大

很明显这是个需要递推的问题,设第m个海盗为Am,我们从2个人开始研究,很明显2个人的时候无解,因为腹黑假设,A2即使把财宝全数送上也无法保命;3个海盗的时候,利用第A2的这种心理,A3大可以全吞所有财宝,因为A2无论如何都不能进行到2人表决。于是分配方案可写为

0,0,n

A4除了自己之外还需要争取2票,A3欲壑难填因而果断放弃,只要能让A1A2收入比三人的情况有所增加即可,于是给他们各一份,方案为

1,1,0,n-2

A5需要争取的也是两票,除非砸下血本(n-1份),否则拉拢A4无异于天方夜谭。于是放弃A4,A3只需要1份财宝即可拉拢,A1和A2中挑一个拉拢就行了(所以多重解了),方案为

2,0,1,0,n-3

0,2,1,0,n-3

A1A2都有可能得到2份,所以他们的行为很难预测,但是原则上说只要A6在方案中给他们稳定的2份,就必然得到支持,俗话说,a bird in the hand is better two in the bush,何况是两只鸟,作为A6,要获得3人支持,当然不可能去拉拢A5,A4是0个只需要1个即可拉拢,拉拢A3需要2个,拉拢A1A2都只需要2个。于是又是一个多重解。

0,2,2,1,0,n-5

2,0,2,1,0,n-5

2,2,0,1,0,n-5

大约就是这样可以分析到银河的尽头,我也懒的做了,但是以这个简单的数学模型去理解一些事情,你会发现无比精准:

为什么共产党要“依靠贫农,联合中农,限制富农,剥夺地主财产”,贫农(方案中得0份财宝的)非常易于收买,地主(Am-1)完全无法收买只能完全剥夺财产。用这个理解土地革命非常简单易懂。革命者要做的就是提出一个革命方案,分配利益,得到足够多人支持就可以推翻即得利益者了。这个高度抽象而有趣的数学模型让我进一步厌恶起了革命,对暴力的无所谓的应用很有可能制造的是下一个暴君。即得利益者被剥夺权力后其财产如果也被立刻剥夺,很有可能造就的就是另一群即得利益者,所以财富的平均只能是一个渐进的过程才能保证有序,这是俄罗斯正在发生的,也是中国终有一天要面对的。

当然我想说的其实已经说完了,严谨期间把通解做出来了:最末尾三个人的分配方案必须为1,0,X,其中X为收买人心之余的所有财宝。这个很好理解,地主要打击,贫农要依靠,利益要独占,很简单,很简单。前面的需要至少拿到一半的票,可以证明前面的那些人完全没有区别,都是收买要且仅要2份财宝的,可以随便选一些人收买。用数学归纳法证明,显然对于m=5是成立的,设m个海盗时成立,在m+1个海盗时,后三位如前所述是1,0,X,还需要一半以上的票,剩下的这个人包括m个海盗时的那个随机的多重态,这部分海盗收益的期望要么等于1(m-3为偶数),要么略大于1(m-3为奇数),再加上m个海盗时Am-2那个1,在m+1个海盗时收买起来都是要且仅要2份的(1份不够,由腹黑假定),这m-2个海盗也需要收买1半以上,证明完毕。之后可以计算出m个人总共需要的安抚份数是[m-2]+1份,[]为下取整符号,要是总共财宝不能分成这么多份,那么第m个海盗就死定了,能分的话,除了这些财宝有多少就能拿多少。还有我的前两个假定改一下解也会变,首先是腹黑假定一改就会产生平庸解——所有财宝集中于分配者,m=3成立,m个海盗成立时m+1个海盗不满于分配条件的只有第m个海盗,他的利益受到了损害,其他人都抱着事不关己的态度同意的话Am+1也可以侵吞所有财宝。至于表决时不需要超过一半只需要达到一半,即2x个人只要有x个同意即可,那么得出的解为一个很简单的;

0,X

1,0,X

0,1,0,X

1,0,1,0,X

0,1,0,1,0,X

以此类推,像国际象棋盘一样01交错即可