基础博弈论

博弈论，又称对策论，是现代数学的一个分支，强调一个对策，看起来十分深奥，好像古代那些军师的计谋。的确，博弈论是一门非常深奥的学科，在生活中也有不少运用，但作为信息学奥赛选手，我们没有必要去专业的学习博弈论，只需要知道一些常见的博弈论以及它的结论和证明即可。

---

1、巴什博弈：

这是一个最常见的博弈论，我们小学都玩过。这个博弈讲的是有n个石子，两个人轮流取，每次至少要取一个，最多取m个，谁先取完谁胜，判断谁有必胜策略。

我们假设希望后手赢，那么最理想的状态就是，轮到后手取了，而剩下的石子数不超过m。记石子数为x，不难得出，这时候x的取值范围在1~m。那么，我们再往前推一步，先手还没取时x的取值范围应该在2~2m之间。但是，这里面并不是所有情况下我们都能保证后手必胜，这时候我们分别讨论它的两个边界：

①∵先手取完后剩下的石子数量必须大于0，得x-m>=1，即x>=m+1；

②∵先手取完后剩下的石子数量还不能大于m，得x-1<=m，即x<=m+1.

∴综上所述：x=m+1。也就是说，在一轮内后手必胜的情况当且仅当x=m+1。说明一下讨论的过程：我们的目的是想让后手在先手->后手这一轮内必胜，所以当先手肯定不能把石子取完，换句话说就是先手取完后剩下的石子数必须不小于1；但是，既然要保证在一轮内结束，先手->后手以后不能再有剩下的石子，换句话说就是先手取完后剩下的石子数不能超过m，于是就得出了我们的结论。

既然这样，那这个问题就变得很简单了：我们已经知道一轮内后手必胜的条件，那我们如果能使整个局面划分成很多这样的“一轮”，结果不就很明显了吗？如果n可以被m+1整除，那么后手就可以控制整个局面，只要每一轮取得石子与先手取的石子的和都保持在m+1，就相当于玩了很多轮，每轮都胜，最后必胜；反之，如果无法整除，那么先手的人就可以把n取到可以被m+1整除，然后，原来的后手就处于先手的位置上了，原来的先手扮演的角色就变成了后手，谁胜谁负不言而喻。

所以，巴什博弈的结论就是：如果n除以m+1余数为0，则后手必胜；否则先手必胜。

---

2、尼姆游戏：
尼姆游戏是一种两个人玩的回合制数学战略游戏。游戏者轮流从一堆棋子（一共有好几堆，一次只能从其中一堆拿）中取走一个或者多个，最后不能再取的就是输家。当然，这是最基本的尼姆游戏，在这个规则上可以加上五花八门的规则，使这个游戏更有趣味，思维也更加复杂。所以，我们会拿具体的例子来分析，也会随时拿新的规则来试玩。

（1）给出n堆石子，从1到n标号，每堆若干个。两个人轮流取石子，每次只能从有石子的，且标号最小的那一堆取石子，不能不取。取走最后一个石子的玩家获胜。
什么意思呢？假如说我有n堆石子，那我们两个人必须先把第一堆石子取完，才能取第二堆，取完第二堆才能取第三堆，取完第三堆才能取第四堆......

未完待续