也谈取棋子游戏

luyuanhong

也谈取棋子游戏

作者 | 肖韧吾

来源 |《数学通报》，2009 年第 48 卷第 12 期

张慧欣在文[1]中提出一个取棋子的游戏：

游戏 A 有若干堆棋子，两人轮流取棋子，每人每次只能从 1 堆中取 1～4 个棋子，取到最后一个棋子者获胜。

文中提出这个游戏是否有必胜策略的问题，这个问题后来被牛伟强[2]解决。

我们的问题是：游戏 A 中每次取 1～4 个棋子的规定过于特殊，自然地应该改为“每次取 1～k 个棋子”，其中 k 是一个可以任意预先商定的正整数。本文将证明，这样的游戏的必胜策略问题仍是可以解决的，特别地这也给出文[2]中结果的另一个证明。

首先我们来说明下面一个游戏的必胜策略：

游戏 B 有若干堆棋子，甲乙两人轮流取棋子(第一次由甲取棋子)，每人每次只能从 1 堆中取至少 1 个棋子(取子数没有上限)，取到最后一个棋子者获胜。

这个游戏的必胜策略问题早已解决，至少可以在 60 余年前的杂志上查到。我们下面用现代的语言叙述这个问题的答案并给出证明，这样比较简单些。我们需要用到二进制数，对二进制数我们用 + 记半加法，即对任意两个二进制数 b ，b' ，b + b' 为将 b 和 b' 的各位数字分别相加，但不进位，例如 10101 + 1111 = 11010 。显然半加法满足交换律和结合律，此外对任意二进制数 b 有 b + b = 0 。



有趣的是，如果将游戏 B 中的胜负规则改为相反，即规定取最后一个棋子者输，则上面的必胜策略仍然适用！为方便起见，记

游戏 B' 有若干堆棋子，甲乙两人轮流取棋子(第一次由甲取棋子)，每人每次只能从 1 堆中取至少 1 个棋子(取子数没有上限)，取最后一个棋子者输。

则有

推论 1 对游戏 B 假设开始时至少有 1 堆棋子的个数＞1 。如果开始时总半和为 0 ，则乙有必胜的策略；反之则甲有必胜的策略。

证明 不妨设开始时总半和为 0 ，否则由命题 1 可以类似地证明。

乙的必胜策略与游戏 B 基本相同，即保持总半和为 0 ，所不同的是在游戏接近尾声时，即只剩下一堆棋子个数＞1 时，乙取该堆棋子使得余下棋子的总半和为 1 ，这总是可以做到的：设此时共有 n 堆棋子，其中第 i 堆的棋子个数＞1 而其余各堆棋子的个数都是 1 ，则在 n 为奇数时取第 i 堆的棋子留下 1 个，而在 n 为偶数时取尽第 i 堆的棋子。这样轮到甲取子时有奇数堆棋子每堆 1 个，当然甲必取最后一个棋子无疑，证毕。

下面我们来讨论开始时所说的游戏，即

游戏 C 设 k 为正整数。有若干堆棋子，甲乙两人轮流取棋子(第一次由甲取棋子)，每人每次只能从 1 堆中取 1～k 个棋子，取到最后一个棋子者获胜。



与游戏 B' 类似地可建立

游戏 C' 设 k 为正整数.有若干堆棋子，甲乙两人轮流取棋子(第一次由甲取棋子)，每人每次只能从 1 堆中取 1～k 个棋子，取最后一个棋子者输。

推论 2 对游戏 C 假设开始时至少有 1 堆棋子的个数模 k+1 的余数 >1 。如果开始时余半和为 0 ，则乙有必胜的策略；反之则甲有必胜的策略。

证明 不妨设开始时余半和为 0 ，否则由命题 2 可以类似地证明。



顺便指出，有另一种游戏的数学原理与上面的取棋子游戏等价，就是所谓“自由棋”(参看[3])，这种棋的棋盘只有一排格子(格数不限)，棋子只有一种(个数不限)，对弈时任取一些棋子放在一些格中(一个格里可放多枚棋子)，然后“弈者双方递行一着”，每人每次取一枚棋子按指定的方向前进至少 1 格，直到所有棋子都走到最后一格为止，走最后一步者获胜如果每次走的格数没有上限，则这种自由棋的数学原理与前面的游戏 B 等价；如果规定每次至多走 k 格，则数学原理与游戏 C 等价。若将胜负规则改为“走最后一步者输”，则在每次走的格数没有上限时这种自由棋的数学原理与游戏 B' 等价；而在每次至多走 k 格时数学原理与游戏 C' 等价。道理很简单：如果将棋盘的格子从最后一格开始往前依次标号 0 , 1 , 2 , …(见下图)那么在开始放棋子时就可以将第格中的一枚棋子对应于游戏 B 或 C 中的一堆 i 个棋子(格中放了几个棋子就对应于游戏 B 或 C 中有几堆棋子)，而将一个棋子前进 d 格对应于相应的那堆棋子取出 d 个，不难看出这样就建立了自由棋与取棋子游戏之间的数学等价。因此，命题 1 和命题 2 也给出了自由棋的必胜策略。



参考文献

1 张慧欣. 数学中的几个小游戏数学通报，2008.11

2 王跃进,牛伟强. 数学中的几个小游戏遗留问题的探索. 数学通报, 2009.11

3 自由棋. 小学生数学报,1996:398～401