基于遞推關系的海盜分金幣數學模型的后續研究

(重慶交通大學 重慶 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