5A版学生建模报告-海盗分赃问题

1、7A 版优质实用文档 海盗分赃问题 一 . 问题重述： 从前 ,在一个小岛上有一伙海盗（共 5 人），他们刚刚从来往的运金船上抢得了一 批金砖，经点算共计 1000 块。有一个狡猾的海盗建议， 不采取平均分配的原则， 而是将 5 个人按照一种次序，依次提出分赃方法，如果第一个人提出的方法有 半数或半数以上的人同意（包括提议人自己） ，则大家就按他的方法分配，否则 就把他干掉， 由下一个人继续提出方法； 依次类推。前提是这些海盗都非常贪婪 和精明，能够多得到一块就不会拱手让给别人， 可是他们又很重江湖规矩， 一旦 决定了分配方法就会按照它执行，不会采用任何非常手段抢夺。到底如何分配， 既可以保存

2、自己生命，又可以获得尽可能多的财宝？ 2.模型假设：五名海盗编号，分别为 A,B,C,D,E; 3.模型求解：整个过程可以归纳为下表： E 1000 0 1 0 1 D / 1000 0 1 0 C / / 999 0 1 B / / / 999 0 A / / / / 998 从本题中可以看出， 在讨论编号次序时， 如何将自己放在首位将直接决定所分得 的黄金数量。 4模型进一步思考： （1）.当只在半数以上（不含半数）讨论该问题时，哪个位置是最好的？ （ 2） .当金块数量为 3 ，人数为 6 时，哪个位置是最占便宜的？ 5问题的延伸： 7A 版优质实用文档 7A 版优质实用文档 从问题中我

3、们可以看出， 在这个问题中， 强盗们在同意该提议时， 则最后的分配 结果，在某种意义上说，是绝对公平的。但是，因为他们都很聪明，所以第一个 位置的争夺将是无休止的， 也就是说这个问题是无结果的。 再者，我们可以把金 块等同于其他有待分配的实体。 显然，只有给每个人赋予一定的权值求解该问题 才是有意义的。 故运用席位分配问题来代替它，以给出某种较公平的分配方法。 6说明： 设第 i 方人数为 pi ，i=1,2, 总m,人z数 p= pi待分配的席位为 N,理想化的席 位分配结果为 Ni, 满足 N= Ni 。记 qi=N pi/p, 显然q若i,均为整数，则应有 Ni=qi. 以下研究 qi

4、不全为整数的情形 . Ni 是 N 和 pi 的函数，记 Ni=Ni(N,p1, pm), 分qi别向为下取整和向上取整， 则公平分配方法的理想化原则为： 原则一： qi- Ni qi+,i=1,2,Ni 必m取, 即qi-,qi+ 二者之一。 原则二 :Ni(N,p1, pm) Ni(N+1,p1, pm),i=1,2, mN,i即总席位增加时 不应减少。 声明：我们的初衷是为了迎合这两个原则去选择一种方案 ,而不是构造出某种方 法后再去验证它是否满足它们。 我们不得不承认我们的出发点是卑鄙的， 甚至是 下流的。但是正是在这种思想的指引下， 在选择方案的过程中， 我们欣喜地发现， 我们得到的

5、却是最最振奋人心的结果， 换句话说， 我们把满足这两条原则的所有 分配方案都找到了。我们不妨把这种方法命名为 H.W.L 方法。它不仅满足这两 条原则而且给出了一个非常明确的数量指标。 因此，从某种意义上说， 席位分配 问题获得了圆满的解决。 我们可以大胆的说， 如果它能够得到大家的认可， 那么 我们现在使用的数学模型 (第三版)的下一版就应该有所修正，确切地说应 该是改正了。 7A 版优质实用文档 7A 版优质实用文档 H.W.L 方法简介： 设总人数为 N，组数为 W,各组人数为 n;待分配的席位为 M 。为了满足上述两条 原则。我们可以这样来选择分配方案：当待分配席位数 M 确定后，则每

6、组最理 想的分配席位数分别为 niM/N 。我们来讨论前式含非整数的情况。无妨设前式 的小数部分的和为 T。显然 0=TW ，我们只须选其中 T 个向上取整即可。当 待分配席位数为 M+1 时，我们从上向下取整的一个组加上一个席位且满足原则 一。(我们若得不到，则只须调整上步总可得到)但是现在总席位数为 M1 的 分配方案是否满足原则二是有待考证的。 所以我们无妨采用倒推法。 从总席位数 等于总人数 N 一直往下推，按上述方法的逆方法，则原则二显然满足了，我们 只须给出一条法则，以保证它满足原则一即可。如下表所示： 分组 总人数 次数 1 2 3 4 5 席位 20GG 1999 1998 1

7、997 1996 1995 1 1100 1099.45 1098.9 1098.35 1097.8 1097.25 2 700 699.65 699.3 698.95 698.6 698.25 3 100 99.95 99.9 99.85 99.8 99.75 说明：我们的组是按照大小变化来排列的， 从上表中容易得出每一行都是等差数 列，而且每组的人数越多，公差越大，也就是总席位每减少一个，则从这一组减 少一个席位的几率越大。 考察 ni M/N每减少 k 个席位。即 M 减 k 时，前式就变为(ni- ni M k)/N我 们记 ni M/-N,ni M/N+ 分别为向,下向上取整。现在我

8、们将 ki依次取 1，2， 3 , 一直到 (ni -niMk)/N=ni -M-1/N为 止，并记下 ki 这样我们按 ki 从小 7A 版优质实用文档 7A 版优质实用文档 到大的顺序将 W 个 ni M/N排了个序。我们按这样的顺序依次取 W-T 个组， 并将它们向下取整，其余 T 组向上取整这就是 H.W.L 方法的核心内容。它相当 于引入了另一个相对不公平度的概念。 现在我们来证明这种方法是可行的。 我们 只须举出可能的不可行的情形， 并将它们一一否定即可。 显然只有一种可能， 即 M 个 席 位 分 配 后 ， 当 减 少 一 个 席 位 时 ， 出 现 两 个 以 上 (ni -

9、Mni k)/N-=ni M/N-1 ，而在上一步分配 M 个席位时我们却取了它 们的上界。我们来证明在上述法则的前提下，这种情形是完全可以避免的。 因为是这样， 我们总有其他取下界的组， 而当 M-1 时它们的整数部分是不变的， 而按我们的法则， 我们早在 M 之前应该取 (ni -ni M k)/N的下界而非上界。 证 毕。 说明： 1.如果我们按向上取的方法， 也可以得解，无妨称之为 H.W.L 逆法则。只不过结 果却是迥异的，大家可以一试。 2.以这种方法为基础，我们可以得到满足原则一和原则二的所有分配方案。 据我 们粗略的估计，当组数为 4，各组人数相差不是很悬殊的情况下，我们可以得到 一组斐波那契数列，并从第三项开始对其求和。即： 235813213455 +an( 第n 项); 我们没有得到它的通式，但是它至少比 n2 阶要大很多。 3.如上所述，这一法则的意义不仅在于对任一分配问题找到了一个较满意的分配 方案，我们其实还可以把它作为一个定常轨道， 把其它一切有待考证的方法纳入 其中。 例：不妨设按 Q 值法把 M 个席位分配完毕，如果与我们的方法不同，则依原则 一，原则二向上，下依次加减 N/ni 个席位( ni 指人数最少的那个组的