作者 | 肖韧吾
感谢作者授权「好玩的数学」发布。
过年还在做数学题吗? 那也太辛苦了, 来几个数学游戏放松放松吧。
I. 取糖果游戏
1. 网上的一个智力游戏
不久前, 在网上可以看到这样一个双人智力游戏:
在桌上放 13 颗糖果, 两个游戏者轮流拿, 每次取糖果不超过 3 颗, 不可不取，取完为止。
取得糖果总数为偶数的人获胜。
即使聪明人, 要获胜也不容易。不过如果找出了其中的奥妙, 先取者可保必胜, 就是说有“必胜策略”。下面会说明这个必胜策略。
2. 游戏的推广
这个游戏可以推广, 将 13 换成任意奇数 n (当然不能太小)。
有数学修养的人遇到这类游戏会想: 有没有“必胜策略”呢? 就是说有没有办法保证获胜呢?
对于这个游戏, 答案是肯定的: 当 n≡3,5,7(mod 8) 时先取者有必胜策略, 而当 n≡1 (mod 8) 时后取者有必胜策略。
那么, 知道必胜策略的人, 就可以包赢了? 这里要稍做一点说明: 如果参加游戏的一方知道必胜策略而另一方不知道, 那么知道必胜策略的一方可以稳扎稳打, 一旦遇到一种可保必胜的情形就抓住不放, 从而锁定胜局; 而不知道必胜策略的一方, 每次操作都按必胜策略的概率太小了, 几乎迟早一定会让对方抓到机会, 此后就必败无疑了。
3. 一个引理
要说明上面的必胜策略, 关键是下面的引理。
引理 I.1.设甲乙两人做上面的推广的取糖果游戏, 在轮到甲取糖果时桌上还有 m 颗糖果。则当 m≡2,3,6,7(mod 8), 或 m≡1,4(mod 8) 且甲手上的糖果数是奇数, 或 m≡0,5 (mod 8) 且甲手上的糖果数是偶数时, 甲有必胜策略; 而在其他情形乙有必胜策略。
证. 对 m 用归纳法, 当 m≤4 时不难直接验证。
设 m≥5 , 对于 m 模 8 及甲手上的糖果数的奇偶性的各种可能情形分别讨论。
若 m≡5 (mod 8) 且甲手上的糖果数是偶数, 则乙手上的糖果数也是偶数, 此时 A 可取 1 颗糖果, 使得乙遇到或 m≡4 (mod 8) 且手上的糖果数是偶数的情形, 从而由归纳法假设可见甲有必胜策略。
若 m≡6 (mod 8), 则甲当手上的糖果数是偶数时 (即乙手上的糖果数是奇数时) 取 1 颗糖果,使得乙遇到 m≡5 (mod 8) 且手上的糖果数是奇数的情形; 而当手上的糖果数是奇数时 (即乙手上的糖果数是偶数时) 取 2 颗糖果, 使得乙遇到 m≡4(mod 8) 且手上的糖果数是偶数的情形, 从而由归纳法假设可见甲有必胜策略。
若 m≡7(mod 8), 则甲当手上的糖果数是偶数时 (即乙手上的糖果数是偶数时) 取 3 颗糖果, 使得乙遇到 m≡4(mod 8) 且手上的糖果数是偶数的情形; 而当手上的糖果数是奇数时 (即乙手上的糖果数是奇数时) 取 2 颗糖果, 使得乙遇到 m≡5(mod 8) 且手上的糖果数是奇数的情形, 从而由归纳法假设可见甲有必胜策略。
若 m≡0 (mod 8) 且甲手上的糖果数是偶数, 则乙手上的糖果数是奇数, 此时甲可取 3 颗糖果, 使得乙遇到 m≡5 (mod 8) 且手上的糖果数是奇数的情形, 从而由归纳法假设可见甲有必胜策略。
若 m≡1 (mod 8) 且甲手上的糖果数是奇数, 则乙手上的糖果数也是奇数, 此时甲可取 1 颗糖果, 使得乙遇到 m≡0(mod 8) 且手上的糖果数是奇数的情形, 从而由归纳法假设可见甲有必胜策略。
若 m≡1(mod 8), 则甲当手上的糖果数是偶数时 (即乙手上的糖果数是奇数时) 取 2 颗糖果, 使得乙遇到 m≡0(mod 8) 且手上的糖果数是奇数的情形; 而当手上的糖果数是奇数时 (即乙手上的糖果数是偶数时) 取 1 颗糖果, 使得乙遇到 m≡1(mod 8) 且手上的糖果数是偶数的情形, 从而由归纳法假设可见甲有必胜策略。
若 m≡3(mod 8), 则甲当手上的糖果数是偶数时 (即乙手上的糖果数是偶数时) 取 2 颗糖果, 使得乙遇到 m≡1 (mod 8) 且手上的糖果数是偶数的情形; 而当手上的糖果数是奇数时 (即乙手上的糖果数是奇数时) 取 3 颗糖果, 使得乙遇到 m≡0(mod 8) 且手上的糖果数是奇数的情形, 从而由归纳法假设可见甲有必胜策略。
若 m≡4(mod 8) 且甲手上的糖果数是奇数, 则乙手上的糖果数是偶数, 此时甲可取 3 颗糖果, 使得乙遇到 m≡1(mod 8) 且手上的糖果数是偶数的情形, 从而由归纳法假设可见甲有必胜策略。
余下还有 4 种情形: m≡1,4(mod 8) 且甲手上的糖果数是偶数, 或m≡0,5 (mod 8) 且甲手上的糖果数是奇数。对这些情形不难逐一验证: 无论甲 取几颗糖果, 留给乙的都是有必胜策略的情形。
这样就完成了归纳证明。证毕。
注意在引理 I.1的证明中, 对于甲有必胜策略的每种情形, 都给出了一种必胜策略的操作方法。特别地, 对于网上的游戏 (n=13 的情形), 先取者可按此给出必胜的操作方法。
4. 游戏规则的改变
将取糖果游戏按原来的操作规则但改变胜负规则, 就成了下面的游戏。
在桌上放 n 颗糖果 ( n为奇数), 两个游戏者轮流拿, 每次取糖果不超过 3 颗, 不可不取，取完为止。
取得糖果总数为奇数的人获胜。
这个游戏仍然是有趣的, 而且难度与原来的取糖果游戏相同。那么是否也有必胜策略呢?
答案是肯定的: 当 m≡1,3,7(mod 8) 时先取者有必胜策略, 而当 m≡5 (mod 8) 时后取者有必胜策略。
要说明上面的必胜策略, 关键是下面的引理。
引理 I.2. 设甲乙两人做上面的推广的取糖果游戏, 在轮到甲取糖果时桌上还有 m 颗糖果。则当 m≡2,3,6,7 (mod 8), 或 m≡1,4(mod 8) 且甲手上的糖果数是偶数, 或 m≡0,5(mod 8) 且甲手上的糖果数是奇数时, 甲有必胜策略; 而在其他情形乙有必胜策略。
这个引理的证明可以仿照引理 I.1 的证明, 此处从略。
II. 最简单的棋与取棋子游戏
1. 最简单的棋
笔者在上小学时, 校园里流行过这样一种棋: 它的棋盘只有一排 8 个方格, 在第 1, 3, 5 格中各放一枚棋子 (见下图)。
二人对弈, 奕者双方递行一着。每个奕者每次任取一枚棋子向右移动若干格 (至少一格, 至多不限, 允许在一格中放入多枚棋子)。走最后一步者输。
作为小学生, 玩这个游戏还是有点难度的, 而且没看到其中的奥妙。直到上了中学以后, 才明白这个游戏是有必胜策略的。
首先可以将这个游戏推广, 棋盘仍是一排方格, 但格数不限。在一些方格中放入棋子, 一个格中可以放多枚棋子。仍是二人对弈, 奕者双方递行一着。每个奕者每次任取一枚棋子向右移动若干格 (至少一格, 至多不限)。走最后一步者输。
以下将这种棋称为“单行棋”。下面将说明单行棋的必胜策略。
2. 取棋子游戏
这也是个双人游戏。在桌上放若干堆棋子 (每堆棋子的个数不限), 每个游戏者每次任选一堆从中取走任意多枚棋子 (至少一枚, 至多不限)。取最后一枚棋子者输。
我们首先来说明, 这个取棋子游戏与单行棋在数学上是等价的。
将单行棋的棋盘各格标号, 最右边的一格标号 0, 然后从右到左依次标号 1, 2, 3, … (如下图)。
设开始时在棋盘上放了 m 枚棋子, 编号依次为从 1 到 m, 第 i 号棋子所在的格的标号记为 ni(1≤i≤m)。将此单行棋对应于如下的取棋子游戏: 在桌上预先放 m 堆棋子 (编号依次为从 1 到 m ),其中第 i 堆的棋子数为 ni(1≤i≤m)。
在单行棋中走一步, 相当于将某一个非零的 ni 减小 (至少减小 1, 至多可以减小到 0); 另一方面, 在取棋子游戏中, 每次取走一堆棋子中的若干枚, 相当于将某一个非零的 ni 减小 (至少减小 1, 至多可以减小到 0)。这样, 我们就可以将单行棋中第 i号棋子向右移动 s 格对应于取棋子游戏中从第 i 堆棋子中取走 s 枚。这样, 在单行棋中走最后一步就对应于取棋子游戏中取最后一枚棋子。这就说明单行棋与取棋子游戏在数学上是等价的。
在数学中经常可以遇到类似的情形: 两个不同的问题却可以用同一种数学方法处理。
取棋子游戏的历史很老, 至少在民国时期的文献中就有必胜策略。不过下面的一些变化是较新的。单行棋则未在很早的文献中见到, 尽管它在数学上与取棋子游戏等价。
3. 胜负规则的改变
也是与取糖果游戏相似, 单行棋 (或取棋子游戏) 的胜负规则也可以改为“走最后一步者赢” (或“取最后一颗棋子者赢”)。为了与前面所说的游戏区别, 我们将前面所说的单行棋称为“单行棋 A”, 而将按“走最后一步者赢”规则的单行棋称为“单行棋 B”; 类似地将前面所说的取棋子游戏称为“取棋子游戏 A”, 而将按“取最后一颗棋子者赢”规则的取棋子游戏称为“取棋子游戏 B”。
我们将看到, 尽管游戏 A 与游戏 B 的胜负规则正相反, 难度和复杂度却几乎相同, 而且必胜策略也几乎相同。
4. 单行棋或取棋子游戏的必胜策略
单行棋, 或者与之等价的取棋子游戏, 也是有必胜策略的。这个必胜策略要用到二进制数。
设 a=aa…ar 和 b=bb …br为两个二进制数, 其中每个 ai或 bi等于 0 或 1, 令 ci=ai bi(mod 2), 也等于 0 或 1 (1≤i≤r), 称二进制数 c=cc … cr为 a 与 b 的半和, 记为 c=a† b 。易见这样定义的“半加法运算” † 满足交换律和结合律, 此外还有a† a=0。
引理 II.1. 甲乙二人对弈单行棋。设在对弈过程中轮到甲行棋时, 棋盘上有 m 颗棋子, 所在的格号分别为且这些格号都表为二进制数。令
则当 时, 甲总有办法移动一颗棋子使得行棋后的 t 变为 0; 而当 t=0 时, 甲无论如何行棋结果都会使 t 变为非 0。
证. 设 t 的最高位非零数是右数第 i 位 (相当于 ), 则至少有一个 的右数第 i 位非零, 这样 。令 , 将第 j 号棋子右移 s 格, 就将 改变为 而保持其他 不变, 从而将 t 改变为 ; 另一方面, 若t=0而甲将第 j 号棋子右移 s 格使得 改变为 , 则 至少有一位数字与 不同, 从而移动第 j 号棋子后 t 变为非零。证毕。
注意引理 II.1 的证明中, 对于 t≠0 的情形给出了将 t 变为 0 的操作方法。
我们下面先讨论单行棋 B (或取棋子游戏B) 的必胜策略, 这比较简单些。
必胜策略是: 奕者甲若遇到 t≠0 的情形, 就按引理 II.1 的证明中的方法操作将t 变为 0, 由引理 II.1 可知, 尔后遇到的总是t≠0 的情形, 所以甲每次都可以操作使得 t 变为 0。由于每次操作都使得一个 ti变小, 这个过程最终将终止, 就是所有 ti都变为 0, 此时t=0 , 故最后一次操作是由甲完成的。若甲遇到 t=0 的情形, 则不要着急慢慢行棋, 如果对手不知道必胜策略, 则一直按照必胜策略操作的概率很小,甲只要得到一次 t≠0 的机会, 就可以锁定胜局了。
那么单行棋 A (或取棋子游戏A) 的必胜策略呢?
基本上与单行棋 B (或取棋子游戏B) 的必胜策略相同, 就是奕者甲先慢行,等待遇到 t≠0 的情形, 通过操作使得 t 变为 0, 然后保持这种状态, 只是到游戏接近尾声时要改变一下策略。所谓游戏接近尾声时, 是指在甲的某次操作后所有 ti中除了两个 2 外其余都是 1 或 0, 此时其中 1 的个数必为偶数。如果乙将某个 ti=1变为 0, 则甲将另一个tj=1变为 0 (即仍保持前述策略); 如果乙将某个 ti=2 变为 0, 则甲将另一个 tj=2 变为 1; 如果乙将某个 ti=2 变为 1, 则甲将另一个 tj=2 变为 0; 这样就给乙留下奇数个1, 所以最后一次操作者必为乙。
5. 加上限条件的游戏
在单行棋的操作规则中, 每次可将一枚棋子向右移动任意多格, 就是说移动的格数没有上限。如果对于移动的格数加个上限, 就成了一个更复杂的游戏,详述如下。
单行棋 Ak.棋盘是一排方格,格数不限。在一些方格中放入棋子, 一个格中可以放多枚棋子。二人对弈, 奕者双方递行一着。每个奕者每次任取一枚棋子向右移动 1 至 k 格 (其中 k 是一个大于 1 的整数)。走最后一步者输。
同样可以改变胜负规则, 这样给出了另一个游戏。
单行棋 Bk. 棋盘是一排方格,格数不限。在一些方格中放入棋子, 一个格中可以放多枚棋子。二人对弈, 奕者双方递行一着。每个奕者每次任取一枚棋子向右移动 1 至 k 格 (其中 k 是一个大于 1 的整数)。走最后一步者赢。
对于取棋子游戏也可以仿此加上取子个数的上限条件。
取棋子游戏 Ak. 在桌上放若干堆棋子 (每堆棋子的个数不限), 每个游戏者每次任选一堆从中取走若干枚棋子, 至少取 1 枚至多取 k 枚 (其中 k 是一个大于 1 的整数)。取最后一枚棋子者输。
加上限的取棋子游戏的特殊情形最早见于 [1] (相当于取棋子游戏A )。
对于加上限的取棋子游戏同样可以改变胜负规则, 这样给出了另一个游戏。
取棋子游戏 Bk. 在桌上放若干堆棋子 (每堆棋子的个数不限), 每个游戏者每次任选一堆从中取走若干枚棋子, 至少取 1 枚至多取 k 枚 (其中 k 是一个大于 1 的整数)。取最后一枚棋子者赢。
注意取棋子游戏 Ak与单行棋 Ak在数学上等价, 而取棋子游戏 Bk与单行棋 Bk在数学上等价。
6. 加上限条件的游戏的必胜策略
加上限的单行棋, 或者与之等价的加上限的取棋子游戏, 也是有必胜策略的。
这个必胜策略也要用到二进制数, 此外还要做一点准备。我们先来讨论单行棋Bk, 或等价的取棋子游戏 Bk。
对于一个非负整数a , 记 为 a 模 k 1 的余数, 并表为二进制数。对任意两个非负整数 a, b, 记
称为 a 与 b 的余半和。对于多个非负整数, 则将它们都取模 k 1 的余数然后再取半和称为余半和。易见这样定义的“余半加法运算” ‡ 满足交换律和结合律, 此外还有。
引理 II.2. 甲乙二人对弈单行棋 。设在对弈过程中轮到甲行棋时, 棋盘上有 m 颗棋子, 所在的格号分别为 , , , 。令
则当 时, 甲总有办法移动一颗棋子使得行棋后的 变为 0; 而当 时, 甲无论如何行棋结果都会使 变为非 0。
证. 设 的最高位非零数是右数第 位 (相当于 ), 则至少有一个 的右数第 位非零, 这样 。令 , 注意 , 可见 。若甲将第号棋子右移 格, 就将 改变为
而保持其他 不变, 注意 , 从而这一移动将 改变为 ; 另一方面, 若 而甲将第 j 号棋子右移 s 格 使得 改变为 , 则 至少有一位数字与 不同 (有可能 , 此时由于 , 必有 ), 从而移动第 j 号棋子后 变为非零。证毕。
注意引理 II.2 的证明中, 对于的情形给出了将 变为 0 的操作方法。
与单行棋 B (或取棋子游戏B) 的情形类似, 由引理 II.2 即可得到单行棋 Bk(或取棋子游戏Bk) 的必胜策略如下。
甲若遇到的情形, 就按引理 II.2 的证明中的方法操作将变为 0, 由引理 II.2 可知, 尔后遇到的总是的情形, 所以甲每次都可以操作使得变为 0。由于每次操作都使得一个变小, 这个过程最终将终止, 就是所有都变为 0, 此时, 故最后一次操作是由甲完成的。若甲遇到的情形, 则不要着急慢慢行棋, 如果乙不知道必胜策略, 则一直按照必胜策略操作的概率很小, 甲只要得到一次的机会, 就可以锁定胜局了。
单行棋(或取棋子游戏) 的必胜策略, 基本上与单行棋(或取棋子游戏) 的必胜策略相同, 就是甲先慢行, 等待遇到的情形, 通过操作使得变为 0, 然后保持这种状态, 只是到游戏接近尾声时要改变一下策略。所谓游戏接近尾声时, 是指在甲的某次操作后所有 中除了两个 2 外其余都是 1 或 0, 此时其中 1 的个数必为偶数。此时如果乙将某个变为 0, 则甲将另一个 变为 0 (即仍保持前述策略); 如果乙将某个变为 0, 则甲将另一个变为 1; 如果乙将某个变为 1, 则甲将另一个变为 0; 这样就给乙留下奇数个 1, 所以最后一次操作者必为乙。
注. 引理 II.2 的证明中所具体给出的必胜策略, 并不是唯一的必胜策略。
由引理 II.2 立得下面的推论。
推论 II.1. 甲乙二人对弈单行棋 Ak(或取棋子游戏 Ak), 甲先行。假设开始时至少有 1 堆棋子的个数模 k 1 的余数>1 。如果开始时余半和为 0, 则乙有必胜的策略; 反之则甲有必胜的策略。
III. 称球问题
1. 12 球问题
可能很多人都见过下面这个智力游戏 (或智力测验) 问题。
12 球问题. 有 12 个球, 外表看上去都一样, 其中 11 个球重量相同 (为方便起见简称为“正常球”), 而另一个球的重量与正常球不同 (称为“异常球”), 但不知异常球比正常球重些还是轻些。现在用一台天平, 要求只称 3 次就将异常球找出来。请给出一种称法。
这个问题的历史也比较老, 至少在 60 年前就有多种解法, 这些解法无一例外都有很强的逻辑性, 显示 12 球问题的高难度。现在要搜到12 球问题的一两种解法应该不难, 这里就不举例了。
有数学修养的人遇到12 球问题可能会想: 12 这个数有什么特殊之处吗? 如果将 12 换成 11 或 13, 是否也是一个好问题呢? 答案是肯定的, 但对于 13 个球的情形, 下面将看到一点小的差异。而若将 12 换成 14, 则问题无解, 就是说不能保证称 3 次就找出异常球。
我们下面要做的, 一是给出12 球问题的推广, 二是从数学上给出另一个思路, 使得问题很容易解决。
2. 一般的称球问题
对于 12 球问题, 还有一点细节值得注意: 在找出异常球的同时, 能否判断异常球比正常球重还是轻? 原问题中没有提这个要求, 实际上加了这个要求问题仍然是可解的, 只是要做得更细致些 (参看见下面第 5 节)。
如果在称的过程中, 有一次天平的两边放着同样数目的球, 其中有异常球, 那么天平是不平衡的。如果天平的左边重而异常球在左边, 就可判断异常球比正常球重; 而若天平的左边重而异常球在右边, 则可判断异常球比正常球轻。对于天平的右边重的情形同样可以作判断。唯一问题是, 如果每次称都没有把异常球放在天平上, 那么每次称天平都是两边平衡, 即使找到异常球也不能判断异常球比正常球重还是轻。
所以, 加上判断异常球比正常球重还是轻这个要求, 相当于要求每个球至少要上天平称一次。这与原问题有所不同, 称为加强的问题。
对于一般的球数, 问题应该如下提出。
称球问题. 有n>3个球, 外表看上去都一样, 其中 n-1 个球的重量相同, 称为正常球; 而另一个球的重量与正常球不同, 称为异常球, 但不知道异常球比正常球重还是轻。现在用一台天平, 问至少要允许称多少次, 才能保证将异常球找出来?
由于上面提到的细节, 还有一个稍不同的问题。
加强的称球问题. 有 n>3 个球, 外表看上去都一样, 其中n-1个球的重量相同, 称为正常球; 而另一个球的重量与正常球不同, 称为异常球, 但不知道异常球比正常球重还是轻。现在用一台天平, 问至少要允许称多少次, 才能保证将异常球找出来, 并判定异常球比正常球重还是轻?
3. 称球问题的答案
一般的称球问题的历史也较老, 至少 50 年前就有人给出解答, 但至今尚未见到正式发表, 所以这里无法引用。我们先将结果陈述如下。
定理 III.1.对于 个球的称球问题, 为保证找出异常球, 至少要称
[log(2n-1)] 1
次。而对于n>3 个球的加强的称球问题, 为保证找出异常球并判定异常球比正常球重还是轻, 至少要称
[log(2n 1)] 1
次。
可能很多人初看这些断言难以立刻理解, 我们可以换一个方式陈述: 对于 n>3 个球的称球问题, 若要保证称d 次就找出异常球, 充分必要条件是
而对于n>3 个球的加强的称球问题, 若要保证称 次就找出异常球并判定异常球比正常球重还是轻, 充分必要条件是
特别地, 由此可见 12 球问题在加强后也是有解的。
定理 III.1 的证明颇不简单且颇有难度, 但不需要用什么高深的工具, 完全是初等的, 此处从略, 有兴趣且喜欢解难题的读者, 不妨自己试做一个证明。
4. 预先设计称法的解决方案
按照定理 III.1 的证明, 对于具体的问题都可以给出称法, 但随着 n 的增加越来越复杂, 每次称过后都要根据多种情形分别作判断, 并设计下一次的称法。作为智力游戏是高难度的。
数学上常有这种情况: 对一个问题, 按某一种思路去解决既复杂又困难, 但换一种思路, 却可能“柳暗花明又一村”, 收到意想不到的效果。对称球问题和加强的称球问题就是这样。
我们来这样设想: 假如我们能预先设计好一种称球方案, 只要按这个方案去称, 不管称的结果如何, 在表上一查就可以找到异常球, 那多简单呀! 有没有这样的近乎“傻瓜方案”呢? 不但有, 而且很多。
我们来做点较详细的说明。找异常球的列表方案, 就是先将 n 个球分别标上 1 至 n 的号, 然后用一个表规定各次称球在左盘上和右盘上各放哪些球, 称完后, 按照各次称的结果, 由另一个表查找, 即可找到异常球的号码, 对于加强的称球问题还可从表上看到异常球比正常球重还是轻。
定理 III.2. 对于n>3个球的称球问题和加强的称球问题, 都可以预先设计称法。详言之, 先将 n 个球分别标上 1 至 n 的号, 对于称球问题, 可以预先给出
d=[log(2n-1)] 1
次的称法 (即每次称在左盘和右盘各放的球号), 并另给出一个对照表, 根据各次称的结果即可从表中查出异常球的号码。而对于n>3个球的加强的称球问题, 也是按球号预先给出
d=[log(2n 1)] 1
次的称法 (即每次称在左盘和右盘各放的球号), 并另给出一个对照表, 根据各次称的结果即可从表中查出异常球的号码, 并判定异常球比正常球重还是。
我们注意两个要点: 一是预先设计的称法不需要在称的过程中调整, 甚至称的先后次序也无关紧要; 二是这样设计的称法是按照最少需要称的次数, 并不因为方法简单方便而增加称的次数。
下面来解释称法表的设计原理。将天平的左盘记为 1, 右盘记为-1 。将 n 个球分别标上 1 至 n 的号, 对每个球赋予一个 d 元向量, 它的每个分量只能是 1, -1 或 0, 第 i 个球所对应的向量记为 vi(1≤i≤n)。这个向量的意义是: 若 vi的第 j 分量为 1, 则在第 j 次称时将第 i 个球放在天平的左盘; 若 vi的第 j 分量为-1 , 则在第 j 次称时将第 i 个球放在天平的右盘; 若 vi的第 j 分量为 0, 则在第 j 次称时不将第 i 个球放在天平上。这些向量需要满足下列条件:
i) 若, 则 ;
ii) ;
对于加强的称球问题还要加一个条件
iii)。
条件 i) 是为了保证从称的结果找到异常球, 根据称的结果可以得到一个向量v : 若第 j 次称的结果是左盘重, 则 v 的第 j 分量为 1; 若第 j 次称的结果是右盘重, 则 v 的第 j 分量为 -1; 若第 j 次称的结果是两边平衡, 则 v 的第 j 分量为 0 (1≤j≤n)。易见若第 i 号球是异常球且比正常球重, 则vi=v ; 若第 i 号球是异常球且比正常球轻, 则 vi=-v , 而条件 i) 保证了满足 vi=v 或 vi=-v 的 i 的唯一性。条件 ii) 的意义是对每个 j(1≤j≤n), 第 j 分量为 1 的向量与第 j 分量为 -1 的向量一样多, 即第 j 次称时左右两盘中的球数相同。若条件 iii) 也成立, 则 v≠0,而由 vi=v 或 vi=-v 可以判定第 i 号球 (异常球) 比正常球重还是轻。
引理 III.1. 设整数。若, 则存在 n 个 d 元向量其每个分量都等于1, -1 或 0, 且满足条件 i) 和 ii); 此外若 , 则条件 iii) 也满足。
这个引理的证明方法是归纳地构造, 技术性较强, 此处从略。由引理 III.1 即可得到定理III.2 。
一旦有了称法表, 用天平找异常球就是很容易的事了。
引理 III.1 的证明给出构造称法表的一个方法, 但称法表有很多构造方法, 尽管都不很简单也不很容易。
笔者在四十多年前曾编了一个程序, 对一般的 n 可以构造称法表, 这样构造称法表也就很容易了。
5. 12 球问题的一个称法表
下面是用电脑对 12 球问题构造的一个称法表, 其中表 1 说明各次用天平称时左、右盘中放的球的号码, 由称的结果, 从表 2 中就可以找到异常球号, 而且知道异常球比正常球重还是轻 (故这个称法表可用于加强的称球问题)。
(表 2 中的 * 表示不可能出现的情形。)
例如, 若第 1 次称 (左盘放 2, 5, 8, 10 号球, 右盘放 1, 4, 7, 12 号球) 天平的左盘比右盘重, 第 2 次称 (左盘放 3, 6, 9, 10 号球, 右盘放 2, 5, 8, 12 号球) 右盘比左盘重, 第 3 次称 (左盘放 1, 2, 3, 12 号球, 右盘放 4, 5, 6, 11 号球) 两盘平衡, 则由表 2 可以查出异常球为 8 号球, 比正常球重。
参考文献
[1] 牛伟强: 数学中的几个小游戏遗留问题的探索, 《数学通报》11 (2009)
[2] 肖韧吾: 也谈取棋子游戏. 《数学通报》 12 (2009)
[3] 尹裕: 自由棋, 《小学生数学报》 1996 年第 398-401 期
[4] 张慧欣: 数学中的几个小游戏, 《数学通报》 11 (2008)
