时间：2022-09-09 10:37:43
【摘 要】博弈论是研究如何用最小的代价获得最大的收益的一种策略。实际上它就是一个“选择与放弃”的过程。在数千年的历史中，每一次博弈都是一次智慧的较量，为后人留下了宝贵的财富。通过研讨它们，我们可以掌握人生中的生存法则，选择最佳的成功之道。本文讨论的就是一道博弈题。
【关键词】轮流报数;博弈;必胜策略
题目：Yipeng的奶牛很聪明，因为yipeng经常给他们出智力游戏。Yipeng的奶牛最经常玩得游戏是一个博弈问题。首先yipeng会给奶牛们一个数n，这个数可能很大但肯定可以用31位整数表示。现在选两个奶牛出来，轮流报数，但是每次报的数只能从2到9中选取，每次报完数都会把结果累加，如果某个奶牛报完数恰好使累加和大于或等于n，则这头奶牛获胜。假设两头奶牛都足够聪明，都会按对自己最有利的方式报数，现在的问题是，如果给定n，这两头奶牛谁有必胜策略，是先手胜出还是后手胜出。
题目摘自：cs.scu.省略/soj/problem.action?id=2432
一．题解
设先手奶牛为Ａ，后手奶牛为Ｂ。（以下中括号表示区间，两边都可取到)
（1）当n∈[2，9]时，A取得胜利。
（2）当n∈[10，11]时，由于A只能取2到9的数， B取数时必有和A累加和（用sum表示)sum>=11,B必胜。
（3）当n∈[12，20]时只要A取后数属于[10,11]，问题转化为（2），只是换成B先选，则A必胜。
（4）当n∈[21，22]时无论A取什么，B取后都可以使得剩下的值在区间[10,11]之间；问题转化为（3），B必胜。
（5）由上面可以得出猜想：
I:n=11*x，或11*x-1时（其中x为大于等于1的自然数），B必胜；
II:n∈[11*x-9,11*x-2]，A必胜。
（6）证明：当x=1时转化为（1）情况，命题成立。
设当x=k时成立。n=11*k，或11*k-1时（其中k为大于等于1的自然数），B必胜，其他情况，A必胜。
当x=k+1时，若为情况I:n=11*k+11,或11*k+10。
由于A只能取得2到9的数，B也是，那么B取后总能使得两人取得的数为11.这样n=11*k+11-11=11*k或11*k-10;
即x=k+1时B也必胜，所以由数学归纳法知：n=11*x，或11*x-1时（其中x为大于等于1的自然数），B必胜。
若为情况II：n不等于11*k+11,或11*k+10。那么只要A取后使得n=11*k,或11*k-1。
那么便相当于B先取，而n=11*k,或11*k-1。由I得结论知A必胜。
综上所述：n=11*x，或11*x-1时（其中x为大于等于1的自然数），B必胜，其他情况，A必胜。
证完。
二．现在要讨论的问题是如果2到9变成了a到b,其中a,b∈N+（a
依旧设先手奶牛为Ａ，后手奶牛为Ｂ。
（1）当n∈[a,b]时,那么A必胜。
（2）n∈[b+1,b+a]时，由于A只能取[a，b]中得一个数，取后所得值处于[1,a],所以B取后必有sum>=n,所以B必胜。
（3）n∈[b+a+1,2*b+a]时， A 取后可使得n∈[b+1,b+a]，变为情况（2），但是B先取，胜负相反，于是A必胜。
（4）n∈[ 2*b+a+1,2*（b+a) ] A取后B再取，必能保证两人取得和为a+b ,再轮到A取时，情况便是（2）,即是B必胜。
（4）有了（一）中讨论的思想，便可猜想n∈[（b+a）*k-a+1,（b+a)*k ]时，B必胜，其他情况，A必胜。
（5）证明（4）中的猜想：
先设a,b,x∈N+（a
I:n∈[（b+a）*x-a+1,（b+a)*x ]时，B必胜；
II:n∈[（b+a）*（x-1)+1,（b+a)*（x-1)+b ]时，A必胜。
证明：当x=1时转化为（1）情况，命题成立。
设当x=k时成立。即i:n∈[（b+a）*k-a+1,（b+a)*k ]时，B必胜；ii:n∈[（b+a）*（k-1)+1,（b+a)*（k-1)+b ]时，A必胜。
当x=k+1时，若为情况I: 则有n∈[（b+a）*（k+1）-a+1,（b+a)*（k+1）],由于A只能取得a到b的数，B也是，那么B取后总能使得两人取得的数为（a+b）.这样在区间[（b+a）*（k+1）-a+1,（b+a)*（k+1）]上取数后所得的区间便为[（b+a）*k-a+1,（b+a)*k ]，即x=k+1时B也必胜，所以由数学归纳法知：当n∈[（b+a）*x-a+1,（b+a)*x ]时，B必胜。命题I成立。
若为情况II：则有n∈[（b+a）*k+1,（b+a)*k+b ]。由于A可以取得a到b的数，那么A取后的n便有n∈[（b+a）*k-a+1,（b+a)*k ],问题转化为I，只是先手此时为B，而I已经证明有后手必胜的策略，所以当n∈[（b+a）*（x-1)+1,（b+a)*（x-1)+b ]时， A必胜。命题II成立。
综上所述：n=11*x，或11*x-1时（其中x为大于等于1的自然数），B必胜，其他情况，A必胜。
证完。
（6）有结论I:n∈[（b+a）*x-a+1,（b+a)*x ]时，B必胜；
II:n∈[（b+a）*（x-1)+1,（b+a)*（x-1)+b ]时，A必胜。
三．现在要讨论的是有多个人的问题，
先考虑3个人，就以原始问题为例。
（1）当n∈[2，9]时，A必胜。
（2）当n∈[10，11]时，B必胜。
（3）当n∈[12-18]时，若A想让B胜出，则可以一直取9，那么B胜出。若A想让C胜出，那么可以一直取2，那么C胜出。
因此在3个人时，处于某个数之后，胜负依赖于人的情感，离开了本文的主题。
由于多个人必包含有前三个人，胜负亦与数字n之外的因素有关，不谈。
四．本文讨论的内容至此为止。
【参考文献】
［１］朱震葆.非合作博弈论的基本体系――博弈论简介（三)[J].江苏统计,1998,03.
［２］安毅,杨忠直.博弈决策规则与认知闭合需要[J].软科学,2009,02.
［３］邹杰,何卫.非合作博弈模型的模糊构建与应用[J].重庆教育学院学报,2008,06.