从取石子问题到一个象棋残局

昨天做了一道取石子问题，比较有意思．

题目1 有堆石子，每一堆中的石子个数分别为、、、．二人轮流从中取石子，每人每次可以从某一堆中取任意枚石子（至少枚），最后取完者为胜，谁有必胜策略？

分析 这种操作类问题的策略往往是考虑对称操作，即无论对方如何取石子，自己均可以作出与对方完全一样的操作．为了达成这一目标，我们希望将这四堆石子两两分组，让同组内的石子个数相等．简单尝试后发现，、、、这一初始状态下，双方均没有办法达到这一目的．

既然无法实现整体的对称，我们着眼于局部．很快联想到二进制的每一位只能为或两种状态，如果能让石子个数的二进制表示中，每一位上的个数均为偶数，也就可以达到一样的效果．我们称这是一个平衡状态．

、、、的二进制表示如下（前面不足的位数用补足）：

于是，先手第一次操作时，在最后一堆拿走枚石子，使得四堆石子个数（二进制）分别为：

此时是一个平衡状态．接下来，不论后手如何取走石子，总会将其变为一个非平衡状态，而一个非平衡状态经过某个操作后，也总可以变为平衡状态．（这里需要严谨证明．）而最终胜利状态、、、是一个平衡状态，所以先手有必胜策略．

为了解决更一般的情形，我们给出以下几个引理^[1]：

先给出平衡数组的定义：

平衡数组 对于一个元正整数组，其中每一个数均能唯一地表示成的不同次幂之和．若任意()均包含在偶数个的展开式中，则称为一个平衡数组．

若存在某个()包含在奇数个的展开式中，则称为一个非平衡数组．

引理1 ，对于任意个数，，，，均存在唯一的正整数，使为平衡数组．

引理2 将平衡数组中的任意一个数变为()，其余数不变，则此数组变为非平衡数组．

引理3 对于非平衡数组，存在某个，将数组中的变为，其余数不变，该数组变为平衡数组．

以上三个引理的证明都比较简单，熟悉二进制的同学可以很快得出，故在此略去．

于是我们得到了如下一般性结论：

对于任意堆石子，进行一样规则的游戏（二人轮流从中取石子，每人每次可以从某一堆中取任意枚石子（至少枚），最后取完者为胜）．谁有必胜策略依赖于初始状态是否是一个平衡数组．

如果初始状态为一个非平衡数组（如题目1），则先手一定可以经过恰当的操作使之变成一个平衡数组，因此先手有必胜策略．

如果初始状态为一个平衡数组，例如三堆石子个数依次为、、，则不论先手如何操作，均会得到一个非平衡数组，而后手总能将其再次变为平衡数组，因此后手有必胜策略．

事实上，这就是尼姆博弈的推广．

最后来看一个象棋残局（转自B站up主：--根号13--）：

容易发现，过河兵卒不宜再走动，否则等于给对方“松了绑”．其次，双方炮都只能在各自的路线上进退，不能平动．而且，河沿上的兵卒只有一方可以进一步．除此之外，没有任何着法．于是问题的关键是：双方谁能走到最后一步棋？这样分析之后，就不难用本文的方法来预测此残局的胜负，并且指出取胜的办法了．

参考资料