海盗与金子

shshsh_0510

海盗与金子的问题老掉牙了，比如 http://bbs.emath.ac.cn/thread-505-1-1.html 就有
今天翻看几年前的纪录，当初考虑过一个变形的，不算难但是当初不会（说明这几年俺有提高哦 ），给大家解解闷：

将原题海盗一半或以上同意 改为 “一半以上同意 ” ，也就是说刚好一半不行，那么100个金币，1-500个海盗，结果如何呢？

zgg___

海盗分金问题在出题时应该明确的规定海盗如何判断自己所得利益的大小，而这个往往题目中没有严格的说明，或许是因为不容易说清楚吧。呵呵。

假设说海盗的价值观如下：
1、最重要的是保命；
2、其次是多得金币；
3、再次是多死人。

那么，比如说某个海盗面对一次投票。如果分法通过，那么他将得到一个金币；如果分法不通过，那么他将有一半的机会得到2个金币，一半的机会什么也得不到，（假设还有多死一个人的附加利益）；那么他会如何投票呢？是严格按照概率，还是“二鸟在林，不如一鸟在手”呢？

shshsh_0510

严格按照概率

zgg___

编程模拟了一下。呵呵。

1. /**
   
2. 已知n时的分配方案（int n,k,kn,a[n];）：第i号得到a的金币（i为从1到n）；其中如果a==-1，表示从他们kn个中间随机选出k个，给kx个金币，其它kn-k个不给；
   
3. 如果a==-2，表示他必死。
   
4. 归纳信息（int n,b[n],c[101];）：b为海盗可以被诱惑的金币数；c为b的统计数目。
   
5. 当有n+1个海盗时，第n+1号海盗的方案分析如下：
   
6. 我必须要得到除我之外的[(n+1)/2]票，我根据c，计算我要付出的成本t；如果t<=100，那么余下的归我，如果t>100，我去死，其余的按照原有方案进行；n++;goto start;。
   
7. **/
   
8. #include "stdafx.h"
   
9. #include <conio.h>
   
10. #define N 500
    
11. #define M 100
    
12. int n,k,kn,kx,a[N+3],b[N+3],c[M+3];
    
13. int show()
    
14. {
    
15.         int i;
    
16.         printf("有%d个海盗时的分配方案：\n",n);
    
17.         for(i=0;i<n;i++)
    
18.         {
    
19.                 if(a==-1)printf("第%d号必死，",i+1);
    
20.                 else if(a==-2);//printf("第%d号得到金币数是随机的，",i+1);
    
21.                 else printf("第%d号得到%d个金币，",i+1,a);
    
22.         }
    
23.         if(kn==0)printf("就这样方案是固定的。");
    
24.         else printf("其余的%d个海盗中随机挑出%d个给与%d个金币（期望值是%d）。",kn,k,kx,k*kx/kn+1);
    
25.         printf("\n\n");
    
26.         return 0;
    
27. }
    
28. int _tmain(int argc, _TCHAR* argv[])
    
29. {
    
30.         int i,t,p;
    
31.         a[0]=M;kn=0;
    
32.         for(n=1;n<=N;n++)
    
33.         {
    
34.                 show();
    
35. //                printf("%d,",a[n-1]);
    
36.                 _getch();
    
37.                 for(i=0;i<M;i++)c=0;
    
38.                 if(kn>0)t=k*kx/kn+1;
    
39.                 for(i=0;i<n;i++)
    
40.                 {
    
41.                         if(a==-2)b=t;else b=a+1;
    
42.                         c[b]++;
    
43.                 }
    
44. 
    
45.                 p=(n+1)/2;t=M;
    
46.                 for(i=0;i<M+2;i++)
    
47.                 {
    
48.                         if(p<=c)break;
    
49.                         p-=c;
    
50.                         t-=i*c;
    
51.                         if(t<0)break;
    
52.                 }
    
53.                 if(t<p*i)a[n]=-1;
    
54.                 else if(p==c)
    
55.                 {
    
56.                         a[n]=t-p*i;
    
57.                         kx=i;
    
58.                         kn=0;
    
59.                         for(i=0;i<n;i++)
    
60.                         {
    
61.                                 if(b<=kx)a=b;
    
62.                                 else a=0;
    
63.                         }
    
64.                 }
    
65.                 else
    
66.                 {
    
67.                         a[n]=t-p*i;
    
68.                         kx=i;
    
69.                         k=p;
    
70.                         kn=c;
    
71.                         for(i=0;i<n;i++)
    
72.                         {
    
73.                                 if(b<kx)a=b;
    
74.                                 else if(b==kx)a=-2;
    
75.                                 else a=0;
    
76.                         }
    
77.                 }
    
78.         }
    
79.         printf("---------------End---------------\n");
    
80.         _getch();
    
81.         return 0;
    
82. }
    

