第7讲组合数学之游戏策略（二）

1、第7讲组合数学之游戏策略（二）例1.甲、乙两人在一个有99个石子的石堆玩取石子游戏，两人轮流取1个或4个，约定 谁取走最后一个算谁贏，现在甲先取，他应采取什么样的策略才能保证取胜？解：甲先取4个，剩下95个；然示不管乙取1个或4个，甲对应取4个或1个，每次剩给 乙的石子的个数是5的倍数，甲就可以取胜。例2.卬、乙两人在一个有150个石了的石堆玩取石了游戏，两人轮流取1个或任意质数个。 约定谁取走最后一个算谁赢，现在甲先取，他应采取什么样的策略才能保证取胜？ 解：甲第一次取2个，剩下148个，是偶数,并且是4的倍数，下一次不论甲取什么样的数， 甲只需取一个数，使得两数z和是4的倍数即可，由于每一

2、个大于4的质数，它被4除的余 数一定是1、3中的一个，所以这项工作能完成，直到剩余的数是8或者4,让乙面对8或4,当乙面对8时，乙若収1,则甲取7；乙若去2,则甲取2剩余4个；若乙収3,则甲 取5,若乙取5,则甲取3,若乙取7,则甲取1；当乙而对4时，乙取1、2、3,则甲相应取3、2、1即可。例3. 1到15这15个自然数在黑板上排成一排，甲、乙两人轮流划数，每次从15个数中划 去一个数或三个相邻的数，谁划掉最后一个谁就胜利了，甲先划，那么谁有必胜策略？解：甲先划去&使得两边各剩余7个数，且形式相同，则无论乙怎么取，甲都在相对的另 一边的对称位置取即可。例4.图中是一副2007棋，甲、

3、乙两人玩棋，分別収红黑两方，规定下棋吋，每人只能走 任意一枚棋子，每枚棋子每次可以走一格或儿格，红棋从左到右，黑棋从右到左，但不能跳 过对方的棋子，也不能重叠在对方有棋子的格子里，一直到谁无法走棋时谁就失败。甲先乙 示，请问谁有必胜策略？解：甲第一次把第一行走到头，留给乙2006行一样的棋盘。然后将2016行每两行看成一组，无论乙怎么走，甲都在对应的行屮走为乙相同的步数，留 下了的局面一定还是一个对称的形式，这样卬就可以取胜了。例5甲、乙两人玩数字游戏，他们轮流用19中任意数字（数字可重复使用）代表五位数abcde中的一个数字，如果最后这个数能被4整除，则甲胜，如果不能被4整除，贝忆胜，谁有必

4、腔策略？解：乙有必胜的把握。因为数字e的位置一定是一个偶数，所以甲第一步一定要把e选择为一个偶数，否则 甲就失败了；这吋乙选择合适的数字填在q处，使得两位数de不能被4整除，那么整个五位数一 定不能被4整除。所以最后乙获胜。例6.甲、乙两人轮流在黑板上写27中的正整数，规定在黑板上写过的数，它的任何倍数 就不能再写了，最后不能写的人为火败者。如果甲写第一个数，那么谁冇必胜策略？如果是 写28 z间的正整数呢？解：枚举法：若甲先取2,剩余3、5、7,则乙胜；若甲先取3,剩余2、4、5、7,乙取2,则乙胜;若甲先取4,剩余2、3、若甲先取5,剩余2、3、 若甲先取6,剩余2、3、 若甲先取7,剩余

5、2、3、5、6、4、4、4、65、5、7,7,7,6,乙取6,则乙胜;乙取2,则乙胜;乙取4,则乙胜;乙取2,则乙胜;所以乙必胜;若是甲先取，则卬取走8,剩下的策略与前面一样，所以卬必胜。例799张卡片上分别写着199,甲先从屮抽走一张，然后乙再从屮抽走一张，如此伦流 下去，若最后两张上的数是互质数，则甲胜，若蝕后剩下的两个数不是互质数，则乙胜，问： 甲想要获胜应该怎样抽取卡片？解：甲先取走l剩下的数，每相邻的两个数都是互质的。分组:（2、3）, （4、5）, （6、7）, （98、99）,于是甲第一次取走1,剩下49组数，只要乙取走一个数，甲就取走同一组内的另外一 个数即可。最后剩下的两个数

