下载文档原格式
组合数学第08讲_必胜策略游戏策略中往往有一类比较复杂的，需要逐步来递归的问题，这就需要对必胜与必败转态进行标记．一．网格移动类1．含义：给定一个东西和固定的表格，给出移动该物体的规则，最终谁移动到不能再移谁就算胜（或者输），求必胜（或必败）策略．2．方法：从最后必胜（或必败）的转态进行倒推，找出一般的规律，将必胜（或必败）的格子都标记出来即可找出必胜策略．二．其他类型1．特点：操作次数比较有限，没有周期规律．2．方法：由于操作次数较少，所以通常用枚举法，将必胜的操作标记出来，就可以得到必胜策略．重难点：从最后的必胜条件出来，进行倒推，将必胜的操作标记出来．题模一：网格移动类例1.1.1如下图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45 角走1步，最终将棋子走到方格B的人获胜．请问：（1）谁一定能获胜？必胜策略是什么？BA【答案】（1）甲必胜；（2）甲必胜【解析】（1）我们给必胜格子（如方格B）标记“√”，给必败格子标记“×”．从方格B逆推，能一步走到B的格子都要标记“×”．特别地，最上边一行和最右边一列为“√”和“×”相间的标记，如左图．对于左图中的格子1和格子3，对方有办法把它移到必胜格子中，所以格子1和格子3都是必败格子．如果把棋子移到格子2中，对手无论怎么移，都只能移到必败格子中，因此格子2是必胜格子．用类似的方法分析，得到右图．因此甲有必胜策略，每次把棋子移到标有“√”的格子中即可．（2）与第（1）问方法类似，得到下图．甲有必胜策略，每次把棋子移到标有“√”的格子中 即可．例1.1.2如图，方格A 中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B 的人获胜．请问：（）一定能获胜？A ．甲B ．乙C ．甲和乙都有可能【答案】B【解析】如下图标a 都是必胜格，A 本身就在必胜格里，所以先走的到达不了下一个必胜格，所以乙胜． 例1.1.3如图，方格A 中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B 的人赢．请问：（）一定能获胜？√ × √ × √ × B 1 × × 2 3 √ × √ A × √× √ × √ × B × × × × × × × √ × √ × √ × √ × × × × × × × √ × √ × √ × √ A × × × × × ××× × × × × B × × × × √ × × × × × × × √ × × √ × × × × × × × × × × × × A × × √ × × ×B AB a a ABAA．甲B．乙C．甲和乙都有可能【答案】A【解析】如图表有a的都是必胜格，只要甲第一步走到标有a个格必胜，选A．BaaaA a例1.1.4把一枚棋子放在图中左下角的方格内，甲、乙两人玩这样一个游戏：双方轮流移动棋子，只能向上、向右或者向右上方沿45°角移动，一次可以移动任意多格．谁把棋子移到了右上角的方格中即为输，试问：如果甲先走，是否有必胜的策略，为什么？【答案】乙必胜．从右上角开始分析哪些位置是必胜的，哪些位置是必败的，结果如图所示．因此甲第一步必然走到“√”上，而乙必然可以每一步都给甲留下“×”．【解析】首先看图最右面的那列，在这列中，如果棋子在右上角的下面，那么先走的只能把棋子向上走，所以他必败；如果棋子不在这个位置，那么他只要把棋子走到这个位置便可确保胜利．而为了方便分析，下面在图中先走必胜的位置标“√”，先走必败的位置标“×”，此时图如下所示：对1和2这两个位置，第一步只要走到右上的“×”处，便可取胜，所以标“√”；对3来说，怎么先走的如何走，都是走到一个“√”处，因为“√”处先走必胜，所以对3先走必败，应当标“×”．从上面的分析中，可以发现，对一个位置来说，如果它的上，右或右上有一个“×”，那先走的只需要把棋子移动到这些“×”处便可确保胜利；相反，如果它的三个方向上全是“√”，那无论如何走，都是后走的获胜．根据这个规律，便不难知道对任意一个位置来说，是否先走必胜，从而可以完成这个图，完成后的图如下所示：因为棋子最开始在左下角，甲只能向右走，而它右侧全部是“√”，所以乙必胜，每步时× √ √ √ × √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ √ √ √× 1 √ 2 3 √ √ √ √ √ √ √ ● √× √ √ √ × √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ √ √ √ √ √ √ √ √ √ √ √ × √ √ √ √ ● √ √ √ √ √ √ √ √ √ √乙只需要把棋子移动到“×”即可． 题模二：其它例1.2.1桌上有一块巧克力，它被直线划分成3行7列的21个小方块，如图所示．现在让你和对手进行一种两人轮流切巧克力的游戏，规则如下：①每人每次只许沿一条直线把巧克力切成两块；②拿走其中一块，把另一块留给对手再切；③不断重复前两步，最后谁能恰好留给对手一个小方块，谁获胜．如果你首先切巧克力，那么你第一次应该切走多少个小方块，才能保证自己最后获胜？【答案】切走12个小方块【解析】当只剩1行（或1列）时，但不是一个小方块，先切的人只要切剩下一个小方块就赢了．当剩2行（或2列）时，如果剩22⨯的方块，那么先切的人切完后成为12⨯的方块，所以后切的人必胜；如果剩23⨯、24⨯、…等情况，先切的人只要切剩下一个22⨯的方块就可以取胜．当剩3行（或3列）时，如果剩33⨯的方块，先切的人切一刀后只能剩下13⨯或23⨯的方块，此时后切的人获胜．当有37⨯块时，先切的人切走3412⨯=块，给对手留下一个33⨯的正方形，接着每次都给对手留下一个11⨯或22⨯的正方形即可获胜． 例1.2.2如图为“狡兔三窟”的游戏，游戏中只有两个棋子：一为“猎人”，一为“狡兔”，它们的位置如图所示，棋盘的北端X 是一方飞第，这意味着任何一方棋子，都可以“飞”过X ，即：由C 直接到达D ，或由D 直接到达C ，游戏开始，由“猎人”先走，接下去双方轮流运子，每次一步，每次只能沿着黑线走到其相邻的点上，当猎人和兔子都到同一点时，猎人可以抓住兔子．那么，“猎人”至少要走（ ）步才能抓住兔子．A ．5B ．6C ．7D ．8【答案】B【解析】如果猎人第一步就开始往下抓兔子，那么兔子也会往下跑，这样猎人紧追兔子中间只差一步的话是永远抓不到兔子．那么猎人的对策就是第一步向上走，前三步向上绕一圈，这是猎人在空心点上，兔子在实心点上，如果兔子在1号位置，第4步抓到，若兔子在2，至多再3步抓到，最终在第6步被抓到例1.2.3在黑板上写有999个数，2、3、4、……、1000．甲、乙两人轮流擦去黑板上的一个数（甲先擦，乙后擦），如果最后剩下的两个数互质，则甲胜，否则乙胜．请判断：__________有必胜策略．【答案】乙【解析】共有500个偶数，甲共擦499个数．若甲想获胜，他必须擦499个偶数，否则乙只要先擦奇数，最终必能剩两个偶数，乙胜．但当甲全擦偶数时，乙只要保留两个个位为5的奇数至最后即可，故乙有必胜策略．随练1.1如右图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走1步，最终将棋子走到方格B的人获胜．请问：谁有必胜策略？必BA【答案】甲必胜【解析】策略是每次把棋子走到下图中标有“√”的格子内．√×√× B×××××√×√×√A ××××随练1.2如图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B的人赢．请问：（）一定能获胜？BAA．甲B．乙C．甲和乙都有可能【答案】B【解析】如下图标a都是必胜格，A本身就在必胜格里，所以先走的到达不了下一个必胜格，所以乙胜，选B．BaaaA随练1.3如图，方格A中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走任意步（不能拐弯），最终将棋子走到方格B的人获胜．请问：（）一定能获胜？BAA．甲B．乙C．甲和乙都有可能【答案】A【解析】甲第一步走到如图所示的a处，无论乙怎么走，甲都有方法取胜，所以选A．BaA随练1.4桌上有一块巧克力，它被直线划分为排成3行7列的21个小方块，如图所示．现在让你和对手进行一种两人轮流切巧克力的游戏，规则如下： ① 每次只许沿一条直线把巧克力切成两块； ② 拿走其中一块，把另一块留给对手再切； ③ 谁能留给对手恰好是一个小方块，谁就取胜．如果请你首先切巧克力，那么你第一次应该切走多少个小方块，才能使你最后获胜？【答案】切走12块，给对手留下一个33⨯的正方形，接着每次都给对手留下一个正方形 【解析】如果只剩1行或1列，但不是一个小方块，那么先切的人只要剩一个小方块就赢了；如果剩2行，如果是22⨯的方块，那么先切的人切完后成为12⨯的方块，所以后切的人必胜；如果比22⨯多的话（23⨯，24⨯……），因为22⨯的时候是后切的人获胜，所以这时先切的人只要剩下一个22⨯的方块就可以取胜；在33⨯的时候，先切的切完后，剩下的巧克力是13⨯或者23⨯，根据上面的分析可以知道后切的一定获胜．所以第一刀切完后剩下33⨯的就可以保证获胜了，即是切下3412⨯=块巧克力．随练1.5如图所示，五角星上共有10个交点和15条小线段．甲首先将一枚棋子放在A 点上，并由此出发沿某条小线段将棋子移到相邻的一个交点上，之后乙再将棋子沿某条小线段移到下一个相邻的交点上，之后甲再走，……，如此下去．如果要求每条小线段都不能重复经过，并且轮到某人无路可走时便判其失败，那么甲是否有必胜策略？【答案】甲没有必胜策略，且乙必胜．一旦甲由角上的点走到中间，乙就再走回相邻的角上去．【解析】一枚棋子如果处在五角星的某个角上的话，先走的人只能把它从角上移到中心．而如果在中心的话则可以选择移到角上或者其他中心位置．据此可以给乙想出如下的方案：一旦甲由角上的点走到中间，乙就再走回相邻的角上去，角上的点是5个，中心点也只有5个，最后必然是连成一个封闭图形，甲无路可走．作业1如下图，方格A 中放有一枚棋子，甲先乙后轮流移动这枚棋子，只能向上、向右或向右上方沿45°角走1步，最终将棋子走到方格B 的人获胜．请问：谁一定能获胜？必胜策略是什么？A【答案】甲必胜【解析】我们给必胜格子（如方格B ）标记“√”，给必败格子标记“×”．从方格B 逆推，能一步走到B 的格子都要标记“×”．特别地，最上边一行和最右边一列为“√”和“×”相间的标记，如左图．对于左图中的格子1和格子3，对方有办法把它移到必胜格子中，所以格子1和格子3都是必败格子．如果把棋子移到格子2中，对手无论怎么移，都只能移到必败格子中，因此格子2是必胜格子．用类似的方法分析，得到右图．因此甲有必胜策略，每次把棋子移到标有“√”的格子中即可．作业2（1）在一个3×3的方格棋盘的左上角方格中放有一枚棋子。
必胜策略知识点总结：一取余制胜（取棋子，报数游戏）1．每次取1~n个棋子，总数，取最后一个赢策略：总数÷（1+n）有余则先，拿掉余数，之后总与对手凑成1+n即可无余则后，总与对手凑成1+n即可2. 每次取1~n个棋子，总数，取最后一个输策略：最狠的做法就是留给对方一枚棋子，对方不取也得取。
所以想赢的关键就在于能不能取到倒数第二枚棋子。
问题转化为：每次取1~n个棋子，总数，取倒数第二枚棋子赢。
（总数-1）÷（1+n），之后同1中做法。
二．抢占制胜点（倒推法）1. 能一步到棋子的位置均是不能走的地方即负位2. 处处为别人着想。
自己不能走的地方逼别人走进去即可，即确定制胜点。
三．对称法1. 同等情况下，模仿对方步骤可以达到制胜目的。
2. 不同等情况下，创造对等局面方可制胜。
1.桌子上放着100根火柴，甲、乙二人轮流每次取走1～5根。
规定谁取走最后一根火柴谁获胜。
如果双方都采用最佳方法，甲先取，那么谁将获胜？分析：100÷（1+5）=16 (4)有余数，先拿必胜，甲必胜。
（1）甲先拿4个；（2）乙拿a个，甲就拿6-a个2.甲乙两人轮流报数，报出的数只能是1～7的自然数。
同时把所报数一一累加起来，谁先使这个累加和达到80，谁就获胜。
请问必胜的策略是什么？分析：80÷（1+7）=10无余数，后拿必胜。
甲拿a个，乙就拿8-a个必胜3.1000个空格排成一行，最左端空格中放有一枚棋子，甲先乙后轮流向右移动棋子，每次移动1～7格。
规定将棋子移到最后一格者谁赢。
甲为了获胜，第一步必须向右移多少格？分析：（1000-1）÷（1+7）=124 (7)有余，先走必胜。
（1）甲先走7格（2）乙走a格，甲就拿8-a个必胜4.5张扑克牌，每人每次只能拿1张到4张。
谁取最后一张谁输。
必胜的策略是什么？分析：先拿4张，留给别人1张就行。
5.现有1000根火柴，甲乙两人轮流去拿，每人每次最少拿1根，最多拿7根，谁取最后一根谁输。
毕生策略知识点总结：一取余制胜（取棋子，报数游戏）1．每次取1~n个棋子，总数，取最后一个赢策略：总数÷（1+n）有余则先，拿掉余数，之后总与对手凑成1+n即可无余则后，总与对手凑成1+n即可2. 每次取1~n个棋子，总数，取最后一个输策略：最狠的做法就是留给对方一枚棋子，对方不取也得取。
所以想赢的关键就在于能不能取到倒数第二枚棋子。
问题转化为：每次取1~n个棋子，总数，取倒数第二枚棋子赢。
（总数-1）÷（1+n），之后同1中做法。
二．抢占制胜点（倒推法）1. 能一步到棋子的位置均是不能走的地方即负位2. 处处为别人着想。
自己不能走的地方逼别人走进去即可，即确定制胜点。
三．对称法1. 同等情况下，模仿对方步骤可以达到制胜目的。
2. 不同等情况下，创造对等局面方可制胜。
1.桌子上放着100根火柴，甲、乙二人轮流每次取走1～5根。
规定谁取走最后一根火柴谁获胜。
如果双方都采用最佳方法，甲先取，那么谁将获胜？分析：100÷（1+5）=16 (4)有余数，先拿必胜，甲必胜。
（1）甲先拿4个；（2）乙拿a个，甲就拿6-a个2.甲乙两人轮流报数，报出的数只能是1～7的自然数。
同时把所报数一一累加起来，谁先使这个累加和达到80，谁就获胜。
请问必胜的策略是什么？分析：80÷（1+7）=10无余数，后拿必胜。
甲拿a个，乙就拿8-a个必胜3.1000个空格排成一行，最左端空格中放有一枚棋子，甲先乙后轮流向右移动棋子，每次移动1～7格。
规定将棋子移到最后一格者谁赢。
甲为了获胜，第一步必须向右移多少格？分析：（1000-1）÷（1+7）=124 (7)有余，先走必胜。
（1）甲先走7格（2）乙走a格，甲就拿8-a个必胜4.5张扑克牌，每人每次只能拿1张到4张。
谁取最后一张谁输。
必胜的策略是什么？分析：先拿4张，留给别人1张就行。
5.现有1000根火柴，甲乙两人轮流去拿，每人每次最少拿1根，最多拿7根，谁取最后一根谁输。
对策问题之必胜策略 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT对策问题之必胜策略知识点总结：一取余制胜（取棋子，报数游戏） 1．每次取 1~n 个棋子，总数，取最后一个赢策略：总数÷（1+n）有余则先，拿掉余数，之后总与对手凑成 1+n 即可无余则后，总与对手凑成 1+n 即可 2. 每次取 1~n 个棋子，总数，取最后一个输策略：最狠的做法就是留给对方一枚棋子，对方不取也得取。
所以想赢的关键就在于能不能取到倒数第二枚棋子。
问题转化为：每次取 1~n 个棋子，总数，取倒数第二枚棋子赢。
（总数-1）÷（1+n），之后同 1 中做法。
二．抢占制胜点（倒推法） 1. 能一步到棋子的位置均是不能走的地方即负位 2. 处处为别人着想。
自己不能走的地方逼别人走进去即可，即确定制胜点。
三．对称法 1. 同等情况下，模仿对方步骤可以达到制胜目的。
2. 不同等情况下，创造对等局面方可制胜。
1. 桌子上放着 100 根火柴，甲、乙二人轮流每次取走 1～5 根。
规定谁取走最后一根火柴谁获胜。
如果双方都采用最佳方法，甲先取，那么谁将获胜分析：100÷（1+5）=16??4 有余数，先拿必胜，甲必胜。
（1）甲先拿 4 个；（2）乙拿 a 个，甲就拿 6-a 个2. 甲乙两人轮流报数，报出的数只能是 1～7 的自然数。
同时把所报数一一累加起来，谁先使这个累加和达到 80，谁就获胜。
请问必胜的策略是什么分析： 80÷（1+7）=10 无余数，后拿必胜。
甲拿 a 个，乙就拿 8-a 个必胜3. 1000 个空格排成一行，最左端空格中放有一枚棋子，甲先乙后轮流向右移动棋子，每次移动 1～7 格。
规定将棋子移到最后一格者谁赢。
甲为了获胜，第一步必须向右移多少格分析：（1000-1）÷（1+7）=124??7 有余，先走必胜。
（1）甲先走 7 格（2）乙走 a 格，甲就拿8-a 个必胜4. 5 张扑克牌，每人每次只能拿 1 张到 4 张。
第七讲必胜策略问题例1．甲乙二人轮流报数。
从1起，每人每次可报一个数或连续报两个数。
谁能报得20谁就获胜。
先和同学玩一玩这个游戏。
如果由你先报数，你能保证获胜吗？练习1、一堆糖果共有10颗，两人轮流从中拿走1颗或2颗，谁拿到最后一颗糖果谁就获胜。
想一想：如果让你先拿，第一次应该那几颗才能确保获胜？2．甲乙二人轮流报数。
从1起，每人每次可报一个数或连续报两个数。
谁能报得50谁就获胜。
先和同学玩一玩这个游戏。
如果由你先报数，你能保证获胜吗？例2．甲乙二人轮流报数。
从1起，每人每次最多可以连续报3个数。
谁能报得30谁就获胜。
练习1．甲乙二人轮流报数。
从1起，每人每次最多可以连续报4个数。
谁能报得100谁就获胜。
怎样保证获胜？2.轮流报数，每次报出的数不能超过5，也不能是0，把两个人报出的数连加起来，谁报数后使和为25，谁就获胜。
如果让你先报数，为了确保获胜，你第一次应该报几？接下来该怎马报？例3．按照例1的报数方法，如果先报“20”的一方失败，怎样保证获胜？练习1．甲乙二人轮流报数。
从1起，每人每次最多可以连续报3个数。
谁报得30谁就失败。
怎样保证获胜？2、50个球，甲、乙两人进行取球比赛，规则是两人轮流各取一次，每人每次最少取1个，最多取5个，取到最后一个球的人就失败。
如果甲先取，他怎样去才能保证获胜？例4．两堆火柴，一堆16根，一堆11根。
甲乙两人轮流从中拿走1根或几根甚至一堆，但每次只能在某一堆中拿火柴，谁拿走最后一根谁取胜，问甲如何才能取胜？练习：1、有两个箱子分别装有63、108个球。
甲、乙两个轮流在任一箱中任意取球，规定取得最后一个球的为胜。
甲先取，他应该如何取才能获胜？2、三堆火柴，一堆8根，一堆11、还有也是8根，甲乙两人轮流从中拿走1根或几根甚至一堆，但每次只能在某一堆中拿火柴，谁拿走最后一根谁取胜，问甲如何才能取胜？例题5新年运动会时，举行四年级乒乓球团体赛，每人打一场，如果你是体育委员，你能安排好四（3）班必胜吗？练习：1. 新年运动会时，举行四年级跳绳团体赛，每人比一场，如果你是体育委员，你能安排好四（3）班必胜吗？四（2）班代表队四（3）班代表队张明105个/分李文110个/分李维90个/分陈敏95个/分刘涛60个/分刘瑞75个/分2.玩扑克牌，比大小：出示两组扑克牌，分别是A组10、7、5和B组2、6、8请问选哪组会获胜？一定会获胜吗？如果选A组一定会获胜呢？家庭作业：1、棋盒中有100枚棋子，甲乙二人轮流从中取出棋子，每次最多可以取5枚，最少也要取1枚。
