取石子-博弈论

小灰灰 2022-08-22 03:52 186阅读 0赞

有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物

体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深

刻的数学原理。下面我们来分析一下要如何才能够取胜。

**（一）巴什博弈（Bash Game，同余理论）****：****只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个****，最多取m个。最后取光者得胜。**

显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次

拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s

≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下

（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍

数，就能最后获胜。  
这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100

者胜。  
**（二）威佐夫博弈（Wythoff Game，黄金分割）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样****多的物品，规定每次至少取一个，多者不限，最后取光者得胜。**

这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，...,n)表示两堆物品的数量

并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是

：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12

，20）。  
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有  
如下三条性质：

1。任何自然数都包含在一个且仅有一个奇异局势中。  
由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1

> ak-1 。所以性质1。成立。  
2。任意操作都可将奇异局势变为非奇异局势。  
事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所

以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局

势的差，因此也是非奇异局势。  
3。采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）

；如果a = ak ，b > bk，那么，取走b - bk个物体，即变为奇异局势；如果 a = ak ， b < bk ,则同

时从两堆中拿走 ak - ab - ak个物体,变为奇异局势（ ab - ak , ab - ak+ b - ak）；如果a > ak ，

b= ak + k,则从第一堆中拿走多余的数量a - ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，

a=aj （j < k）,从第二堆里面拿走 b - bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b - aj

即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者

取胜。

那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：  
ak =\[k（1+√5）/2\]，bk= ak + k （k=0，1，2，...,n 方括号表示取整函数)  
奇妙的是其中出现了黄金分割数（1+√5）/2 = 1。618...,因此,由ak，bk组成的矩形近似为黄金矩形，

由于2/（1+√5）=（√5-1）/2，可以先求出j=\[a（√5-1）/2\]，若a=\[j（1+√5）/2\]，那么a = aj，bj

= aj + j，若不等于，那么a = aj+1，bj+1 = aj+1+ j + 1，若都不是，那么就不是奇异局势。然后再按

照上述法则进行，一定会遇到奇异局势。

**（三）尼姆博弈（Nim Game，异或理论）：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次****至少取一个，多者不限，最后取光者得胜。**

这种情况最有意思，它与二进制有密切关系，我们用（a，b，c）表示某种局势，首先（0，0，0）显

然是奇异局势，无论谁面对奇异局势，都必然失败。第二种奇异局势是（0，n，n），只要与对手拿走一

样多的物品，最后都将导致（0，0，0）。仔细分析一下，（1，2，3）也是奇异局势，无论对手如何拿，

接下来都可以变为（0，n，n）的情形。

计算机[算法][Link 1]里面有一种叫做按位模2加，也叫做异或的运算，我们用符号（+）表示这种运算。这种运

算和一般加法不同的一点是1+1=0。先看（1，2，3）的按位模2加的结果：

1 =二进制01  
2 =二进制10  
3 =二进制11 （+）  
———————  
0 =二进制00 （注意不进位）

对于奇异局势（0，n，n）也一样，结果也是0。

任何奇异局势（a，b，c）都有a（+）b（+）c =0。

如果我们面对的是一个非奇异局势（a，b，c），要如何变为奇异局势呢？假设 a < b< c,我们只要将 c

变为 a（+）b,即可,因为有如下的运算结果: a（+）b（+）(a（+）b)=(a（+）a)（+）(b（+）b)=0（+）

0=0。要将c 变为a（+）b，只要从 c中减去 c-（a（+）b）即可。

例1。（14，21，39），14（+）21=27，39-27=12，所以从39中拿走12个物体即可达到奇异局势（14

，21，27）。

例2。（55，81，121），55（+）81=102，121-102=19，所以从121中拿走19个物品就形成了奇异局势

（55，81，102）。

例3。（29，45，58），29（+）45=48，58-48=10，从58中拿走10个，变为（29，45，48）。

例4。我们来实际进行一盘比赛看看：  
甲:(7,8,9)->(1,8,9)奇异局势  
乙:(1,8,9)->(1,8,4)  
甲:(1,8,4)->(1,5,4)奇异局势  
乙:(1,5,4)->(1,4,4)  
甲:(1,4,4)->(0,4,4)奇异局势  
乙:(0,4,4)->(0,4,2)  
甲:(0.4,2)->(0,2,2)奇异局势  
乙:(0,2,2)->(0,2,1)  
甲:(0,2,1)->(0,1,1)奇异局势  
乙:(0,1,1)->(0,1,0)  
甲:(0,1,0)->(0,0,0)奇异局势  
甲胜。

[Link 1]: http://lib.csdn.net/base/31

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关【博弈论】因数-数字游戏 | 石子游戏

因数-数字游戏题目小Q的柠檬汁做完了，掏出了自己的数字卡牌，想要和别人做数字游戏，可是她又不想要输掉游戏。她制定好规则，每次每个人只能把这个牌换成它的因子的某个

墨蓝/ 2024年03月25日 08:56/ 0 赞/ 72 阅读

相关 1812: 取石子（一）

1812: 取石子（一）时间限制: 3 Sec 内存限制: 64 MB 提交: 84 解决: 53 您该题的状态：已完成 \[[提交][Link 1]\]\

àì夳堔傛蜴生んèń/ 2024年02月18日 22:19/ 0 赞/ 39 阅读

相关题目833 取石子

![20160729150723513][] 已AC代码： include <iostream> using namespace std;

浅浅的花香味﹌/ 2022年09月24日 11:18/ 0 赞/ 133 阅读

相关 NYOJ 23-取石子（一）

取石子（一）时间限制：3000 ms | 内存限制：65535 KB 难度：2 描述一天，TT在寝室闲着无聊，和同寝的人玩起了取石子游戏，而由于条件有限，他/她

浅浅的花香味﹌/ 2022年08月22日 03:52/ 0 赞/ 125 阅读

相关取石子-博弈论

有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单

小灰灰/ 2022年08月22日 03:52/ 0 赞/ 187 阅读

相关 HDOJ 2516-取石子游戏

取石子游戏 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others

ゞ浴缸里的玫瑰/ 2022年08月20日 04:19/ 0 赞/ 162 阅读

相关取石子问题

<table> <tbody> <tr> <td align="center"><span style="font-size:14px

青旅半醒/ 2022年08月06日 12:23/ 0 赞/ 150 阅读

相关 poj 1067 取石子游戏

取石子游戏 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

超、凢脫俗/ 2022年08月03日 14:40/ 0 赞/ 178 阅读

相关取石子定输赢

题目内容：有一堆石子，A，B两人轮流从中取出石子，每次取出的石子数目只能为1，3，7或8，最后一枚石子谁取到就是输方。A,B两人都足够聪明，不会做出错误的判断。现给出一定数

怼烎@/ 2021年12月15日 10:11/ 0 赞/ 236 阅读

相关取石子游戏

[也许更好的阅读体验][Link 1] \\(\\mathcal\{Description\}\\) ![qsz10914f.png][][![qsz2b35c5.png]

港控/mmm°/ 2021年11月09日 20:04/ 0 赞/ 268 阅读