取子游戏 博弈简单分析.doc

一局游戏在两个游戏人之间如下交替进行:游戏从一空堆开始。当轮到一个游戏人时,他可以往堆中加进1,2,3或4枚硬币。往堆中加进第100枚硬币的游戏人为得胜者。确定在这局游戏中是游戏人A还是游戏人B能够确保取胜。取胜的策略是什么?在学术论坛有博士家园,组合图论论坛确保取足5个硬币即可例题:两个人玩移火柴的游戏,桌子上有1000根火柴,每个人停次可以拿走1-7根火柴,拿走桌了上最后那根火柴的算输,问第一个人第一次要拿多少根火柴才能保证赢7根。以后对方拿几根,你都要拿够凑足8根的数。1000根和8根性质是一样的。从抢30到NIM游戏的取胜策略(-)倒推法抢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是两个报数者年内能够报出的最大数与最小数的和。在类似游戏中,我们把游戏者所能用到的最大数和最小数之和称之为关键因子k,关键数就是k的倍数在抢30的游戏中,关键因子k等于3。又例如,抢100报数游戏中,如果每人可报数为1至9个连续的自然数,谁先报到100谁就是胜利者。•报最小数1的和,即k=10o报数获胜的策略就是:(1)让对方先报数;(2)每次报数为关键因子减去对方所报数。这样自己每次所报数都是关键数。如果对方一定要先报,你只能期待对方不懂策略或者大意出错了。(三) 不平衡因子在上述的抢30或者抢100的游戏中,最后数30是关键因子3的整数倍,最后数100是关键因子10的整数倍。我们可以把这样的游戏称为平衡游戏,也就是最后报数与关键因子相除余数为0。如果最后报数与关键因子相除有余数,这个游戏就可以称为不平衡游戏,其余数就是不平衡因子。抢数不平衡游戏也是不公平的游戏,先报数者有必胜策略。先报数者的获胜策略就是先消除不平衡因子,使其变成一个平衡游戏,先报数者随后就成为平衡游戏的后报数者。例如,在抢30游戏中,两人从1开始轮流报数,每人每次可报1到3个连续的数,谁先报到30,谁就为胜方。在这里,关键因子是4,不平衡因子是2。又例如,抢100报数游戏中,如果每人可报数为1至10个连续的自然数,谁先报到100谁就是胜利者。在这里,关键因子是11,不平衡因子是1。在不平衡游戏中,如果先报数者不懂得游戏策略,懂得这个策略的后报数者需要不断计算不平衡因子,以便最后获胜。(四) 更多例子报数游戏里的最后数都是些比较小的数,因此用倒推法比较容易得到策略。当我们把数变得大一些的时候,就变成了小学奥赛题。如果掌握上述讨论中的美键因子和不平衡因子的计算,奥数题也变得迎刃而解了。下面就是两个奥数例题。(1) 2008个空格子排成一■排