基于递推关系的海盗分金币数学模型的后续研究

(重庆交通大学 重庆 400074)

一、引言

有这样一个问题：5个海盗抢得100枚金币，他们按抽签的顺序依次提方案：首先由1号提出分配方案，然后5人表决，不少于半数同意方案才被通过，否则他将被扔入大海喂鲨鱼，依此类推。假定“每个海盗都是绝顶聪明的、凶残的、贪婪的”，那么“第一个海盗提出怎样的分配方案才能够活下来并使自己的收益最大化？”

采用简单的博弈论与递推关系模型即可得出结论：1号海盗能活下来，他分给3号1枚金币，分给5号海盗1枚，自己独得98枚[4]。

然而当上述问题中的海盗和金币数取足够大时，问题会变得十分复杂，常规方法已不适用。因此，通过建立数学模型求解此问题是十分必要的。

本文就海盗和金币数量较大，并且海盗数大于金币数的情况下，对“海盗分金币”的拓展模型进行了求解。拓展问题如下：

有n个海盗，按凶狠程度排名老大、老二……老n，他们抢来m个金币(n>m，且n足够大)。现在老大提出一种分配方案，然后大家投票，如果有不少于50%的人支持，就按照他提出的方案分。否则，将老大扔下海(下海即被鲨鱼吃掉)，由老二来分，依此类推。

其中，海盗都是绝顶聪明的(任何一种情况大家都能想到)，是凶残的(在利益相同的情况下没有人情味)，是贪婪的(在条件允许下，谁给的利益多就支持谁，并使自身利益最大化)。问：当n,m为任意正整数时,最多有多少海盗能活下来？

二、模型的建立与求解

(一)问题分析

当海盗和金币的数量不大时，通过分析发现在某些情况下必存在一个海盗，无论怎样分配金币都不能使自己活下来。基于海盗是绝对聪明的，可假设一种情况：某些海盗可以利用“组团”的方法活下来，即后面的某些海盗通过与其前面的部分海盗进行“联合”便能活下来。故以此假设为切入点，通过一定方法计算进行“组团”方式活下来的海盗数量，进而求得可以活下来的海盗总数。

有这样的规律：第奇数个海盗d后面的海盗总数为偶数(包括海盗d)，第偶数个海盗c后面的海盗总数为奇数(同上)。如果有奇数个海盗(计为λ)来“分赃”(λ：进行“分赃”的海盗总数)，则分配金币的海盗要活下来，至少需要拿出0.5(λ-1)个金币来贿赂后面的海盗才能使支持率满足要求，但海盗是贪婪的，故他只会拿出0.5(λ-1)个金币，即每个海盗只分1个金币。

如果有偶数个海盗(计为(λ+1))来“分赃”，则分配金币的海盗要能活下来，至少需拿出0.5(λ+1)-1个金币来贿赂后面的海盗即可使支持率符合要求，可海盗是贪婪的，他也仅会拿出0.5(λ+1)-1个金币，即每个海盗只分1个金币。

因此有结论1：第奇数个海盗和第偶数个海盗在能活下来的前提下，都只会拿出0.5(λ-1)个金币给后面的海盗。

受递推关系模型启发，本文从倒数第三个海盗起进行分析。

(二)“组团”海盗数量的分析与计算

1.海盗数量为偶数

