第1讲：对弈问题课件.ppt

1、 有一种游戏被称为有一种游戏被称为“争抢三十争抢三十”，游戏规则是：两人轮流，游戏规则是：两人轮流报数，每人每次至少报报数，每人每次至少报1 1个数，最多报个数，最多报4 4个数，从个数，从1 1到到3030按顺序连按顺序连续报数，谁先报到续报数，谁先报到3030，谁就获胜。请给出取胜的方法。，谁就获胜。请给出取胜的方法。30（1+4）6米德，让你先报吧！米德，让你先报吧！30（1+4）6我只要使自己报的数我只要使自己报的数的个数与米德报的数的个的个数与米德报的数的个数保持和为数保持和为5。30 30（1+41+4）6 6制胜方法：制胜方法：（1）让对方先报数；（2）只要每次所报数的个数和对方

2、所报数的个数之和凑成5，即每次抢到5的倍数，这样就一定能抢到30。米德、阿派两人轮流报数，每人每次至少报米德、阿派两人轮流报数，每人每次至少报1 1个数，最多个数，最多报报5 5个数，从个数，从1 1到到180180，谁先报到，谁先报到180180，谁就获胜。请给出取胜，谁就获胜。请给出取胜的方法。的方法。18030 180 180（1+51+5）3030制胜方法：制胜方法：（1）让对方先报数；（2）只要每次所报数的个数和对方所报数的个数之和凑成6，即每次抢到6的倍数，这样就一定能抢到180。卡尔、阿派两人抓棋子，规定最多可以抓卡尔、阿派两人抓棋子，规定最多可以抓3 3个，个，最少抓最少抓1

3、1个，谁取到最后一个棋子就算输。若卡尔先个，谁取到最后一个棋子就算输。若卡尔先去抓，棋子数为去抓，棋子数为20012001个，问阿派是否有必胜的策略。个，问阿派是否有必胜的策略。2001500+1 200120014 4500+1500+1制胜方法：制胜方法：（1）让卡尔先抓；（2）只要每次取的个数与卡尔保持和为4就可以。双方各取500次之后，剩下最后一个棋子，卡尔不得不取走，卡尔输，故阿派必赢。盘子里有盘子里有8080粒珠子，阿尔法、欧拉两人每次轮流取走粒珠子，阿尔法、欧拉两人每次轮流取走1 1至至3 3粒珠子，谁能取完盘子里的珠子谁就获胜。如果双方都采取最粒珠子，谁能取完盘子里的珠子谁就获

4、胜。如果双方都采取最佳取法，阿尔法先取。那么获胜的一定是谁？佳取法，阿尔法先取。那么获胜的一定是谁？8020 80 804 42020获胜的一定是后取的欧拉：获胜的一定是后取的欧拉：（1）阿尔法先抓；（2）欧拉肯定可以保持与阿尔法取的个数和为4，双方各取19次后还剩下4粒珠，阿尔法无论拿几粒，欧拉都能拿完盘里的珠子。对弈问题主要研究下棋、报数等比赛，对弈问题主要研究下棋、报数等比赛，在这些活动中，参加竞争的双方都想获胜，在这些活动中，参加竞争的双方都想获胜，必须考虑对方可能怎样决策，从而选出一个必须考虑对方可能怎样决策，从而选出一个最好的对付策略。最好的对付策略。解决这类问题一般采用逆推法和归

5、纳法。解决这类问题一般采用逆推法和归纳法。游戏规则：游戏规则：两人轮流地往一张大的圆形卡纸上放一个圆形纸片不能重叠。谁贴完一个圆之后而使得对方无法再往大圆上贴纸片时，谁就是胜利者。博士、米德两人轮流地往一张圆桌面上放一枚五角硬币不博士、米德两人轮流地往一张圆桌面上放一枚五角硬币不能重叠。谁放完一枚之后而使得对方无法再往桌面上放硬币时，能重叠。谁放完一枚之后而使得对方无法再往桌面上放硬币时，谁就是胜利者。如果博士先放，博士有没有稳操胜券的策略？谁就是胜利者。如果博士先放，博士有没有稳操胜券的策略？我先放吧！我先放吧！答：博士有稳操胜券的策略。先在圆桌正中心放一枚硬币，答：博士有稳操胜券的策略。先

