组合游戏中的必胜策略

记得小学的时候，奥数课程里有一章叫作博弈问题，其中第一个问题就是经典的“报30”游戏。两个人从1开始轮流报数，每个人都只能报接下来的一个数或两个数。比如，第一个人可以报1，也可以报1、2；如果第一个人报了1、2，第二个人就可以选择报3或者报3、4……不断这样报下去，谁最先报到30谁就获胜。我还记得当时看完游戏分析之后的那种震撼感：这个看似有趣的游戏实际上非常无聊，因为后报数的人有一种非常简单的方法可以保证必胜。

我们可以从获胜条件出发，倒推出获胜之路上的关键点在哪里。由于最先报到30的人获胜，那么先报到27的人就一定可以获胜，因为对方报28我就报29、30，对方报28、29我就报30。由于先报到27的人可以保证获胜，根据同样的道理，先报到24的人就一定可以获胜了……不断这样推下去，最终得到的结论就是，先报到3的人一定必胜。于是，先报的人报1，后报的人就报2、3；先报的人报1、2，后报的人就报3。不管怎样，后报数的人都是必胜的。

这种类似的思想可以用于很多其他的博弈问题。考虑这样一个游戏：有10枚硬币，两人轮流从中拿走硬币，每次可以拿走1枚、2枚或者4枚，谁取到最后一枚硬币，谁就获胜。这个游戏同样是非常无聊的，因为先取者有必胜策略。它的推导方法则更具典型性，更能反映一般情况下的做法：

· 如果硬币的总数只有1枚，则先取者胜；

· 如果硬币的总数是2枚，则先取者胜；

· 如果硬币的总数是3枚，则先取者败，因为他不管取多少，对方面临的情形都是必胜的情形；

· 如果硬币的总数是4枚，则先取者胜；

· 如果硬币的总数是5枚，则先取者胜，他只需要取走2枚，对方将会被迫面临3枚的情形；

· 如果硬币的总数是6枚，则先取者败，因为他不管取多少，对方面临的情形都是必胜的情形；

· 如果硬币的总数是7枚，则先取者胜，他只需要取走1枚，对方将会被迫面临6枚的情形；

· 如果硬币的总数是8枚，则先取者胜，他只需要取走2枚，对方将会被迫面临6枚的情形；

· 如果硬币的总数是9枚，则先取者败，因为他不管取多少，对方面临的情形都是必胜的情形；

· 如果硬币的总数是10枚，则先取者胜，他只需要取走1枚，对方将会被迫面临9枚的情形。

上面两个游戏之所以都能用同一种分析方法，是因为它们都满足某些共同的条件。我们不妨试着把这些共同的条件抽象出来，从而建立一套适用范围更广的博弈游戏分析法。说白了，这类游戏本质上就是两名玩家轮流让棋局状态向某个终结点转移，谁先不能走了谁就输了。具体地说，这类游戏有这么三个共同的特征：首先，游戏当中的信息是完全透明的，每个人都知道对方可以怎么走（这就排除了斗地主、军棋之类的游戏）；第二，也是最重要的一点，就是下一步可以怎么走与下一步是谁走没关系，两名玩家的唯一区别就是谁先走谁后走（这就排除了象棋、围棋及所有区分棋子颜色的游戏）；最后，整个游戏必然会在有限步之后结束，谁先没走的谁就输了。在博弈论中，这类游戏叫作“无偏博弈”（impartial game）。

对于所有这类游戏，我们都可以像刚才那样，用“必胜态”、“必败态”来分析。如果对于某个棋局状态，谁遇到了它谁就有办法必胜，我们就把它叫作“必胜态”；如果对于某个棋局状态，谁遇到了它对手就会有办法必胜，我们就把它叫作“必败态”。根据定义可以立即判断出，那些不能走的状态就是必败态了。从这些必败态出发，我们可以按照下面两条规则，自底向上地推出其他所有状态的性质：有办法走到必败态的状态就是必胜态，只能走到必胜态的状态就是必败态。从这两条规则可以看出，一个状态不是必胜的就是必败的。因此，像这样不断推下去，我们最终会得出：初始状态要么是必胜的，要么是必败的。换句话说，整个游戏要么是先行者必胜，要么是后行者必胜。

无偏博弈不见得是线性的，也不见得是显性的。不妨一起看看下面这个我非常喜欢的经典例子。地上有 n 颗石子（假设 n ≥ 2），两个人轮流从中取出石子。规定：第一个人最少可以取走1颗石子，最多可以取走 n -1颗石子。今后，每个人取走的石子数量必须小于前一轮对方取走的石子数量的2倍（但必须取走至少1颗石子）。谁先取到最后一颗石子，谁就获胜了。比如说，当 n =4时，第二个人是有必胜策略的。如果第一个人取走了2颗石子或者3颗石子，第二个人可以在下一轮直接获胜；如果第一个人取走了1颗石子，这将立即使得今后每个人取石子时永远只能取1颗石子，第二个人必然会取到最后一颗石子，从而获胜。我们的问题是，对于哪些 n ，第二个人是必胜的？