6、一定是互质的。例8.甲班与乙班学牛同时从学校出发去公园，甲班步行的速度是每小时4千米，乙班步行 的速度是每小时3千米，学校有一辆汽年，它的速度是每小时48千米，这辆汽不恰好能坐 一个班的学生，为了使两个班学生在最短时间内到达公园，那么甲班与乙班于生需要步行的 距离z比是多少？解：随堂测试1. 甲、乙两人在一个有100个石子的石堆玩取石子游戏，两人轮流取1个或2个，约定谁 取走最后一个算谁赢，现在卩先取，他应采取什么样的策略才能保证取腔？解：甲先取走1个，剩卜99个。后而若乙収1个则甲取2个，若乙取2个则甲取1个，使得剩余的数一定是3的倍数, 这样就可以取胜。2. 学学和旭旭两人玩取石子游戏，有

7、一堆石子，两人轮流取，轮到自己取的时候可以去1 个、2个或4个，谁取最后一个算赢，第一局一开始只有一个石子，以后每一局开始的石子 的个数比上一局多一个，总共玩了 4（）局，第一局学学先取，第二局旭旭先取，等等，两人 轮流先取，学学和旭旭是足够聪明的人，都会选择最优的策略，问旭旭一共赢多少局？ 解：第一局，学学赢：第二局，学学赢，笫三局：旭旭赢；第四局：学学赢；笫五局：学学赢；（学学取走2个，剩余3个。）第六局：旭旭赢（学学先取1、2、4个，剩余5、4、2个给旭旭，结果相同于第五、四、 一局屮自己的地位）；第七局：学学赢；（学学取走4个，剩余3个）；第八局：学学赢：（学学先取走2个，剩余6个，参

8、考笫六局的情况，学学赢）；第九局：旭旭赢：（学学先取1、2、4个，剩余8、7、5个给旭旭，结果相同于第八、 七、五局中白己的地位）；综上所述，旭旭赢的局是笫三、六、九，等，也就是说，旭旭一共赢了 13局。学学赢了 27局。3. 1到10这10个自然数在黑板上排成一排，甲、乙两人轮流划数，每次从10个数中划去 一个数或划去三个相邻的数，谁划掉最后一个谁就胜利了，甲先划，那么谁冇必胜策略？ 解：乙有必腔策略。甲如果先划走三个数，则乙也划去三个数，剩余四个数，若这四个数中没有三个数相 邻，则乙一定获胜；若这四个数屮还有三个数相邻，甲也不能划走这三个数，还是乙获胜;如果甲先划一个数，那么乙划走三个数，

9、剩余六个数，乙仍然取胜。4. 卞图是一种红黑棋，甲、乙两人玩棋，分别取红黑两方，规定：每人每次只能走任意一 枚棋子，每枚棋子每次可以走一格或儿格，红棋从左向右走，黑棋从右向左走，但不能跳过 对方的棋了，也不能重亞在对方有棋了的格了里，一肯到谁也无法走棋时，谁就失败。甲先 乙后走棋，问甲有没有必胜策略？解：有必胜策略，甲笫一次把上面的棋子向前走4格，使得上行的情况与下血一行完全一样，不论后血乙怎么 走，甲都在另一行中走与乙相同的步数，即可获胜。5. 甲、乙两人玩数字游戏，他们轮流在数7d8236的方框内填入一个数字，规则是：甲先 填一个数字，如果乙再填一个数字，使这个六位数是11的倍数，则乙获胜

