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

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

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

Read more…

趣题:无限多层嵌套的逻辑推理

大家一定见过很多“我不知道,我也不知道,我还是不知道,我还是不知道,我知道了,我也知道了”的问题。但是,我想大家一定没有见过下面这样的问题。

A 、 B 两人在主持人 C 的带领下玩一个游戏。 C 向两人宣布游戏规则:“一会儿我会随机产生两个不同的形如 n – 1/2k – 1/2k+r 的数,其中 n 、 k 是正整数, r 是非负整数。然后,我会把这两个数分别交给你们。你们每个人都只知道自己手中的数是多少,但不知道对方手中的数是多少。你们需要猜测,谁手中的数更大一些。”这里,我们假设所有人的逻辑推理能力都是无限强的,并且这一点本身也成为了共识。 C 按照规则随机产生了两个数,把它们交给了 A 和 B ,然后问他们是否知道谁手中的数更大。于是有了这样的一段对话。 Read more…

Thue-Morse 序列与免平方字符串

字符串 hello 当中连续出现了两个 l 。字符串 prototype 当中连续出现了两个 ot 。字符串 nonsense 当中连续出现了两个 nse 。如果某个字符串中连续出现了两个相同的片段,换句话说这个字符串里面含有形如 XX 的模式(其中 X 代表一个子串),我们就说这个字符串中含有一个“平方”(square)。如果某个字符串中没有平方出现,我们就说这个字符串是“免平方”的(square-free)。

如果只使用两种字符,比方说字符 0 和字符 1 的话,我们只能构造出一些长度非常有限的免平方字符串。事实上,我们只能构造出以下 6 个免平方字符串: 0 、 1 、 01 、 10 、 010 、 101 。然而,如果允许使用三种字符,比方说字符 0 、 1 、 2 的话,我们不但能够构造出任意长的免平方字符串,还能构造出无限长的免平方字符串。在继续阅读下去之前,你不妨先自己试试看。

Read more…

为什么Fibonacci数列相邻两项之比会趋于0.618?

    你或许熟知一个非常经典的结论: Fibonacci 数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … (头两项都是 1 ,此后每一项都是前两项之和)的相邻两项之比将会越来越接近黄金比例 0.618 ,不信请看:

      1 / 1 = 1.0000000…
      1 / 2 = 0.50000000…
      2 / 3 = 0.66666667…
      3 / 5 = 0.60000000…
      5 / 8 = 0.62500000…
      8 / 13 = 0.61538462…
      13 / 21 = 0.61904762…
      21 / 34 = 0.61764706…
      34 / 55 = 0.61818182…
      55 / 89 = 0.61797753…
      89 / 144 = 0.61805556…
      144 / 233 = 0.61802575…
      … …

    Fibonacci 数列究竟是怎么和黄金比例扯上关系的?一个简单的解释就是,假设相邻两项之比存在一个极限,那么到了无穷远的时候,连续的三个数 a, b, a + b 将会满足 a / b = b / (a + b) ,这正好就是黄金比例的定义。我最近用 Mathematica 做了一组动画,尝试着用图形化的方法更直观地展示 Fibonacci 数列和黄金比例之间的联系。

Read more…