资源描述：
《取子游戏 博弈简单分析.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一局游戏在两个游戏人Z间如下交替进行：游戏从一空堆开始。当轮到一个游戏人时，他可以往堆中加进1,2,3或4枚硬帀。往堆中加进第100枚硬帀的游戏人为得胜者。确定在这局游戏屮是游戏人A还是游戏人B能够确保取胜。取胜的策略是什么？在学术论坛有博十家园，纟fl合图论论坛确保取足5个驶币即可例题：两个人玩移火柴的游戏，桌子上有1000根火柴，每个人毎次可以拿走1・7根火柴，拿走桌了上最示那根火柴的算输，问第一个人第一次要拿多少根火柴才能保证赢7根。以后对方拿儿根，你都要拿够凑足8根的数。1000根和8根性质是一样的。从抢30到NIM游
2、戏的取胜策略（-）倒推法抢30是我国民间的一个两人游戏，具有很强的对抗性和娱乐性。抢30游戏通常有两种玩法。（1）两人从1开始轮流报数，每人每次可报-•个数或两个连续的数，谁先报到30,谁就为胜方。（2）两人从1开始轮流报数，每人每次可报一个数或两个连续的数，同时把两个人报出的所有数累加，谁先使这个累加数最先达到30,谁就为胜方。解决最个问题的一般策略是用倒推法。以（1）为例,要抢到30,必须抢到27；要抢到27,必须抢到24。如此倒推回去，可得到一系列关键数30、27、24、21、18、……9、6、3。根据以上分析，抢30游
3、戏本身并不是一•个公平的游戏，初始数和先后顺序己经决定了最后的结果，因为只有后报数者才能抢到3的倍数，后报数者有必胜策略。（二）关键因子所有这些关键数都是3的倍数。3是两个报数者年内能够报出的最大数与最小数的和。在类似游戏小，我们把游戏者所能用到的最大数和最小数Z和称Z为关键因子k,关键数就是k的倍数・。在抢30的游戏屮，关键因子k等于3。又例如，抢100报数游戏中，如果每人可报数为1至9个连续的自然数，谁先报到100谁就是胜利者。这里的关键因子k就是可报最犬数9和可报最小数1的和，即210。报数获胜的策略就是：（1）让对方先
4、报数；（2）每次报数为关键因子减去对方所报数。这样自己每次所报数都是关键数。如果对方一定要先报，你只能期待对方不懂策略或者大意出错了。（三）不平衡因子在上述的抢30或者抢100的游戏屮，最后数30是关键因子3的整数倍，最后数100是关键因子10的整数倍。我们可以把这样的游戏称为平衡游戏，也就是最后报数与关键因子相除余数为0。如果最后报数与关键因子相除有余数，这个游戏就可以称为不平衡游戏，其余数就是不平衡因子。抢数不平衡游戏也是不公平的游戏，先报数者有必胜策略。先报数者的获胜策略就是先消除不平衡因子，使其变成一个平衡游戏，先报数
5、者随后就成为平衡游戏的后报数者。例如，在抢30游戏屮，两人从1开始轮流报数，每人每次可报1到3个连续的数，谁先报到30,谁就为胜方。在这里，关键因子是4,不平衡因子是2。又例如，抢100报数游戏屮，如果每人可报数为1至10个连续的自然数，谁先报到100谁就是胜利者。在这里，关键因子是11,不平衡因子是1。在不平衡游戏屮，如果先报数者不懂得游戏策略，懂得这个策略的后报数者需要不断计算不平衡因子，以便最后获胜。（四）更多例子报数游戏里的最后数都是些比较小的数，因此用倒推法比较容易得到策略。当我们把数变得大一些的n寸候，就变成了小学
6、奥赛题。如果掌握上述讨论屮的关键因子和不平衡因子的计算，奥数题也变得迎刃而解了。下面就是两个奥数例题。（1）2008个空格子排成一排，第一格放有一个棋子。两人做游戏，轮流移动这枚棋子。每个人每次可前移1到5个格子，谁先把棋子移到最后一格，谁就是获胜者。问怎样的策略才能保证获胜。（2）桌JL放着一•堆火柴，共有5000根。两个人轮流从屮取火柴，每人每次取的火柴根数为1到8根，谁取了最后一根谁就输。问怎样的策略才能保证获胜。（五）进一步扩展到NIM游戏抢30的游戏是屮国NTM游戏（也叫筹码游戏）的一种特例。NIM游戏的一种经典表述
7、为：有n堆火柴，每堆各有若干根。两人轮流取出火柴，每次取出的根数不限但至少取1根，每次也只能从1堆里取火柴。谁最后把火柴取完，谁就是获胜者。问如何才能保证获胜。获胜策略已由美国数学家C.L.Bouton分析完成，用到的是二进制和平衡状态概念。其结论是：如果一开始火柴的总根数转化成二进制后各位数上的数字和都是偶数时，则是平衡状态，后取者必胜。最简单的平衡态是（1,1）,即2堆火柴，每堆各1根。如果开始吋火柴的状态处于不平衡状态，先取者必胜，其策略是取完后使火柴根数保持为平衡状态。最简单的不平衡态是（1）,即1根火柴。例如，2堆火
8、柴数都为2根，二进制记为（10,10）,各位数Z和为20,这是一个平衡态，则后取者必胜。3堆火柴数分别为1根、2根、1根，二进制记为（1,10,1），各位数之和为12,这不是一-个平衡态。先取者先取掉屮间一堆2根火柴，变成平衡状态（1,1）,则先取者必胜。下面的一道例题，可以