这个游戏似乎不太符合刚才的模型，因为此时出现了一个刚才并没有涉及的情况：这一步能怎么走，要依赖于上一步是怎么走的。在这种情况下，我们似乎没法确定出状态与状态之间的转移关系。然而，只需要把“这次可以拿多少颗石子”的信息本身也纳入棋局状态里，游戏就变成纯粹的状态转移了。我们用( x , y )来表示现在还有 x 颗石子，并且玩家最多可以拿走其中 y 颗石子。当 n =4时，游戏的初始状态就是(4,3)，第一名玩家可以把这个状态变为(3,1)、(2,3)、(1,5)之一；如果第一名玩家把状态变成了(2,3)，那么第二名玩家可以把它继续变为(1,1)和(0,3)。谁先把状态变成了形如(0, y )的样子，谁就获胜了。

为了打印出当 n ≤ 100时哪些 n 能使第二名玩家必胜，我们只需要在Mathematica中写入三行代码，如图1所示。我们用True来表示一个状态是必胜态，用False来表示一个状态是必败态。函数 f 用于返回从( x , y )出发可以到达哪些状态，函数 g 则用于计算( x , y )是必胜的还是必败的。

结论非常出人意料：第二名玩家有必胜策略，当且仅当 n 是2的整数次幂！这究竟是为什么呢？下面就是一个漂亮的解释。

如果初始时石子个数不是2的整数次幂，那么石子个数的二进制表达中至少有两个数字1。第一名玩家的必胜策略就是，去掉石子个数的二进制表达中的右起第一个数字1。例如，如果石子个数为176（其二进制表达为10110000），第一名玩家的必胜策略就是拿走16颗石子，把石子个数变为160（其二进制表达为10100000）。第二名玩家无法仿照第一名玩家的做法，因为要想去掉石子个数的二进制表达中的右起再下一个数字1，需要拿走的石子数量至少是刚才第一名玩家拿走的石子数量的2倍。第二名玩家唯一能做的，就是把石子个数的二进制表达中末尾形如1000…00的部分变为0???…??，并且这些问号位置上的数字里至少有一个为1。比方说，在刚才的例子中，第二名玩家可以从160颗石子中拿走20颗石子，余下140颗石子，石子个数的二进制表达就从10100000变成了10001100。注意，第二名玩家拿走的石子数量是20，其二进制表达为10100，最后一个数字1在右起第3位。这决定了现在余下的石子个数的二进制表达中最后一个数字1也在右起第3位。因此，为了把这个数字1变为0，需要拿走的石子数量不会超过刚才第二名玩家拿走的石子数量（当然就更不会达到或超过它的2倍了）。所以，第一名玩家可以继续重复刚才的必胜策略。一旦第二名玩家留下的石子个数满足其二进制表达里只含一个数字1（比如把石子个数的二进制表达从1000变为10，或者最后迫不得已地把10变为1），第一名玩家就获胜了。

这个玄妙的结论鼓励我们继续探究下去。如果我们把游戏规则中的取走石子数量的上限“必须小于前一轮对方取走的石子数量的2倍”改成“必须小于等于前一轮对方取走的石子数量的2倍”呢？如图2所示，结果更加神奇：第二名玩家有必胜策略，当且仅当 n 是一个斐波那契数（Fibonacci number）！

为什么斐波那契数列会在这里出现？解释的大致方法和刚才相差不大，但细节更复杂一些，这里我们就不多说了。

在数学竞赛、编程竞赛和面试题当中，博弈问题往往有一些简洁而漂亮的解答。为了找出这个解答，有时可能要先用这种递推的办法做一下试验。在本文的最后，我们从易至难地给出3个小题目。我们的建议是，首先利用递推的办法尝试着列出游戏规模较小时的必胜态和必败态（用纸和笔也行，写一段代码也行），然后从中发现规律，最后想办法给出一个解释，从而给出一个完美的回答。如果你成功地找到了必胜态和必败态的规律，那么找出一个解释也就不难了：只需要说明每个必胜态确实可以导向某个必败态，并且每个必败态确实都只能导向必胜态即可。

不妨把游戏双方叫作A、B。先来看A、B两人玩的第一个游戏——掰巧克力。整板巧克力里面一共有10×10个小块。首先，A把巧克力掰成两个矩形，吃掉其中一块，把另一块交给B；B再把剩下的巧克力掰成两个矩形，吃掉其中一块，把另一块交回给A……两人就像这样轮流掰下去。规定，谁没法继续往下掰，谁就输。如果A先开始掰，A和B谁有必胜策略？这种策略是什么？

答案是，在这个游戏中，B有必胜策略。B只需始终保持巧克力是正方形的就行了。刚开始，巧克力是10×10的，A不管怎么掰，都会把它掰成一个长和宽不相等的矩形，B只需要把它再掰回正方形即可。比如，A把它掰成了7×10的巧克力，B就再把它掰成7×7的巧克力。不断这样下去，直到B把它掰成1×1的巧克力，此时A就输定了。在这个游戏中，我们可以用( m , n )来表示巧克力的两边之长分别为 m 和 n ，那么 m = n 时的所有状态就是必败态， m ≠ n 时的所有状态就是必胜态。

