又见博弈参考答案(第五期)
修改于2019/07/11167 浏览综合
博弈论深入的东西有很多很多，此次参考答案就题论题，没有深入展开，如果你对博弈论这块感兴趣，可以自己找时间专门学习。类似于第三题的取石子博弈还有巴什博弈(Bash Game)、威佐夫博弈(Wythoff Game)、斐波那契博弈(Fibonacci)等等……
1.
500张骨牌整齐地排在一行，按顺序编号为1、2、3、……、499、500。
1)第一次拿走所有偶数位置上的骨牌，第二次再从剩余骨牌中拿走偶数位置的骨牌，以此类推，请问最后剩下的一张骨牌的编号是多少？
2)第一次拿走所有奇数位置上的骨牌，第二次再从剩余骨牌中拿走奇数位置的骨牌，以此类推，请问最后剩下的一张骨牌的编号是多少？
2.
有两个学生，放学后他们偶然看到了校园小树林深处，有一棵奇怪的树，上面长满了奇怪的果实。突然这棵树发出了声音：“智慧树上智慧果，智慧树下你和我。智慧树下做游戏，欢乐多又多。两位年轻人，你们好，欢迎来到智慧树乐园。”说完便从树上掉下一朵花来，对两个人说：“这朵花有13片花瓣，现在请你们轮流摘去花瓣，一个人可以摘去一片或相邻的两片，谁摘去最后的花瓣就是赢家，他将得到一箱的智慧果。”
那么你觉得是选择先摘好还是后摘好？给出你的策略。
如果先摘取者摘了一片花瓣，那么后摘取者在花瓣的另一边摘去2片花瓣；如果先摘取者摘了2片花瓣，那么，后摘取者在花瓣的另一边摘去1片花瓣。这时，剩下10片花瓣。后摘取者在第一次摘时保证在摘取后，剩下的10片花瓣分成两组，并且这两组被上轮摘取的3个花瓣的空缺隔开。在以后的摘取中，如果先摘者摘取1片，后摘者也摘1片；如果先摘者摘了2片，后摘者也摘2片。并且摘取的花瓣是另一组对应的位置，这样下去，后摘者一定可以摘到最后的花瓣。
3.
现有5堆石子，石子数依次是3,5,7,19,50，甲乙两人任一堆中任取（每次只能取自一堆，不能不取），取最后一颗石子的一方获胜。甲先取，问甲有没有获胜策略（即无论乙怎么取，甲只要不失误，都能获胜）？如果有，甲的第一步应该在哪一堆里取多少？
4.
在平时做题中我们经常会遇到经典的海盗分金问题，现在我们把这个问题扩大到500名海盗的情形，即500名海盗抢得了窑藏的100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后由下一位最厉害的海盗重复上述过程。
所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们更愿意得一笔现金，当然也不愿意自己被扔到海里。所有的海盗都是有理性的，而且知道其他的海盗也是有理性的。此外，没有两名海盗是同等厉害的——这些海盗按照完全由上到下的等级排好了座次，并且每个人都清楚自己和其他人的等级。这些金块不能再分割，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。
为方便起见，我们按照这些海盗的怯懦程度来给他们编号。最怯懦的海盗为1号海盗，次怯懦的海盗为2号海盗，以此类推。这样最厉害的海盗就应当得到最大的编号，而方案的提出就将倒过来从上至下地进行。在采取最优策略的前提下，最终编号为多少的海盗提出的方案会被通过?
答案：456名
经典的海盗分金问题所述的规律直到第200号海盗都是成立的。200号海盗的方案将是：从1～199号的所有奇数号的海盗都将一无所获，而从2～198号的所有偶数号海盗将各得1块金子，剩下的1块金子归200号海盗自己所有。
乍看起来，这一论证方法到200号之后将不再适用了，因为201号拿不出更多的金子来收买其他海盗。但是即使分不到金子，201号至少还希望自己不会被扔进海里，因此他可以这样分配：给1～199号的所有奇数号海盗每人1块金子，自己一块也不要。
202号海盗同样别无选择，只能一块金子都不要了——他必须把这100块金子全部用来收买100名海盗，而且这100名海盗还必须是那些按照201号方案将一无所获的人。由于这样的海盗有101名，因此202号的方案将不再是唯一的——贿赂方案有101种。
203号海盗必须获得102张赞成票，但他显然没有足够的金子去收买101名同伙。因此，无论提出什么样的分配方案，他都注定会被扔到海里去喂鱼。不过，尽管203号命中注定死路一条，但并不是说他在游戏进程中不起任何作用。相反，204号现在知道，203号为了能保住性命，就必须避免由他自己来提出分配方案这么一种局面，所以无论204号海盗提出什么样的方案，203号都一定会投赞成票。这样204号海盗总算侥幸捡到一条命：他可以得到他自己的1票、203号的1票，以及另外100名收买的海盗的赞成票，刚好达到保命所需的50％。获得金子的海盗，必属于根据202号方案肯定将一无所获的那101名海盗之列。
205号海盗的命运又如何呢？他可没有这样走运了。他不能指望203号和204号支持他的方案，因为如果他们投票反对205号方案，就可以幸灾乐祸地看到205号被扔到海里去喂鱼，而他们自己的性命却仍然能够保全。这样，无论205号海盗提出什么方案都必死无疑。206号海盗也是如此——他肯定可以得到205号的支持，但这不足以救他一命。类似地，207号海盗需要104张赞成票——除了他收买的100张赞成票以及他自己的1张赞成票之外，他还需3张赞成票才能免于一死。他可以获得205号和206号的支持，但还差一张票却是无论如何也弄不到了，因此207号海盗的命运也是下海喂鱼。
208号又时来运转了。他需要104张赞成票，而205、206、207号都会支持他，加上他自己一票及收买的100票，他得以过关保命。获得他贿赂的必属于那些根据204号方案肯定将一无所获的人（候选人包括2～200号中所有偶数号的海盗以及201、203、204号）。
现在可以看出一条新的、此后将一直有效的规律：那些方案能过关的海盗（他们的分配方案全都是把金子用来收买100名同伙而自己一点都得不到）相隔的距离越来越远，而在他们之间的海盗则无论提什么样的方案都会被扔进海里——因此为了保命，他们必会投票支持比他们厉害的海盗提出的任何分配方案。得以避免葬身鱼腹的海盗包括201、202、204、208、216、232、264、328、456号，即其号码等于200加2的某一次方的海盗。
现在我们来看看哪些海盗是获得贿赂的幸运儿。分配贿赂的方法是不唯一的，其中一种方法是让201号海盗把贿赂分给1～199号的所有奇数编号的海盗，让202号分给2～200号的所有偶数编号的海盗，然后让204号贿赂奇数编号的海盗，208号贿赂偶数编号的海盗，以此类推，也就是轮流贿赂奇数编号和偶数编号的海盗。
结论是：当500名海盗运用最优策略来瓜分金子时，头44名海盗必死无疑，而456号海盗则给从1～199号中所有奇数编号的海盗每人分1块金子，问题就解决了。由于这些海盗所实行的那种民主制度，他们的事情就搞成了最厉害的一批海盗多半都是下海喂鱼，不过有时他们也会觉得自己很幸运——虽然分不到抢来的金子，但总可以免于一死。
只有最怯懦的200名海盗有可能分得一份赃物，而他们之中又只有一半的人能真正得到一块金子，的确是怯懦者继承财富。