Nim 游戏的若干变种

今年我为北京世纪坛的数学益智游戏展贡献了不少内容。我打算在这里记录一些自己的创作、发现、收获和心得。这是该系列的第三篇。

今年的数学益智游戏展有一个特色,就是到访者可以购买一个小册子,这可以为自己的参展体验加分。我们内部把它叫作“任务单”。任务单里有很多任务,对应了展会中的各种项目。完成任务可以获得印章,赢取奖励。为了增加任务单的附加价值,任务单上还附赠了很多简单展品的高级玩法说明。这里举一个有趣的例子。

展会现场有很多冰糕棍,可以用来做冰糕棍炸弹。任务单上给出了冰糕棍的另一种玩法——Nim 游戏。将冰糕棍从左到右摆成若干堆。两人轮流从其中一堆冰糕棍中取走任意数量的冰糕棍(可以全部取走,但不能不取)。取走最后一根冰糕棍的玩家获胜。

考虑到任务单的读者可能已经熟悉 Nim 游戏了,因此为了让所有人都能有新的收获,我补充了一些不太常见的 Nim 游戏变种。我一共准备了 10 条补充规则。游戏开始前,双方可以任选其中一条来玩。

  1. 每次只能从最左端或者最右端的那一堆中取冰糕棍。
  2. 每次只能从冰糕棍数最多的那一堆中取冰糕棍(如果冰糕棍数最多的堆出现了并列的情况,任选其中一堆即可)。
  3. 每次只能从冰糕棍数最少的那一堆中取冰糕棍(如果冰糕棍数最少的堆出现了并列的情况,任选其中一堆即可)。
  4. 第一个人可以从任意一堆中取冰糕棍,今后每个人只能从和刚才不同的堆中取冰糕棍。
  5. 第一个人可以从任意一堆中取冰糕棍,今后每个人只能从和刚才相邻的堆中取冰糕棍。
  6. 第一个人可以从任意一堆中取冰糕棍,今后每个人只能从和刚才相同的堆中取冰糕棍(除非刚才那一堆被取完了)。
  7. 每次取完后,还可以再从另一堆中取走同样多的冰糕棍。
  8. 每次取冰糕棍的数目改为最多 3 根。
  9. 取走最后一根冰糕棍的玩家算输。

还差一条,应该写什么呢?我有三个备选方案。大家可以猜一猜,我最后用了哪个方案。

  • 游戏双方各有一次“跳过”的机会。
  • 游戏中有一次“跳过”的机会,任意玩家使用后该机会作废。
  • 每次对方取完后,如果他还有别的取法,你便能要求他该轮换一种取法。

Read more…

称假币问题的变形:无假币与“天平机”

大家应该听说过 9 枚硬币的问题吧。9 枚硬币当中有 8 枚是真币,有 1 枚是假币。所有的真币重量都相同,假币的重量则稍重一些。怎样利用一架天平两次就找出哪一枚硬币是假币?方法是,先把 9 枚硬币分成三组,每组各 3 枚硬币。然后,把第一组放在天平左边,把第二组放在天平右边。如果天平向左倾斜,说明假币在第一组里;如果天平向右倾斜,说明假币在第二组里;如果天平平衡,说明假币在剩下的第三组里。现在,假币的嫌疑范围就被缩小到 3 枚硬币之中了。选择其中 2 枚硬币分放在天平左右两侧。类似地,如果天平左倾,就说明左边那枚硬币是假的;如果天平右倾,就说明右边那枚硬币是假的;如果天平平衡,就说明没放上去的那枚硬币是假的。

9 硬币问题实在是太经典了,你甚至能在人教版小学五年级下册的课本里看到它。9 硬币问题还衍生出了很多变形,其中最著名的当属 12 硬币问题了:有 12 枚硬币,其中一枚是假币,但我们不知道假币是更重一些还是更轻一些;请利用一架天平三次找出哪一枚硬币是假币,并判断出它比真币更重还是更轻。12 硬币问题的经典程度恐怕不亚于 9 硬币问题。早在 20 世纪 40 年代,12 硬币问题就已经吸引了一大批数学家和数学爱好者,甚至有人建议把这个问题扔到德国去,以削弱德国人在二战中的战斗力。如果你想知道答案,可以在网上找找,应该很容易找到。我们今天就不讨论了。

今天,我们真正想聊的其实是这个问题的另外一种比较少见的变形:仍然是要在 9 枚硬币当中寻找 1 枚假币,仍然假设假币的重量要稍重一些,仍然只能使用天平两次;但是这一次,你所使用的是一种“天平机”,它不会立即告诉你现在是哪边重哪边轻,而是在你两次称完后把这两次的结果一并打印给你。这下,你就没法根据天平的反馈结果随机应变了,必须事先把每次怎么放硬币全规划好。那么,你该怎么办?在本文后面的内容中,均已知假币比真币更重,直至另有说明。

Read more…

位换记号、排列测试与状态图:杂耍中的数学

2016 年 7 月 30 日至 8 月 7 日,第 39 届欧洲杂耍大会(European Juggling Convention)在荷兰的阿尔梅勒举行, 8 月 3 日凌晨的搏击之夜(Fight Night)自然再度成为了众人关注的焦点——它是杂耍斗(combat juggling)这项运动最大的赛事。在杂耍斗的圈子里,有两个响当当的大名你必须要知道:德国选手 Jochen Pfeiffer 目前世界排名第二,之前拿过 6 次搏击之夜的冠军;英国选手 Luke Burrage 目前世界排名第一,之前拿过 8 次搏击之夜的冠军。这一年的比赛中,两位老将均以完胜的成绩轻松进入 32 强,并在淘汰赛阶段过关斩将,最终成功在决赛场上相遇。最终,世界排名第二的 Jochen 以 5 比 4 的成绩击败了世界排名第一的 Luke ,夺得了又一个搏击之夜的冠军。

杂耍斗是一种两人对战类的体育运动。比赛规则非常简单。每局比赛开始时,两名选手各自抛耍 3 个杂耍棒。任何一方都可以故意上前干扰另一方(但只能针对对方手中的或者空中的杂耍棒,不能针对对方的手臂和身体)。谁站到最后,谁就赢得该局。先赢 5 局者获得比赛的胜利。

典型的一局比赛大致就像下面这样。这是 Jochen 和 Luke 的第 6 局比赛。

Read more…

捡石子游戏、 Wythoff 数表和一切的 Fibonacci 数列

让我们来玩一个游戏。把某个国际象棋棋子放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。如果把棋子放在如图所示的位置,那么你愿意先走还是后走?显然,答案与我们放的是什么棋子有关。

这个游戏对于兵来说是没有意义的。在如图所示的地方放马或者放象,不管怎样都无法把它移动到棋盘的最左下角,所以我们也就不分析了。因此,我们只需要研究王、后、车三种情况。

Read more…

实数、超实数和博弈游戏:数学的结构之美

(一)一个博弈游戏

让我们来玩一个游戏。下面有五行石子,白色的石子都是我的,黑色的石子都是你的。我们轮流拿走一个自己的石子,并且规定如果一个石子被拿走了,它后面的所有石子都要被扔掉。谁先没有拿的了,谁就输了。

○●●○●●○●●○
●○○●○●●○●
○○○○
●●●○●●●

Read more…