再来看看A、B两人玩的第二个游戏——吃糖果。桌子上放着两堆糖果，一堆里有50个糖果，一堆里有101个糖果。A、B轮流对这些糖果进行操作。在每一次操作中，操作者需要吃掉其中一堆糖果，只要另外一堆糖果的数量大于1个，他就必须把另外一堆糖果分成两堆（可以不相等）让对方继续操作。如果某人吃掉其中一堆糖果之后，发现另一堆里只有一个糖果，不用再分了，那么他就获得胜利。如果A先开始操作，A和B谁有必胜策略？这种策略是什么？

答案是，在这个游戏中，A有必胜策略。事实上，任何时刻，如果两堆糖果中有任何一堆的糖果数被5除余1、余4或正好除尽，那么此时的操作者就是必胜的。反之，如果两堆糖果的数目被5除余数都是2或3，那么此时的操作者就会输掉游戏。当游戏状态属于前者时，我们可以把糖果数被5除余1、余4或正好除尽的那一堆分成糖果数被5除余数都是2或3的两堆（这是总能办到的，除非该堆的糖果数就是1，而此时我们已经直接获胜了），而对方不得不把其中一堆糖果又分出新的糖果数被5除余1、余4或正好除尽的一堆留给我们操作。这样逼着对方总是面临必败的状态，使得最后对方不得不把2个糖果或者3个糖果分成两堆，从而让我们获得游戏的胜利。

最后，让我们一起来看看A、B两人玩的第三个游戏——拿石子。地板上有10堆石子，各堆里面的石子数量分别为1,2,…,10个。两个人轮流对这些石子进行操作，操作方式有两种：要么从某一堆石子中拿走一颗石子，要么把某一堆石子分成两个小堆。谁先没法继续操作（即石子被拿完），谁就输。如果A先走，A和B谁有必胜策略？这种策略是什么？

答案是，在这个游戏中，A是必胜的。事实上，我们会证明一个更一般的结论：满足下列两个条件之一的棋局都是必胜棋局：（1）只含一颗石子的有奇数堆；（2）含有偶数颗石子的有奇数堆。这种形式的棋局对于玩家是有利的，因为“有奇数堆”意味着至少有一堆，此时的玩家总能继续往下走。面对这种类型的棋局，我们的策略就是，把当前的棋局变为上述条件均不满足的棋局，即只含一颗石子的及含有偶数颗石子的都是偶数堆。这总是可以办到的。我们所面对的局势可以分成以下三类。

· 只含一颗石子的有奇数堆，含有偶数颗石子的有偶数堆。这样的话，我们把其中一个只含一颗石子的堆拿走就行了。只含一颗石子的堆数会减1，从而变成偶数；同时，含有偶数颗石子的堆数也仍然保持偶数不变。

· 只含一颗石子的有偶数堆，含有偶数颗石子的有奇数堆。如果能找到某个恰好含有两颗石子的堆，那就把它分成两堆，每堆各一颗石子；如果所有含有偶数颗石子的堆都含有两颗以上的石子，那就从中任选一堆，拿走其中一颗石子。这样一来，只含一颗石子的堆数会加2或者不变，因而仍然是偶数；含有偶数颗石子的堆数则会减1，从而变成了偶数。

· 只含一颗石子的有奇数堆，含有偶数颗石子的也有奇数堆。如果能找到某个恰好含有两颗石子的堆，那就从中拿走一颗石子；如果所有含有偶数颗石子的堆都含有两颗以上的石子，那就从中任选一堆，把它分成1加上某个大于1的奇数。这样一来，只含一颗石子的堆数会加1，因而变成了偶数；含有偶数颗石子的堆数则会减1，也变成了偶数。

于是，我们留给对方的局势将会满足这样的条件：只含一颗石子的有偶数堆，并且含有偶数颗石子的也有偶数堆。对方有以下四种选择。

· 选择某一个只含一颗石子的堆，把这颗石子拿走。这样的话，只含一颗石子的堆数就变成奇数了。

· 选择某一个含有偶数颗石子的堆，把其中一颗石子拿走。这样的话，含有偶数颗石子的堆数就变成奇数了。

· 选择某一个含有偶数颗石子的堆，把它拆成两堆石子，每一堆各含奇数颗石子。这样的话，含有偶数颗石子的堆数就减少了1，从而变成了奇数。

· 选择某一个含有偶数颗石子的堆，把它拆成两堆石子，每一堆各含偶数颗石子。这样的话，含有偶数颗石子的堆数就增加了1，从而变成了奇数。

不管怎样，局势又回到了对于我们来说有利的情形：要么只含一颗石子的有奇数堆，要么含有偶数颗石子的有奇数堆（或者两者同时满足）。于是，我们可以继续让对方面对不利的情形，并且逼迫对方把棋局变成对于我们有利的形势。不断这样下去，我们将会始终面对有路可走的棋局，从而保证不会输掉。

这个问题来自2006年意大利全国奥林匹克数学竞赛中的第6题。 kpxvES8afp+4pvEC31NnnTBCuERNkoroxi4rv4gM3uixAwOVYf8WQj8xwq677wsy