海盗分金

海盗分金问题的结题步骤和对于该问题的推广探索

前言

昨日闲暇饭后之余和一众老友谈论到宇宙，外星人。又从外星人话题扯到了博弈论。于是老生常谈，我还是出了那道最经典的海盗分金问题供大家饭后消遣。

问题描述

假设在一艘船上有5名海盗，并偶然间得到了100枚金币，现在要按照顺序，每名海盗提出一种具体的分配金币的意见（具体到每一个人应分得多少枚金币），由在场所有海盗（包括自己）进行表决，若大于一半的人认可此方案，方案通过，否则，此海盗将被扔入大海。，但是这五名海盗有着自己的生存秩序，分别排列成了“老大”，“老二”，“老三”，“老四”，“老五”（相应的他们的地位也是这样排序，老大先提方案，然后老二，老三等等）。假设每名海盗都是经济学假定的“理性人”，即绝顶聪明，能充分考虑到每一种情况而进行每次的判断，在投票过程中海盗们不能交流，且它们都遵守此规则问第一名海盗应该怎样提出分配方案，才能使自己的方案通过且自身利益最大化？

推导

解决此类问题最好的办法就是用倒推法，其中我认为包含了一种递归的思想

• step 1

当只有最后两名海盗，绰号分别是老四老五的时候（其他三个估计已经死了）。此时，会出现一种情况，就是老四提任何方案，都已经可以无视老五的选择，因为始终他自己会有1票同意，达到50%

所以此时，老四的方案一定是自己100枚金币，老五0个，此时无论老五如何投反对票，都不会影响方案。

得出结论：(n=2)——>(100,0)

• step 2

如果此时老三在场的话，会如何决策呢？老四首先不论如何都不会同意老三的方案，并且希望老三赶紧死，然后自己就可以独吞这100个金币。所以老三如果想要票数超过50%，那在3个人中，除了自己一定要争取到1票，所以他只要给老五1个金币，老五就会无条件的支持他（因为老五也是聪明人，如果老五不同意，老三死了之后，又回到了老四的方案，在老四的方案中他一个金币都得不到）。

得出结论：(n=3)———>(99,0,1)

• step 3

同以上的推论，老二的方案中老三也是无论如何都要投反对票的，而且老二需要争取到另外1票就可以了。所以，此时老二给了上一轮在老三的方案中一无所有的老四一枚金币，这样老四就会支持他了。（老四的视角中，如果到了老三的方案他将一无所有，所以老二只需给他1个金币就可以成功收买）
得出结论：（n=4）——>(99,0,1,0)

• step 4

推理同上，老大需要3票支持，出去自己1票，还需要争取2票同意。所以容易得知，老二无论如何争取不到，只需要争取在老二的方案中一无所获的老三和老五就可以了，分别给1个金币就ok。
得出结论：（n=5）——>(98,0,1,0,1)

扩展

若此时有10名海盗参与投票分赃，推理过程略，思想都一样，如下图所示具体的方案

海盗数量	海盗1	海盗2	海盗3	海盗4	海盗5	海盗6	海盗7	海盗8	海盗9	海盗10
n=1										100
n=2									100	0
n=3								99	0	1
n=4							99	0	1	0
n=5						98	0	1	0	1
n=6					98	0	1	0	1	0
n=7				97	0	1	0	1	0	1
n=8			97	0	1	0	1	0	1	0
n=9		96	0	1	0	1	0	1	0	1
n=10	96	0	1	0	1	0	1	0	1	0

经过推理得出以上10名海盗的分金币情况，进一步抽象后，可以得出人数n和第一名海盗金币个数的表格

海盗数量	1	2	3	4	5	6	7	8	9	10
第一名金币数量	100	100	99	99	98	98	97	97	96	96

通项公式：X = 101 - [(n+1)/2]
n为海盗数量，X为当前提方案海盗应该得到的金币数，[]为取整运算

讨论

已知通项公式 X = 101 - [(n+1)/2]
当X=0时，n值为201,202，那么以上X,n所代表的意义是什么？
可以这么理解，当有201个海盗的时候，第一个海盗提的方案，就是自己拿的金币数为0（为了保命），剩下的100枚金币全部用于贿赂那些相隔一位的海盗。

得出如下总结：

• 当n=201及n=202时，201号/202号海盗的最大化收益为0，但可保命。
• 当n=203时，203号海盗必须获得102张赞成票，但他无法用100个宝石收买到101名同伙的支持。因此，无论203号提出什么样的分配方案，他都注定会被扔到海里去喂鱼。
• 当n=204时，204号海盗必须获得102张赞成票，203号为了能保住性命，就必须让204号的方案通过，避免由203号自己来提出分配方案，所以无论204号海盗提出什么样的方案，都可以得到203号的坚定支持。这样204号海盗就可以保命：他可以得到他自己的1票、203号的1票、以及用100个宝石收买到的100名同伙的赞成票，刚好达到所需的半数支持。能从204号那里获得1个宝石的海盗，必属于按照202号海盗的方案将一无所获的那102名海盗之列。
• 当n=205时，205号海盗必须获得103张赞成票，但他无法用100个宝石收买到102名同伙的支持。因此，无论205提出什么样的分配方案，他都注定会被扔到海里去喂鱼。
• 当n=206时，206号海盗必须获得103张赞成票，他可以得到205号的坚定支持，但他无法用100个宝石收买到101名同伙的支持。因此，无论206号提出什么样的分配方案，他都注定会被扔到海里去喂鱼。
• 当n=207时，207号海盗必须获得104张赞成票，他可以得到205号和206号的坚定支持，但他无法用100个宝石收买到101名同伙的支持。因此，无论207号提出什么样的分配方案，他都注定会被扔到海里去喂鱼。
• 当n=208时，208号海盗必须获得104张赞成票，他可以得到205号、206号、207号的坚定支持，加上他自己1票以及收买的100票，使他得以保命。从208号那里获得1个宝石的海盗，必属于那些按照204号方案将一无所获的那104名海盗之列。

眼下可以看出一条新的、此后将一直有效的规律：

那些方案能通过的海盗（他们的分配方案全都是把宝石用来收买100名同伙，自己连1个宝石都得不到）相隔的距离越来越远，而在他们之间的海盗则无论提出什么样的方案都会被扔进海里。因此，为了保命，他们必会投票支持排在他们前面的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、204、208、216、232、264、328、456号，
即200+1、200+2、200+4、200+8、200+16、200+32、200+64、200+128、200+256。即
200+2的0次幂，200+2的1次幂，200+2的2次幂，200+2的3次幂，200+2的4次幂，200+2的5次幂，200+2的6次幂，200+2的7次幂，200+2的8次幂，
即其号码等于200加2的某次幂。

未完

目前只探讨了，对于海盗人数是发散的讨论，并没有对于金币数和海盗人数同时讨论的情况，当海盗人数和金币数都为变量时，则可以画出一个函数图像，有时间会继续思考，就到这里了。