假设海盗人数n取偶数，对第奇数个海盗和第偶数个海盗进行“配对”(奇数在前，偶数在后)，如第n-3、n-2个海盗组合在一起，第n-5、n-4个海盗组合，依次类推(本文所述的‘第几个海盗’均为按正序排列，例如：n-3

一共有m个金币，并且金币数少于海盗数，假设第ω个海盗成为第一个需采取与前面的海盗“组团”的方式才能活下来的人。可以看出直接找出这个人不容易，为此采用间接方式：

记第ω海盗的后面一个海盗为第η个海盗(η=ω+1)，η必定也是无法获得金币的。假设海盗η能分到金币，那么意味着第ω海盗依然可以通过分配金币的形式活下来，而无需合作，这与假设矛盾，故第η个海盗不能拿到金币。

按照上文所述的“配对”的方法和结论1，可得结论2：海盗η必定是第奇数个海盗。

故此时由偶数个海盗来分赃，则有：

0.5[(n-η)+1]-1=m

得：η=n-(2m+1)

ω=n-(2m+2)

因此从第n-(2m+2)个海盗开始实行“组团”策略。

2.海盗数量为奇数

假设海盗人数n取奇数(n足够大)，则第奇数个海盗a后面的海盗总数为奇数(包括海盗a)，第偶数个海盗b后面的海盗总数为偶数(包括海盗b)。

从后往前，依旧从倒数第三个海盗开始分析，对第偶数个海盗和第奇数个海盗开始“配对”(奇数在前，偶数在后)，如第个n-3、n-2海盗组合在一起，第n-5、n-4个海盗组合……

易知，人数为奇数或偶数的“分赃”情况是相同的。经计算，仍然是从第η=n-(2m+2)个海盗开始“组团”。

综上，在海盗数、金币数为任意正整数n、m时(n>m)，第一个需要发起“组团”才能活下来的是第n-(2m+2)个海盗。可以看出当n≤2m+1时，不存在“组团”的必要，此时全部海盗都能活下来。下文仅讨论n≥2m+2的情况。

(三)模型求解

确定第一个发起采取“组团”策略的海盗后，再来确定其需要联合多少海盗。下文所用未知数含义如下。

xi+1(i=1，2，3……)：从后往前，第i次组团成功后能活下来的海盗总数；

n-xi：第i次组团时，这个团体中等级最高的海盗；

ki(i=1,2,3……n)：提出“组团”的海盗所需联合的其他海盗的数量；

ki+1：第i个团体的总人数；

假设第n-(2m+2)个海盗联合了从第n-x1个海盗起的k1+1个海盗，则有(n-(2m+2))-(n-x1)=k1,化简得:

x1=k1+2+2m

(1)

为使支持率更容易满足要求，所以m个金币均分给后面合适的海盗[4]。由支持率不小于一半的条件得：因海盗是凶残而无人情味的，得：

2(m+k+1)≥x1+1

(2)

联解(1)、(2)得：ki=1

再看第n-(x1+1)个海盗，假设其联合了从第n-x2个海盗开始的k2+1个海盗。所以(n-(x1+1))-(n-x2)=k2

化简得

x2=k2+x1+1

(3)

再结合(1)、(3)得：k2=x1-2m=3

(4)

余下的海盗按照上面同样的方法进行“组团”，直至在固定的海盗人数的限制条件下，找不到足够的需要联合的人数ki。

利用ki与xi的关系得：

ki=k1+k2+…+ki-1+2+i-2

(5)

xi=k1+k2+……+ki+2+2m+i-1

(6)

采用求解数列递推公式的方法计算(5)、(6),得：

ki=2i-1

(7)

xi=2i+1+2m-1

(8)

停止“组团”的条件为：第n-(xi+1)个海盗前面的人数不足ki+1，这时从第n-xi个海盗之后的所有海盗都能活下来。由(7)、(8)得：

n-(xi+2)

解得：

i=log2(n-2m)-2，且i∈Z+

所以

i=[log2(n-2m)]-1，“[]”代表取整

活下来的海盗数h最多为：

h=xi+1=2i+1+2m，i=[log2(n-2m)]-1

三、结论

设海盗数与金币数分别为n，m；支持率要求大于或等于50%时，活下来的海盗最多为：

[1]白岛.写给中国人的经济学[M].北京：中国华侨出版社，2011.

[2]谢识予.经济博弈论[M].上海：复旦大学出版社，2002.

[3]Alan Tucher.应用组合数学[M].北京：人民邮电出版社，2009

[4]Stewart Ian.A Puzzle for Pirates[J].Scientific American,1999,280(5):98-99

[5]姜启源.数学模型第四版[M].北京：高等教育出版社，2011