复制代码

shshsh_0510

编译不过

mathe

假设N个海盗编号为1..N,每次从第N号海盗开始分配，如果失败再N-1号分配，每个海盗策略如zgg__
然后如果存在金币数目随机分配的可能，以期望为标准
先假设总金币数目足够多
只有一个海盗，他拿走所有的金币

两个海盗，2号必死；1号海盗拿走所有的金币。
三个海盗，3号海盗拿走所有的，因为2号海盗必然支持（根据两个海盗的结论）
而四个海盗的时候，4号无论怎么分配，3号海盗必然反对，所以4号海盗必须争取到1号和2号，所以各给它们一个金币就可以了。
也就是4号需要两个金币贿赂1号和2号，自己留下余下的金币。
而五个海盗时，5号海盗的分配4号海盗必然反对，3号需要一枚金币贿赂就可以支持，但是1号或2号都需要2个金币才能够贿赂
   所以5号需要提供3个金币，1个贿赂3号，2个贿赂1号或2号。即1号，2号和3号拿到金币的期望值都为1个金币。4号为0.
于是六个海盗时，6号海盗的分配必然被5号反对，而4号只要1个金币就可以贿赂，1~3号都需要2个金币才可以贿赂，6号还需要争取它们中间的两个，所以需要额外提供4个金币，即总共提供5个金币贿赂他人。其中5号0，4号1，1~3号4/3
于是七个海盗时，6号反对，5号需要1个金币来贿赂,1~4号需要2个金币贿赂，总共需要另外争取3个名额，所以付出5个金币争取了5号和1~4号中的2人，其中6号期望为0，1~5号期望为1个金币.
...
于是2k个海盗时,2k-1号反对，2k-2号只需要1个金币来贿赂,1~2k-3号需要选择k-1个人各用两个金币贿赂，所以2k号海盗需要有1+2(k-1)=2k-1个金币来贿赂他人。其中2k-1号期望为0,2k-2号期望值为1个金币，1~2k-3的期望值为${2k-2}/{2k-3}$
于是2k+1个海盗时,2k号反对，2k-1号只需要1个金币来贿赂,1~2k-2号可以选择k-1个人各用两个金币来贿赂，所以2k+1号海盗需要2k-1个金币贿赂他人。其中2k号期望为0,1~2k-1号期望为1个金币。

mathe

我们现在知道如果2k个或2k+1个海盗的时候，编号最大的海盗都需要提供2k-1个金币来贿赂其他人。
所以现在如果出现2k-1>M，其中M是总金币数目，那就开始出现问题了。
比如现在M=100,那么100个海盗的时候还好，第100号海盗自己号可以留下1个金币
而101个海盗的情况出现变化了，因为这个时候101号还是只要1个金币就可以贿赂99号，但是2个金币除了可以贿赂1~98号，也可以贿赂100号，也就是说,101号贿赂的候选对象多了一人，这个导致1~98号和100号的期望收入为$98/99<1$了，
这个给102个海盗带来了机会，他只需要花一个金币就可以贿赂1~98号或100号中的任何人，而他收买51个人就可以了，所以他们的期望收入都只有$51/99$。
而103个海盗，只需要一个金币可以收买1~101中任何一个人，同样他需要收买51个人，他们期望收入为$51/101$
...
2k或2k+1(2k>=104)个海盗的时候,分配者需要花费k个金币另外收买k个人，自己可以拿到余下的钱，而那些海盗的收入期望都分别为$k/{2k-2}$或$k/{2k-1}$

mathe

在海盗数目为199的时候，199号海盗很幸运的花费了99个金币收买到了99个人的支持，自己还可以留下一个金币。
200号海盗只能将100个金币都拿出去收买到出199号以外的100个人的金币而可以幸免于难。
但是201号海盗的命运就没有这么号了，他没有足够的金币收买他人的支持，所以只有黄泉一条路了。
202号海盗比201号幸运一些，至少他可以得到201号的支持，然后散尽钱财可以保留一条小命。
但是203号和204号都没有足够的资本来逃命，但是它们给205号提供了2票，所以205号可以逃命。
而后面的趋势我们现在基本可以看出来了，后面分配者都肯定无法得到任何金币，而他们能够逃命的编号分别为
200,202,205,211,223,...
其中a(n+1)为满足x-a(n)+100>x/2的最小整数，即a(n+1)=2a(n)-199

shshsh_0510

忘了注明不让math回答了

无心人

对

任何简单问题都不能让肚子参加
肚子太厉害
简单问题他/她一掺和就无趣了
呵呵