1、第十讲 游戏策略 对策论又称博弈论，研究的现象与政治、经济、军事乃至人们的日常生活学 习都有密切的联系一般地，在具有竞争或对抗性质的行为中，参加竞争对抗的 各方具有不同的目标为了达到各自的目标，各方既要制定出对自己最有利的方 案， 又要考虑到对手所有可能采取的方案对策论就是研究竞争对抗中各方是否 存在最佳行动方案，以及如何找到这个最佳方案 我们将要学习的对策问题， 主要是研究在两人的游戏过程中如何使自己取胜 的策略问题如果说“统筹规划”所研究的是“死的”对象的话，那么“对策问 题”所研究的就是一个“活的”对手，因而在考虑问题时需要设想对手可能采取 的各种方案，并使己方的策略能在对手所有可能采取
2、的方案中都处于有利位置， 我们将这种状态称作“必胜状态” （否则称为“必败状态” ） 那么在给定的游戏 规则下，是否存在必胜状态，以及为了达到必胜状态所采取的策略就成了问题的 关键 需要强调的是，我们的目标不是“可能胜” ，而是“必胜” ！我们不能存在侥 幸心理，不能寄希望于对方的失误，而是要在假定双方都足够聪明的前提下寻找 必胜策略 例题 1 有 12 枚棋子，甲、乙两人轮流取，规定甲先取，每人每次至少取 1 枚， 最多取 3 枚 如果谁取走最后一枚棋子谁赢， 那么谁有必胜策略？ 如果谁取走最后一枚棋子谁输，那么谁有必胜策略？必胜策略是什 么？ 分析分析直接考虑 12 枚棋子并不容易，大家不
3、妨试试棋子较少时谁有必胜策略， 看看能否找到规律 练习 1 有 15 枚棋子，甲、乙两人轮流取，规定甲先取，每人每次至少取 1 枚，最 多取 2 枚如果谁取走最后一枚棋子谁赢那么谁有必胜策略？如果谁取走最后 一枚棋子谁输，那么谁有必胜策略？必胜策略是什么？ 情况很复杂时，我们往往需要先从比较简单的情况开始尝试，在逐渐变复杂 的过程中，寻找规律进而解决题目这其实是一种非常重要的数学思想，高年级 乃至往后的数学学习中应用的递推、数学归纳法等都是以此为基础的 利用互补的想法，我们有更一般的结论 “有 m 枚棋子，两人轮流取棋子， 规定每人每次可以取走 1 至 n 枚，直到把棋子取完为止，谁取得最后的
4、一枚棋子 谁胜 ”其取胜策略是：每次取走棋子数除以1n的余数枚棋子，让对方面对 1n的倍数枚棋子必败状态，则可保证取到最后的一枚棋子而获胜 例题 2 现有 2014 根火柴甲、乙两个人轮流从中取出火柴，规定甲先取， 每人每次至少从中取出 2 根，最多取出 4 根如果谁无法取出火柴谁 就赢，请问谁一定能赢？策略是什么？ 分析分析本题中每人每次最少要取出 2 根火柴，如果恰好剩下 1 根火柴，就已经 无法再次取出了能否像例题 1 那样，从火柴较少的情况入手，找出规律呢？ 练习 2 现有 2009 个糖豆，甲、乙两个人轮流取从中出糖豆，每次至少从中取出 2 个，最多取出 5 个，谁无法取出糖豆谁就赢
5、如果甲先取，请问谁一定能赢？策 略是什么？ 在一定能分出胜负的对策问题中，一方要么处于必胜状态，要么处于必败状 态 处于必胜状态的一方， 总能进行一次适当的操作后， 把必败状态留给对手 反 之，处于必败状态的一方，无论采取什么策略，都只能把必胜状态留给对手 在很多对策问题中，具有对称性的状态往往是解决问题的关键 例题 3 甲、乙两人玩一个游戏：有两堆小球，甲、乙两人轮流从中取球，每 次只能从同一堆中取， 个数不为零即可 规定取到最后一个球的人赢， 甲先取球如果开始时两堆分别有五个球和八个球，那么谁有必胜策 略？请说明理由 分析分析直接考虑 5 个和 8 个并不容易，你能像之前一样，从最简单的情
6、况开始 分析，找到规律吗？ 练习 3 甲、 乙两个海盗分金币： 有两堆金币， 一堆有 2009 枚， 一堆有 2014 枚 甲、 乙轮流从中拿金币，每次只能从同一堆中拿，个数不为零即可规定拿到最后一 枚金币的人获胜，胜者可以获得所有金币如果甲先拿，那么谁有必胜策略？请 说明理由 例题 4 如下图，方格 A 中放有一枚棋子，甲先乙后轮流移 动这枚棋子，只能向上、向右或向右上方沿 45角 走 1 步，最终将棋子走到方格 B 的人获胜请问： 谁一定能获胜？必胜策略是什么？ 分析分析在棋盘中，有一些是必胜格，有一些是必败格一方想要获胜，必 须每次都把棋子走到必胜格子中，使得对手下一步无论采取什么操作，
7、都不得不 进入必败格子本题中方格 B 就是必胜格那么其他的格子中哪些是必胜格？ 哪些是必败格？ 练习 4 如右图，方格 A 中放有一枚棋子，甲先乙后轮流移动 这枚棋子，只能向上、向右或向右上方沿 45角走 1 步， 最终将棋子走到方格 B 的人获胜请问：谁有必胜策略？ 必胜策略是什么？ 例题 5 如下图，方格 A 中放有一枚棋子，甲先乙后 轮流移动这枚棋子，只能向上、向右或向右 上方沿45角走 1 步， 最终将棋子走到方格 B 的人获胜请问： （1）谁一定能获胜？必胜策略是什么？ （2）如果每次允许往同一方向（上、右或 右上）走任意多步，结果又如何呢？ 分析分析第（1）问中，每次只能走 1 步
8、，那么B为必胜格，则它相邻的左、 下、左下三个格子全是必败格；第（2）问中，每次可以走任意多步，那么B为 必胜格，则由B可以直接找出多少个必败格呢？ B A B A B A 例题 6 桌上有一块巧克力，它被直线划分成 3 行 7 列的 21 个小方块，如图 所示 现在让你和对手进行一种两人轮流切巧克力的游戏， 规则如下： 每人每次只许沿一条直线把巧克力切成两块； 拿走其中一块，把另一块留给对手再切； 不断重复前两步， 最后谁能恰好留给对手一个小方块， 谁获胜 如果你首先切巧克力，那么你第一次应该切走多少个小方块，才 能保证自己最后获胜？ 分析分析直接分析并不容易， 还是先来看看简单情况吧！ 如
9、果只有一行或一列的小方块，谁会获胜？两行或两 列呢？你能发现什么规律呢？ 在对策问题中，要想取得胜利，必须使自己能始终保持在必胜状态中，而使 对手总是处于必败状态明确了这一点，我们就知道了解决对策问题的关键在于 弄清楚什么是必胜状态，什么是必败状态 “知己知彼，百战不殆 ”哪一方的策 略更胜一筹，哪一方就会取得最终的胜利 课堂内外 田忌赛马 田忌很喜欢赛马有一回他和齐威王约定，进行一次比赛 将马分成上、中、下三等，比赛的时候，上等马对上等马，中等马对中等马， 下等马对下等马由于齐威王每个等级都比田忌的强，三场比下来，田忌都失败 了田忌觉得很扫兴，垂头丧气地准备离开赛马场 这时，田忌发现，他的好
10、朋友孙膑也在人群里孙膑招呼田忌过来，拍着他 的肩膀，说：“从刚才的情形看，齐威王的马比你的马快不了多少呀” 孙膑还没说完，田忌瞪了他一眼，说：“想不到你也来挖苦我！” 孙膑说：“我不是挖苦你，你再同他赛一次，我有办法让你取胜” 田忌疑惑地看着孙膑：“你是说另换几匹马？” 孙膑摇摇头，说：“一匹也不用换” 田忌没有信心地说：“那还不是照样输！” 孙膑胸有成竹地说：“你就照我的主意办吧” 齐威王正在得意洋洋地夸耀自己的马， 看见田忌和孙膑过来了， 便讥讽田忌： “怎么，难道你还不服气？” 田忌说：“当然不服气，咱们再赛一次！” 齐威王轻蔑地说：“那就来吧！” 一声锣响，赛马又开始了 孙膑让田忌先用
11、下等马对齐威王的上等马，第一场输了 接着进行第二场比赛孙膑让田忌拿上等马对齐威王的中等马，胜了第二 场齐威王有点儿心慌了 第三场，田忌拿中等马对齐威王的下等马，又胜了一场这下， 齐威王目瞪口呆了 比赛结果，田忌胜两场输一场，赢了齐威王 还是原来的马，只调换了一下出场顺序，就可以转败为胜 作业 1. 10 枚正面朝下的硬币排成一排放在桌子上，两个小朋友玩翻硬币游戏规定：每人每 次只能翻动一枚或两枚硬币使之正面朝上，翻过的硬币不能再翻两人轮流翻硬币，翻 动最后一枚硬币的人获胜请问：谁有必胜策略？必胜策略是什么？ 2. 现有 200 个石子甲、乙两个人轮流从中取出石子，每次最少从中取出 2 个，最多
12、取出 4 个，谁无法取出石子谁就赢如果甲先取，那么谁有必胜的策略？必胜策略是什么？ 3. 甲、乙两人玩一个游戏：有两堆小球，甲、乙两人轮流从中取球，每次只能从同一堆中 取任意多个，但不能不取规定取到最后一个球的人输，甲先取球 （1）如果开始时两堆各有两个球，那么谁有必胜策略？请说明理由； （2）如果开始时两堆分别有两个球和三个球，那么谁有必胜策略？请说明理由 4. 甲、乙二人轮流在一个正十二边形中画对角线（即两个不相邻顶点的连线） 规定新画 的对角线不能与已经画出的对角线相交，谁不能继续画谁输甲先画，请问谁有必胜策 略？必胜策略是什么？ 5. 如下图所示，方格 A 中放有一枚棋子，甲先乙后轮流
13、移动这枚棋子，只能向上、向右 或向右上方沿45角走 1 步，最终将棋子走到方格 B 的人获胜请问：谁一定能获胜？ 必胜策略是什么？ B A 第十讲 游戏策略 1. 例题 1 答案： （1）乙有必胜策略； （乙有必胜策略； （2）甲有必胜策略）甲有必胜策略 详解： （1）如果剩不到 4 枚棋子，先取的人把所有棋子取走后获胜；如果剩 4 枚棋子，无论先 取的人如何取，所剩的棋子数都不到 4 枚，所以后取的人获胜；如果有 12 枚棋子，甲取 1 枚时 乙取 3 枚，甲取 2 枚时乙取 2 枚，甲取 3 枚时乙取 1 枚，在每次甲取完后，乙可以取适当数量 的棋子以保证两人一个回合共取 4 枚棋子，这样
14、乙可以拿到最后 1 枚，乙胜 （2）如果剩 1 枚，那么先取的人必败；如果剩 2 至 4 枚，先取的人可以剩 1 枚不取，所以后取 的人败12 枚的情况与 4 枚的情况类似，甲先取 3 枚，剩下 9 枚之后乙取 1 枚时甲取 3 枚， 乙取 2 枚时甲取 2 枚，乙取 3 枚时甲取 1 枚，甲保证两人一个回合共取 4 枚棋子最后 1 枚必 然被乙拿到，甲胜 2. 例题 2 答案：甲有必胜策略 详解：根据上题经验，第二个人总可以保证和第一个人共取 6 根火柴，201463354，所 以 2014 根火柴的情况与 4 枚火柴的情况相同4 枚火柴时甲先取 2 根火柴即可获胜，因此 2014 根火柴时
15、甲也先取 2 根火柴，之后乙无论怎么取，甲再取时都可以保证两人一个回合共取 6 根 火柴2014263352，最后剩下的 2 根火柴留给了乙，甲无法取出火柴，甲获胜 3. 例题 3 答案：甲必胜 详解：甲先从 8 个球的那堆中取出三个球，使得两堆球一样多之后每次乙取几个球，甲就在 另一堆中取相同数量的球，甲获胜 4. 例题 4 答案：甲必胜 详解：我们给必胜格子（如方格 B）标记“” ，给必败格子标记“” 从方格 B 逆推，能一 步走到 B 的格子都要标记“” 特别地，最上边一行和最右边一列为“”和“”相间的标 记，如左图对于左图中的格子 1 和格子 3，对方有办法把它移到必胜格子中，所以格子
16、 1 和格 子 3 都是必败格子如果把棋子移到格子 2 中，对手无论怎么移，都只能移到必败格子中，因 此格子 2 是必胜格子用类似的方法分析，得到右图因此甲有必胜策略，每次把棋子移到标 有“”的格子中即可 5. 例题 5 答案： （1）甲必胜； （2）甲必胜 详解： （1）我们给必胜格子（如方格 B）标记“” ，给必败格子标记“” 从方格 B 逆推， B B 1 2 3 A 能一步走到 B 的格子都要标记“” 特别地，最上边一行和最右边一列为“”和“”相间 的标记，如左图对于左图中的格子 1 和格子 3，对方有办法把它移到必胜格子中，所以格子 1 和格子 3 都是必败格子如果把棋子移到格子 2
17、 中，对手无论怎么移，都只能移到必败格子中， 因此格子 2 是必胜格子用类似的方法分析，得到右图因此甲有必胜策略，每次把棋子移到 标有“”的格子中即可 （2）与第（1）问方法类似，得到下图甲有必胜策略，每次把棋子移到标有“”的格子中 即可 6. 例题 6 答案：切走 12 个小方块 详解：当只剩 1 行（或 1 列）时，但不是一个小方块，先切的人只要切剩下一个小方块就赢了 当剩 2 行（或 2 列）时，如果剩2 2的方块，那么先切的人切完后成为1 2的方块，所以后切 的人必胜；如果剩23、2 4、等情况，先切的人只要切剩下一个2 2的方块就可以取胜 当剩 3 行（或 3 列）时，如果剩3 3的
18、方块，先切的人切一刀后只能剩下1 3或23的方块， 此时后切的人获胜 当有37块时，先切的人切走3 412块，给对手留下一个3 3的正方形，接着每次都给对手 留下一个1 1或2 2的正方形即可获胜 7. 练习 1 答案： （1）乙必胜； （2）甲必胜 详解： （1）甲取 1 枚时乙取 2 枚，甲取 2 枚时乙取 1 枚，乙只要保证两人一个回合共取 3 枚棋 子，即可拿到最后 1 枚获胜 （2）甲先取 2 枚，剩下 13 枚之后乙取 1 枚时甲取 2 枚，乙取 2 枚时甲取 1 枚，甲保证两人一个回合共取 3 枚棋子，最后 1 枚必然被乙拿到，甲胜 8. 练习 2 答案：甲必胜 详解：20092
19、5287，甲先取 5 个糖豆，之后乙无论怎么取，甲再取时都可以保证两人一 个回合共取 7 个糖豆，最后剩下的 2 个糖豆留给了乙，甲无法再次取出糖豆，甲获胜 B 1 2 3 A B A B A 9. 练习 3 答案： 甲必胜 简答：甲先从 2014 个金币中取出 5 个金币，使两堆金币一样多之后每次乙拿几个金币，甲就 在另一堆中拿相同数量的金币，最后肯定甲拿走最后一个金币，甲获胜 10. 练习 4 答案： 甲必胜 简答：策略是每次把棋子走到下图中标有“”的格子内 11. 作业 1 答案：先翻动的人必胜 简答：先翻硬币的小朋友翻 1 枚硬币，以后对手翻 1 枚时自己翻 2 枚，对手翻 2 枚时自
20、己翻 1 枚，保证两人一个回合共翻 3 枚，即可保证自己翻到最后 1 枚 12. 作业 2 答案：乙必胜 简答：甲取 2 个乙就取 4 个，甲取 3 个乙也取 3 个，甲取 4 个乙就取 2 个2006332， 最后剩下 2 个石子，甲取完，乙无法再取，乙获胜 13. 作业 3 答案： （1）乙必胜； （2）甲必胜 简答： （1）甲取 1 个乙就取 2 个，甲取 2 个乙就取 1 个 （2）必胜策略是从三个球的那堆中取 1 个球，之后乙取 1 个甲就取 2 个，乙取 2 个甲就取 1 个 14. 作业 4 答案：甲必胜 简答：策略是先画一条经过正十二边形中心的对角线，以它为对称轴，把图形分成对称的两部 分之后乙每画一条对角线，甲就在对称的位置上画出对角线最后肯定是乙不能继续画，甲 胜 15. 作业 5 答案：乙必胜 简答：策略是每次把棋子走到下图中标有“”的格子内 B A B A
