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

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

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

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

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

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

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

先给出平衡数组的定义：

平衡数组 对于一个𝑛元正整数组(𝑚_(1),𝑚_(2),⋯,𝑚_(𝑛))，其中每一个数𝑚_(𝑖)均能唯一地表示成2的不同次幂之和．若任意2^(𝑠)(𝑠∈ℕ)均包含在偶数个𝑚的展开式中，则称(𝑚_(1),𝑚_(2),⋯,𝑚_(𝑛))为一个平衡数组．

若存在某个2^(𝑠)(𝑠∈ℕ)包含在奇数个𝑚的展开式中，则称(𝑚_(1),𝑚_(2),⋯,𝑚_(𝑛))为一个非平衡数组．

引理1 𝑛>1，对于任意𝑛−1个数𝑚_(1)，𝑚_(2)，⋯，𝑚_(𝑛−1)，均存在唯一的正整数𝑝，使(𝑚_(1),𝑚_(2),⋯,𝑚_(𝑛−1),𝑝)为平衡数组．

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

引理3 对于非平衡数组(𝑚_(1),𝑚_(2),⋯,𝑚_(𝑛))，存在某个𝑚′𝑖<𝑚_(𝑖)，将数组中的𝑚_(𝑖)变为𝑚′𝑖，其余数不变，该数组变为平衡数组．

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

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

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

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

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

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

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

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

参考资料