10、，反之，如果乙 填出来的数字没有使这个六位数是11的倍数，则甲获胜，问先填的甲有没有必胜的策略？ 如果有，应该怎么填；如果没冇，说明理由。解：甲有必胜策略；把两个方框设为a, b,数是7a82b6,如果能被11整除,应该使（7+8+b）-+2+6）=7+b-a 是 11 的倍数，甲在a处填6填，这吋式子成为b+1为11的借数，乙无法填了，甲胜。或甲在b处填3,这时式子成为10-a是11的倍数，乙也无法填了。甲胜6. 有两堆石了，分别是7个和8个，甲乙伦流取，可以从某堆屮取任意个（不能为（），或 者从每堆里取出同样多个，谁取定最后一个谁就算谁赢，现在卩先取，谁会赢？并指出获胜 策略。解：甲可以赢

11、，即甲从两堆中各取6个石子，剩余的是（1、2）的局势。无论乙怎么取，甲都胜利。7. 黑板上写有1、2、3、100这100个b然数，甲、乙两人轮流每次划去一个数，直 到剩下两个数为止，如剩下的两数互质，则判甲胜，否则判乙胜，乙先划甲后划，谁有必胜 策略？必胜策略是怎样的？解:相邻的两个自然数是互质的。将这些数分成50组:（、2）, （3、4）, （5、6）,(99、100),若乙划去一个数，则甲划去同组中的另一个数,这样甲获胜。说明：教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”1不是质数也 不是合数，但是它和任何一个自然数在一起都是互质数。所以(1与2是互质的)8. 甲、乙两

12、人在一张19x94的方格表上进行游戏，每人每次可以涂黑一个网格线为边的正 方形，正方形边长是1到19的整数，同时每个小格只能被涂黑一次，即正方形之间不能匣 叠，现在甲先开始，两人轮流进行，谁涂黑了最后一个小方格，谁就获胜，那么在两人都正 确操作的情况下，谁有必腔策略？解：把47、48两列间的边界线称为中轴线,甲从一开始将关于屮轴线对称的一个18x18的正方形涂黑，然后每次都把乙涂黑的正 方形关于中轴线对称的那个正方形涂黑即可。所以甲有必胜策略。6.这是威佐夫博弈(wthoff g<?/77e)有两堆各若干个物品，两个人轮流从某一堆或同吋从两堆中取同样多的物品，规定每次 至少取一个，多者不

13、限，最后取光者得胜；这种规则下游戏是颇为复杂的。我们用(貝甸，优甸)1, 2,/?) 表示两堆物品的数量并称其为局势。如果甲面对(0, 0),那么甲经输了，这种局势我们称为奇异局势。首先列举人们已经发现的前几个奇异局势:(0, 0)、(1, 2)、(3, 5)、(4, 7)、(6, 10)、(8, 13)、(9, 15)、(11, 18)、(12, 20)o通过观察发现：a0=zt0=0xa是未在前面出现过的最小自然数，而仇幻二况幻+ k。 奇异局势有如下三条性质：1、任何自然数都包含h.仅包含在一个奇异局势中。2、任意操作都对以使奇异局势变为非奇杲局势。3、必冇一种操作可以使非奇异局势变为奇

14、异局势。性质1屮的存在性很好理解，对于唯一性，因为a甸是未在前面出现过的最小自然数。所以司甸>孔匕1,优幻=a幻+ 1>a匕1即优甸>a甸>-1 >a匕1。所以某个白然数不会出现多于一次的情况。性质2,我们可以尝试游戏规则中的两利|操作:如果从某一堆中取，那么司甸,仇甸中必有一个量发生变化，由性质1,则变化后的局势 不可能是奇显局势。如果同吋从两堆中取同样多的物品，但由于其差(切沟孔甸)不会改变，所以它变化后 的局势也不可能是奇异局势。性质3,需要分多种情况考虑，假设面对的局势是(i,j),(我们规定i<=j)1 若i=j,则同时从两堆取走i个，局势变成(0,0)的奇异局势.2若i是某个奇异局势的况幼 且则从j中取出个，局势变成(玄©优甸) 的奇界局势.3若i是某个奇异局势的a甸，且两堆z差为j-i个，同时从两堆中取出a幻 -4ri个，局势变成(ji )的奇异局势.4若j是某个奇异局势的切旬，且i>a勺则从i中収岀卜弍沟个，局势变成（孔幻切幼