Nim 游戏的若干变种

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

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

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

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

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

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

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

Read more…

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

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

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

Read more…

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

(一)一个博弈游戏

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

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

Read more…

趣题:庄家的秘密序列

    下面是 2013 年 9 月 IBM Ponder This 的谜题。

    A 和 B 在赌场玩一个游戏,他们要协同作战与庄家对抗。游戏一轮一轮地进行,每一轮的规则都是一样的:首先 A 赌 0 和 1 当中的某个数字,然后 B 再赌 0 和 1 当中的某个数字,最后庄家给出 0 和 1 当中的某个数字;如果所有的三个数字都相同,则 A 和 B 获胜,否则庄家获胜。游戏前, A 和 B 可以商量一个对策,但游戏一旦开始,除了下赌注本身之外,两人不能再有其他任何形式的交流了。

    容易看出,如果 A 和 B 都随机下注,他们只有 25% 的获胜概率。然而,如果两人事先约定,在每一轮中, B 总是跟着 A 下注, A 赌什么 B 就赌什么,那么他们获胜的概率就会提高到 50% 。但是,不管采用哪种方案,在最坏情况下,两人都有可能一次也不能获胜。

    有意思的事情出现了。在游戏开始前两人商量策略的时候,两人突然意识到, B 有办法偷到庄家将会在游戏中使用的 01 序列。也就是说,游戏开始后,每一轮里庄家要出什么, B 都将会知道。但是,一旦 B 拿到了这个 01 序列, B 就不能和 A 交流了。在这样的条件下,两人能做得比刚才更好吗?能!比如说,两人可以保证在最坏情况下也有至少 50% 的获胜次数: B 可以在第 1, 3, 5, 7, … 轮游戏中赌下一轮庄家将会出的那个数(这相当于暗示了 A 下一轮赌什么),两人便能保证在第 2, 4, 6, 8, … 轮游戏中获胜了。

    我们的问题是:假设游戏一共有 9 轮,设计一种策略使得 A 和 B 能够保证至少 6 次胜利。

Read more…

IMO2012趣题:带有说谎的猜数游戏

    考虑一个传统的猜数游戏。 A 、 B 两名玩家事先约定一个正整数 N ,然后 A 在心里想一个不超过 N 的正整数 x , B 则需要通过向 A 提问来猜出 A 心里想的数。 B 的问题只有唯一的格式:先列出一些数,然后问 A “x 是否在这些数里”, A 则需要如实回答“是”或者“否”。显然, B 是保证能猜到 x 的,只需要依次询问“x 是否等于 1 ”,“x 是否等于 2 ”即可。由于 B 可以精心选出满足某种特征的所有数,询问 x 是否在这些数里,因而 B 还可以做得更好。例如当 N = 16 时, B 第一次可以问“x 是否小于等于 8 ”,或者等价地,“x 是否属于 {1, 2, 3, 4, 5, 6, 7, 8} ”;接下来,根据 A 的回复继续细问“x 是否小于等于 4 ”或者“x 是否小于等于 12 ”,以此类推。另一种方法则是询问“x 的二进制表达的第一位是否是 1”,“x 的二进制表达的第二位是否是 1”,以此类推,从而获得 x 的二进制表达的所有数位,便能推出 x 来。

    现在,有意思的问题来了。假设 A 可以偶尔说谎(但保证不会连续说谎两次),那么 B 还能通过询问猜出 A 所想的数吗?如果愿意的话, B 可以询问任意多次。

Read more…