过年玩几个数学游戏

luyuanhong

过年玩几个数学游戏

原创 肖韧吾 好玩的数学 2023-01-24 21:52 发表于江西

过年还在做数学题吗? 那也太辛苦了, 来几个数学游戏放松放松吧。

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 的证明, 此处从略。

luyuanhong

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. 单行棋或取棋子游戏的必胜策略

单行棋, 或者与之等价的取棋子游戏, 也是有必胜策略的。这个必胜策略要用到二进制数。



5. 加上限条件的游戏

在单行棋的操作规则中, 每次可将一枚棋子向右移动任意多格, 就是说移动的格数没有上限。如果对于移动的格数加个上限, 就成了一个更复杂的游戏, 详述如下。

单行棋 Ak . 棋盘是一排方格,格数不限。在一些方格中放入棋子, 一个格中可以放多枚棋子。二人对弈, 奕者双方递行一着。每个奕者每次任取一枚棋子向右移动 1 至 k 格（其中 k 是一个大于 1 的整数）。走最后一步者输。

同样可以改变胜负规则, 这样给出了另一个游戏。

单行棋 Bk . 棋盘是一排方格,格数不限。在一些方格中放入棋子, 一个格中可以放多枚棋子。二人对弈, 奕者双方递行一着。每个奕者每次任取一枚棋子向右移动 1 至 k 格（其中 k 是一个大于 1 的整数）。走最后一步者赢。

对于取棋子游戏也可以仿此加上取子个数的上限条件。

取棋子游戏 Ak . 在桌上放若干堆棋子（每堆棋子的个数不限）, 每个游戏者每次任选一堆从中取走若干枚棋子, 至少取 1 枚至多取 k 枚（其中 k 是一个大于 1 的整数）。取最后一枚棋子者输。

加上限的取棋子游戏的特殊情形最早见于 [1]（相当于取棋子游戏 A4 ）。

对于加上限的取棋子游戏同样可以改变胜负规则, 这样给出了另一个游戏。

取棋子游戏 Bk . 在桌上放若干堆棋子（每堆棋子的个数不限）, 每个游戏者每次任选一堆从中取走若干枚棋子, 至少取 1 枚至多取 k 枚（其中 k 是一个大于 1 的整数）。取最后一枚棋子者赢。

注意取棋子游戏 Ak 与单行棋 Ak  在数学上等价, 而取棋子游戏 Bk 与单行棋 Bk 在数学上等价。

6. 加上限条件的游戏的必胜策略

加上限的单行棋, 或者与之等价的加上限的取棋子游戏, 也是有必胜策略的。

这个必胜策略也要用到二进制数, 此外还要做一点准备。我们先来讨论单行棋 Bk  , 或等价的取棋子游戏 Bk 。

luyuanhong

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 的证明颇不简单且颇有难度, 但不需要用什么高深的工具, 完全是初等的, 此处从略, 有兴趣且喜欢解难题的读者, 不妨自己试做一个证明。

4. 预先设计称法的解决方案

按照定理 III.1 的证明, 对于具体的问题都可以给出称法, 但随着 n 的增加越来越复杂, 每次称过后都要根据多种情形分别作判断, 并设计下一次的称法。作为智力游戏是高难度的。

数学上常有这种情况: 对一个问题, 按某一种思路去解决既复杂又困难, 但换一种思路, 却可能“柳暗花明又一村”, 收到意想不到的效果。对称球问题和加强的称球问题就是这样。

我们来这样设想: 假如我们能预先设计好一种称球方案, 只要按这个方案去称, 不管称的结果如何, 在表上一查就可以找到异常球, 那多简单呀! 有没有这样的近乎“傻瓜方案”呢? 不但有, 而且很多。

我们来做点较详细的说明。找异常球的列表方案, 就是先将 n 个球分别标上 1 至 n 的号, 然后用一个表规定各次称球在左盘上和右盘上各放哪些球, 称完后, 按照各次称的结果, 由另一个表查找, 即可找到异常球的号码, 对于加强的称球问题还可从表上看到异常球比正常球重还是轻。



笔者在四十多年前曾编了一个程序, 对一般的 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)

mathmatical

小外孙（段灿），在医院治疗，病危，怎么办？哎，您聊聊，再生障碍性贫血，

mathmatical

提一条建议，您能不能不发，某某朱教授走了，某某李教授走了，，，很不吉利。。我们都渴望长寿，，