海盗分金问题分析与解决
海盗分金问题分析与解决
——Nim取子问题变形后的解决方案
全文下载链接：海盗分金问题分析与解决.pdf
Author: Zealot Ke(kejie[at]kuxun.cn)
Date: 2010/7/30
背景
强哥邮件发出一个题目
- 有5个海盗,特别的残忍,特别的聪明
- 他们抢了100个金币,要进行分配,每个人都想分配足够多的金币,他们寸步不让.分配顺序是:5号海盗->4号海盗…1号海盗,即是:先由5号海盗决定如何分配,若分配不均,5号被扔下海,4号海盗再决定如何分配,依次类推.
- 如果没有二分之一或以上的海盗同意,分配人将被其他人扔下大海.
- 假如你是5号海盗,你会如何分配金币.确保自己不会被扔下大海,而且让其他4个海盗心服口服.
定义问题
5号海盗必须按照上述规则，找出最优分配方案，否则将被其他人扔下大海。
当前状态
正确分配方案还没出来，必须尽快找出最优解。
分析
典型的nim取子问题的变形，采用倒推方式即可找到最优解。
制定解决方案
倒推方法如下所示
- 如果只有一个海盗，如何分配？
- 如果有两个海盗，如何分配？
- 如果有n个海盗，每个海盗至少需要几个人同意？找出n-1个海盗情况下的分配方案中，需要收买多少海盗？最低需要多少金币？
实现解决方案
倒推方法实现如下表所示，每一行表示一种人数情况下的分配方案，也即，最后一行给出5号海盗的分配方案。
分配方案倒推分析表
注意：从表中可以看出聪明是大前提，当然残忍也是。nim取子游戏向来是君子游戏，没有这个前提的话，后面的海盗不按套路出牌就不可能有最优解。
标准化解决方案
从上表不难看出规律，也即，自己拿尽可能多的金币，同时保证后面的人依次分配0、1交错的金币数。规范化命题如下
*命题: 假设对于n个聪明、残忍的海盗（n≥1），抢了Gold个金币，要进行分配，每个人都想分配足够多的金币，他们寸步不让。分配顺序是：n号海盗->n-1号海盗…1号海盗，即是：先由n号海盗决定如何分配，若分配不均，n号被扔下海，n-1号海盗再决定如何分配，依次类推。在该规则下，n号海盗最佳分配方案应当如此（为简单，避免使用地板函数，按n为奇偶数分类讨论）：
不妨假设ones为得到1个金币海盗数，zeros为得到0个金币的海盗数。
- 当n为奇数时，ones=zeros=(n-1)/2，分配方案为Gold-ones,0,1…0,1
- 当n为偶数时，ones=( n-2)/2,zeros=n/2，分配方案为Gold-ones,0,1…1,0
该命题从上述分析中的规律中得出，不是定理，更不是公理，作为标准化解决方案需要严格证明。
证明：
注释：使用跳跃数学归纳法证明，跳跃的step为2。
先证明n为奇数时命题是否成立。
当n=1时，显然该命题成立
假设当n=m(m>1)时命题成立，则分配方案为
Ones(m) = Zeros(m) = (m-1)/2
Proposal(m) = Gold-Ones(m),0,1,…,0,1
= Gold-(m-1)/2, 0, 1, …,0,1
当n=m+1时，显然命题成立，理由如下
Ones(m+1) = (m+1-2)/2=(m-1)/2，Zeros(m+1) = (m+1)/2
注意：a) m+1为偶数，计算ones和zeros需要换个公式b) 对比n=m情形，仅仅是多了个0。
Proposal(m+1) = Gold-Ones(m+1),0,1,…,0,1,0
= Gold-(m-1)/2, 0, 1, …,0,1,0
对比Ones(m),Ones(m+1),Zeros(m),Zeros(m+1)可以看出仅仅是在Proposal(m)序列后面添个0。这会导致Proposal(m+1)与Proposal(m)两个序列中，0、1交错序列刚好错位，对应金币分配方案中则为：m+1号海盗分配方案就是把Proposal(m)中没有得到金币的人每人给1个金币实现自己金币最大化，同时保证同意的人数大于等于2。
综上所述，当n为奇数时，该命题成立。
再证明n为偶数时命题是否成立。
当n=2时，命题成立（大于的最小偶数只能是2）
归纳方法同1。
综合1、2分析，该命题成立。
证毕。
该标准化解决方案用程序实现如下
说明：该程序考虑了金币数量远小于海盗数量时，最先出来分配的部分海盗都得喂鲨鱼去了。
$ cat nim.c
#include
const int g_first = 2;
const int g_zero = 0;
const int g_one = 1;
int print_proposal(int *gold, int *pirate, int *ones, int *zeros, int *status) {
int ret = 1;
int number = 0;
int remain = *gold - *ones;
if (*pirate <= 0) {
printf(".\n");
return 0;
}
if (remain <= 0) {
number = 0; /* not enough gold, killed by others, regenerate proposal */
ret = 1; /* conitnue */
/* regenerate proposal */
if (*pirate % 2 == 0) {
*ones = (*pirate - 2) / 2;
*zeros = *pirate / 2;
} else {
*ones = *zeros = (*pirate - 1) / 2;
}
} else if (*status == g_one) {
number = 1;
*ones--;
*status = g_zero;
} else if (*status == g_zero) {
number = 0;
*zeros--;
*status = g_one;
} else {
number = remain;
*status = g_zero;
}
if (*status != g_first && *ones <= 0 && *zeros <= 0) {
ret = 0;
}
printf("%d ", number);
*pirate = *pirate - 1;
return ret;
}
int main()
{
int gold;
int pirate;
int ones;
int zeros;
int temp;
int status; /* process first, zero or one */
printf("Please Enter gold and pirate number:\n");
while (scanf("%d %d", &gold, &pirate) == 2) {
if (pirate < 1 || gold < 1)
break;
if (pirate % 2 == 0) {
ones = (pirate - 2) / 2;
zeros = pirate / 2;
} else {
ones = zeros = (pirate - 1) / 2;
}
status = g_first;
printf("Proposal(%d, %d) is: ", gold, pirate);
temp = pirate;
while (print_proposal(&gold, &temp, &ones, &zeros, &status))
;
if (pirate == 1)
printf(".\n");
printf("\n");
printf("Please Enter gold and pirate number:\n");
}
return 0;
}
程序运行结果如下所示
$ gcc nim.c -o nim
$ ./nim
Please Enter gold and pirate number:
100 1
Proposal(100, 1) is: 100 .
Please Enter gold and pirate number:
100 2
Proposal(100, 2) is: 100 0 .
Please Enter gold and pirate number:
100 3
Proposal(100, 3) is: 99 0 1 .
Please Enter gold and pirate number:
100 4
Proposal(100, 4) is: 99 0 1 0 .
Please Enter gold and pirate number:
100 5
Proposal(100, 5) is: 98 0 1 0 1 .
Please Enter gold and pirate number:
0
决定下一步
本问题到此为止，暂时没有下一步动作。
总结
这个结论告诉我们
- 最先掌握分配权的人，看似最危险，胆小的人可能会担心所有人都不支持你，你就只能下海去喂鲨鱼了。其实，他优先掌握了主动权，天下武功，唯快不破，掌握市场先机很重要。
- 越快越好，但不能快过了头。100个金币，1000个海盗的话，最先出来分配的人必然死掉。同样的，20年前搞酒店搜索，率先占据主动权，快得一塌糊涂那也没戏。
完。
最新评论