《取石子游戏.docx》由会员分享，可在线阅读，更多相关《取石子游戏.docx（4页珍藏版）》请在三一文库上搜索。
1、取石子游戏取石子游戏有一种很有意思的游戏，就是有物体若干堆，可以是石子，也可以是火柴棍或是围棋 子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者为胜。这是我国民间很 古老的一个游戏，由于早先是用石子来玩的，我们习惯称之为“取石子游戏”。别看这游 戏极其简单，却蕴含着深刻的数学原理。好从祖先那里来追寻荣耀的中国人，还称取石子 游戏是“博奕论”的鼻祖呢。下面从取石子游戏的几种典型玩法的数学模型来分析一下要如何才能够取胜的策略。(一) 巴什博奕( Bash Game)只有一堆 n 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 m 个。最后取光者得胜。显然，如果n=m+1那
2、么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果 n=(m+1)*r+s ，( r 为任意自然数， s这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个， 谁能报到 100 者胜。(二) 威佐夫博奕( Wythoff Game ) 有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每 次至少取一个，多者不限，最后取光者得胜。这种情况下是颇为复杂的。我们用(ak , bk )(ak < bk ,k=0 , 1, 2,n)表示两堆物品的数量并称其为局势，如果甲面对(
3、 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
4、 、任意操作都可将奇异局势变为非奇异局势事实上，若只改变奇异局势( ak ，bk )的某一个分量，那么另一个分量不可能在其 他奇异局势中，所以必然是非奇异局势。如果使( ak ， bk )的两个分量同时减少，则由 于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。3 、采用适当的方法，可以将非奇异局势变为奇异局势。假设面对的局势是( a,b )，若 b = a ，则同时从两堆中取走 a 个物体，就变为了 奇异局势( 0，0)；如果 a = ak ，b > bk ，那么，取走 b - bk 个物体，即变为奇异局势； 如果 a = ak ， b ak ， b= ak + k, 则从
5、第一堆中拿走多余的数量 a - ak 即可；如果 a从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜； 反之，则后拿者取胜。那么任给一个局势( a ，b )，怎样判断它是不是奇异局势呢？我们有如下公式： ak =k (1+V5) /2 , bk= ak + k (k=0, 1, 2, .,n方括号表示取整函数)奇妙的是其中出现了黄金分割数(1+V5)/2 = 1。618., 因此,由ak , bk组成的矩形近似为黄金矩形，由于 2/ ( 1+V5) = (“5 -1 ) /2，可以先求出 j=a (“5 -1 ) /2,若 a=j(1+V5) /2，那么 a = aj
6、, bj = aj + j，若不等于，那么 a = aj+1 , bj+1 = aj+1 + j+ 1 ,若都不是,那么就不是奇异局势。然后再按照上述法则进行,一定会遇到奇异局势。(三) 尼姆博奕( Nimm Gam)e有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个, 多者不限,最后取光者得胜。这种情况最有意思,它与二进制有密切关系,我们用( a , b , c )表示某种局势, 首先( 0, 0, 0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势 是( 0, n , n ),只要与对手拿走一样多的物品,最后都将导致( 0, 0, 0)。仔细分析 一
7、下,( 1, 2, 3)也是奇异局势,无论对手如何拿,接下来都可以变为(0, n , n )的情形。计算机算法里面有一种叫做按位模2力口，也叫做异或的运算，我们用符号表示这种运算。这种运算和一般加法不同的一点是1+1=0。先看( 1, 2, 3)的按位模 2加的结果：1 = 二进制 012 = 二进制 10二进制110 = 二进制 00 (注意不进位)对于奇异局势( 0，n ， n )也一样，结果也是 0。任何奇异局势(a , b , c )都有a ® b ® c =0。如果我们面对的是一个非奇异局势( a ， b ， c )，要如何变为奇异局势呢？假设 a例1、( 14,
8、 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)-&g
9、t;(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)奇异局势甲胜。最后再出几道思考题,请找出胜策(当没有必胜的策略时,肯定不败的策略就是胜 策)：1 、巴什博奕( Bash Game)桌面上有 2019 根火柴，二人参加游戏。规则是：二人轮流从中取出火柴，每次可取出
10、1 3根，谁取到最后一根谁获胜（Last Player Winning ，简称LPW）。你为了保证获 胜，应选择先取还是后取？如果你先取，第一次应取几根？当对方取了下一步后，你又应 相应地采取什么策略？如果将规则改为谁取到最后一根谁输（ Last Player Losing ，简称LPL ），保证获胜的策略又相应有什么改变？ 将上面规则中的“每次可取出13根”改成“每次可取出 1N 根”， N 是小于 2019的任意数，你又如何保证自己获胜？2 、斐波那西博弈（ Fabonacci Game）桌面上有 2019 根火柴，二人参加游戏。规则是：二人轮流从中取出火柴，每次可取 出 13 根，直至取
11、完。取完后清点手中的火柴根数，谁取到奇数根谁获胜。你为了保证 获胜，应选择先取还是后取？如果你先取，第一次应取几根？当对方取了下一步后，你又 应相应地采取什么策略？如果将规则改为谁取到偶数根谁赢，保证获胜的策略又相应有什 么改变？将上面规则中的“每次可取出13 根”改成“每次可取出 1N 根”， N 是小于2019 的任意数，你又如何保证自己获胜？3 、 NIM 博弈桌面上有2019堆火柴，根数分别为1, 2，2019。二人参加游戏。规则是：二人 轮流从中取出火柴，每次限制只能在其中一堆中取出任意根，不能同时在两堆中取（当然 轮到你取时也不能不取，这其实与“不能同时在两堆中取”是等价条件）。谁取到最后一 根谁获胜（LPW）。你为了保证获胜，应选择先取还是后取？如果你先取，第一次应在第 几堆中取几根？当对方取了下一步后，你又应相应地采取什么策略？如果将规则改为 LPL ，保证获胜的策略又相应有什么改变？