6、在圆桌正中心放一枚硬币，然后无论米德怎么放，只要放在与米德所放位置中心点对称然后无论米德怎么放，只要放在与米德所放位置中心点对称的位置上。博士一定获胜。的位置上。博士一定获胜。在一张大圆桌上放同样大小的碗，不能重叠，每次放一只，在一张大圆桌上放同样大小的碗，不能重叠，每次放一只，放到对方无法再放时，你就获胜。你先放，怎样放必胜？放到对方无法再放时，你就获胜。你先放，怎样放必胜？米德，你米德，你先放吧！先放吧！答：先放的人有稳操胜券的策略。先在圆桌正中心放一个碗，答：先放的人有稳操胜券的策略。先在圆桌正中心放一个碗，然后无论对方怎么放，只要放在与对方所放位置中心点对称然后无论对方怎么放，只要放在

7、与对方所放位置中心点对称的位置上。自己一定获胜。的位置上。自己一定获胜。有有2626根小棒如图放置。游戏规则为：从最下面一排右边开始根小棒如图放置。游戏规则为：从最下面一排右边开始按顺序取，两人轮流取。每人每次至少取按顺序取，两人轮流取。每人每次至少取1 1根，最多取根，最多取5 5根。且根。且下一排未取完之前不能取上一排，取到最后一根者胜。怎样取下一排未取完之前不能取上一排，取到最后一根者胜。怎样取才能取胜？才能取胜？26 4+2取胜方法：取胜方法：（1 1）自己先取；）自己先取；（2 2）再根据对方所取的数，使自）再根据对方所取的数，使自己所取数与对方所取数之和为己所取数与对方所取数之和为

8、6 6就就能取胜。能取胜。有有2424根小棒如图放置。游戏规则为：从最下面一排右边开根小棒如图放置。游戏规则为：从最下面一排右边开始按顺序取，两人轮流取。每人每次至少取始按顺序取，两人轮流取。每人每次至少取1 1根，最多取根，最多取5 5根。根。且下一排未取完之前不能取上一排，取到最后一根者胜。怎且下一排未取完之前不能取上一排，取到最后一根者胜。怎样取才能取胜？样取才能取胜？24 4 取胜方法：取胜方法：（1 1）对方先取；）对方先取；（2 2）再根据对方所取的数，使自）再根据对方所取的数，使自己所取数与对方所取数之和为己所取数与对方所取数之和为6 6就就能取胜。能取胜。方法三：方法三：对称型

9、规定：谁“无”路可走即为输办法：1、局面非对称抢先，将局面变为对称局面 2、局面已对称抢后，跟随对方方法一：方法一：倒推方法二：方法二：（1）找周期：周期等于可拿最大限度+1 （2）总数周期有余数：抢先拿余数整除（余数为0）：抢后1 1.20082008个空格子排成一排，两人做游戏，轮流移动一枚棋子，个空格子排成一排，两人做游戏，轮流移动一枚棋子，从第一格子开始，每个人每次可前移从第一格子开始，每个人每次可前移1 1到到5 5个格子，谁先把棋个格子，谁先把棋子移到最后一格，谁就是获胜者。问怎样的策略才能保证获子移到最后一格，谁就是获胜者。问怎样的策略才能保证获胜。胜。2008334+4 200

10、820086 6334+4334+4制胜方法：制胜方法：（1）我先移4格；（2）只要每次移的个数与对方保持和为6就可以。双方各移333轮之后，剩下最后六个格子，无论对方移几格，我总能把棋子移到最后一格。2.2.一些苹果如下图放置，游戏规则为：从最下面一排开始取，一些苹果如下图放置，游戏规则为：从最下面一排开始取，两人轮流取，个数不限，但不能不取，且下一排未取完前不能两人轮流取，个数不限，但不能不取，且下一排未取完前不能取上一排，取到最后一个者胜。让你先取，怎样取才能赢？取上一排，取到最后一个者胜。让你先取，怎样取才能赢？取胜方法：取胜方法：保证每一行我先拿，并且前保证每一行我先拿，并且前3 3

11、行，每一行只给对方留一个，最后行，每一行只给对方留一个，最后一行全部自己拿下。一行全部自己拿下。3.3.有这么一个报数的游戏，游戏规则如下：有这么一个报数的游戏，游戏规则如下：（1 1）两人轮流报数；）两人轮流报数；（2 2）每次报的数只能是）每次报的数只能是1 11010中的某一个数；中的某一个数；（3 3）谁报数后两人所报的全部数的和为）谁报数后两人所报的全部数的和为20032003，就算谁获胜。，就算谁获胜。如果让你先报，你应先报几才能保证获胜？为什么？策略如果让你先报，你应先报几才能保证获胜？为什么？策略是什么？是什么？2003182+1 2003 2003（1+101+10）182+1182+1制胜方法：制胜方法：（1）我先报1；（2）只要每次所报的数和对方所报数的和等于11，即保证每次加上他的数和为11的倍数，这样就一定能获胜。