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

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

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

在国际象棋中，车每次可以横着或竖着走任意多格。在上述游戏中，受到规则的限制，车每次只能向左或者向下走任意多格。如果问题中的棋子是车，答案就非常简单了：你应该选择先走。你应该直接把车移到棋盘对角线上的位置（如左图所示），然后不管对方怎么走，你都把它移回到棋盘的对角线上。这样，你就能保证必胜了。

在国际象棋中，王每次可以横着、竖着或者斜着走一格。在上述游戏中，受到规则的限制，王每次只能向左、向下或者向左下方走一格。如果问题中的棋子是王，分析出问题的答案也不算太难：你应该选择先走。你应该直接把王移到棋盘的“奇格”里（如右图所示），然后不管对方怎么走，你都可以把它再次移到某个“奇格”里。这样，你就能保证必胜了。

在国际象棋中，皇后每次可以横着、竖着或者斜着走任意多格。在上述游戏中，受到规则的限制，皇后每次只能向左、向下或者向左下方走任意多格。如果问题中的棋子是皇后，那么你应该选择先走还是后走呢？这次，问题就没那么简单了。

这个“挪动皇后”的游戏是由 Rufus Isaacs 在 1960 年左右提出来的。给定皇后在棋盘上的初始位置，如何判断出谁有必胜策略呢？ Isaacs 给出了一个分析方法。

首先，第一行上的所有位置，第一列上的所有位置，以及对角线上的所有位置，都能一步直接走到棋盘的最左下角。我们可以从最左下角的位置出发，画出三条射线，把这些位置全都划掉。如果皇后位于被划掉的位置上，那么先走的人就会获胜。此时，棋盘上出现了两个死角。如果皇后在这两个地方，先走的人不得不把皇后挪到刚才被划掉的位置上，因而后走的人就必胜了。因而，从这两个地方出发，画出三条射线，被划掉的位置又是先走的人就会获胜的位置，先走的人只需要把皇后挪到这两个地方即可。此时，棋盘上又会出现两个新的死角，它们又是后走的人必胜的位置……不断这样递推下去，我们就能分析出，皇后在哪些地方时先走的人必胜，皇后在哪些地方时后走的人必胜。之前我们曾问，当皇后位于标有 × 的格子时你应该选择先走还是后走，现在我们就知道答案了：你应该后走才对。

那么，在“挪动皇后”的游戏中，哪些位置是后走的人必胜的位置呢？

画出更大的棋盘，将刚才的操作再多重复几次后，我们看见了一个非常明显的规律：这些位置大致形成了两条直线。再仔细观察，你会发现，每行每列里恰好有一个这样的位置。有没有什么公式不用递推就能找出这些位置呢？它们为什么会形成这么两条直线呢？为什么每行每列里有且仅有一个这样的位置呢？看来，这里面还有很深的水。

令 Isaacs 万万没有想到的是，这个游戏虽然是他发明的，但由此引申的问题却已经被前人解决了。 1907 年，荷兰数学家 Willem Abraham Wythoff 提出了一个双人对弈游戏，后来人们把它叫作 Wythoff 游戏。游戏规则是这样的。地上有两堆石子，其中一堆有 m 个石子，另外一堆有 n 个石子。两名玩家轮流取走石子，规定每次要么从其中一堆石子中取走任意多个石子，要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了，谁就输了。也就是说，取到最后一个石子的玩家获胜。 Martin Gardner 认为， Wythoff 本人甚至也不是这个游戏最早的发明者——其实中国很早就有了这个游戏，人们把它叫作“捡石子”。

容易看出， Wythoff 游戏和“挪动皇后”是完全等价的。把棋盘从下到上各行依次标为 0, 1, 2, 3, …，把棋盘从左到右各列依次标为 0, 1, 2, 3, …，那么皇后移动时坐标变化的规则，正好与 Wythoff 游戏中两堆石子数量变化的规则是相同的。而两个游戏的目标也是相同的：谁先将游戏状态变为 (0, 0) ，谁就获得胜利。因此，这两个游戏完全等价。

由于状态 (m, n) 和 (n, m) 本质相同，因而我们可以把游戏状态看作是无序数对，并约定在书写时总把较小的数写在前面。也就是说，今后 (1, 2) 和 (2, 1) 就统一用 (1, 2) 来表示了。另外，只要数对里面至少有一个数不为 0 ，我们就说这是一个非零数对。我们的问题就是，哪些非零数对所对应的游戏状态是后行者必胜的。

Wythoff 给出的答案异常简单——所有这样的数对从小到大依次为：

([1 · φ], [1 · φ²]), ([2 · φ], [2 · φ²]), ([3 · φ], [3 · φ²]), ([4 · φ], [4 · φ²]), …

其中 φ = (√5+ 1) / 2 ， [x] 表示不超过 x 的最大整数（当 x ≥ 0 时， [x] 可以简单地理解为取 x 的整数部分）。不妨把上述序列叫作序列 W 。稍作计算可知，序列 W 的前几项为：

(1, 2), (3, 5), (4, 7), (6, 10), (8, 13), …

对照前面那个棋盘图，我们可以看到，序列 W 还真挺靠谱。 Wythoff 证明了，序列 W 确实就是正确的答案，这是因为序列 W 满足以下三个条件：

• 条件 1 ： W 当中的任何一个数对都无法一步变成 (0, 0)
• 条件 2 ： W 当中的任何一个数对都无法一步变成 W 当中的另一个数对
• 条件 3 ： W 之外的任何一个非零数对都可以一步变成 (0, 0) 或 W 当中的某一个数对

这样的话，当游戏状态为 W 当中的数对时，先走的人只能把游戏状态变为 W 之外的非零数对，后走的人即使赢不了，也总能把游戏状态移回到 W 当中。不断这样循环下去，后走的人就赢定了。所以，如果序列 W 真的满足上面三个条件，刚才的公式就是正确的了。那么，序列 W 为什么满足上面三个条件呢？ Wythoff 进一步指出，这是因为序列 W 满足以下三个性质：

• 性质 1 ： W 里面正好既无重复又无遗漏地包含了每一个正整数
• 性质 2 ： W 当中各项里的两数之差依次为 1, 2, 3, …
• 性质 3 ： W 当中各项里的较小数依次递增

我们先来说明这三个性质为什么能推出前面的三个条件，然后再来说明这三个性质本身为什么都是成立的。性质 1 和性质 2 告诉我们： W 当中用到的数都大于 0 ，且没有重复的情况；各个数对里的两数之差也都大于 0 ，而且也没有重复的情况。这能立即推出前面的条件 1 和条件 2 。现在，假设 (a, b) 是 W 之外的某个非零数对。如果 a = 0 或者 a = b ，那么 (a, b) 可以直接变成 (0, 0) 。接下来，我们假设 0 < a < b 。由性质 1 可知，在 W 中，有且仅有一个数对用到了 a 这个数。如果 a 是这个数对里的较大数，或者说这个数对形如 (x, a) ，那么直接把 b 减小到 x ，一步就把 (a, b) 变到 W 里去了。例如， (7, 12) 是 W 之外的数对，把它变成 (4, 7) ，便一步变到 W 里去了。如果 a 是这个数对里的较小数，或者说这个数对是 (a, x) 呢？若 b 比 x 大，直接把 b 减小到 x ，同样能一步把 (a, b) 变到 W 里去。若 b 比 x 小，这就说明和 (a, x) 相比， (a, b) 里的两数之差更小。根据性质 2 ，在序列 W 当中，这个差值在 (a, x) 之前曾经出现过。所以，让 (a, b) 的两个数同时减小相同的量，就能把数对变到 W 里去了。为什么是同时减而不是同时加呢？这就是由性质 3 保证的。举例来说， (6, 11), (6, 12), (6, 13), …都能一步变为 (6, 10) ，而 (6, 7) 、 (6, 8) 、 (6, 9) 则能分别变成 (1, 2) 、 (3, 5) 、 (4, 7) 。

接下来，我们来证明序列 W 满足这三个性质。性质 1 可以直接由 Beatty-Rayleigh 定理推出。 Beatty-Rayleigh 定理说的是，若正无理数 α 和 β 满足 1 / α + 1 / β = 1 ，则数列 [1 · α], [2 · α], [3 · α], … 和 [1 · β], [2 · β], [3 · β], … 既无重复又无遗漏地包含了所有的正整数。由于 φ 和 φ²就满足 1 / φ + 1 / φ²= 1 ，所以序列 W 里的所有数既无重复又无遗漏地包含了所有的正整数。

为了保持文章的完整性，我们给出 Beatty-Rayleigh 定理的证明。 Beatty-Rayleigh 定理有很多证明方法，下面这种方法是我最喜欢的一种。首先注意到，如果 x 和 y 都不是整数，那么 [x] 严格地小于 x ，[y] 严格地小于 y ，从而 [x] + [y] < x + y 。另外，[x] 一定严格地大于 x – 1 ， [y] 一定严格地大于 y – 1 ，从而 [x] + [y] 一定严格地大于 x + y – 2。这说明，当 x 和 y 都不是整数时， [x] + [y] 将介于 x + y – 2 和 x + y 之间。

回到原问题。显然，在数列 [1 · α], [2 · α], [3 · α], … 中，小于 n 的正整数有 [n / α] 个。显然，在数列 [1 · β], [2 · β], [3 · β], … 中，小于 n 的正整数有 [n / β] 个。因此，在这两个数列中，小于 n 的正整数共有 [n / α] + [n / β] 个。由于 α 和 β 都是无理数，因此 n / α 和 n / β 不可能为整数，由刚才的结论， [n / α] + [n / β] 一定介于 n / α + n / β – 2 和 n / α + n / β 之间，即 n – 2 和 n 之间。但是， [n / α] + [n / β] 是个整数，因而它精确地等于 n – 1 。

这说明，前 n – 1 个正整数在两个数列中一共出现了 n – 1 次，这对于所有 n 都成立。于是，正整数 1 必须且只能出现在其中一个数列中，正整数 2 必须且只能出现在其中一个数列中，以此类推，每一个新的正整数都必须且只能出现在其中一个数列中。

序列 W 的性质 2 则是， W 当中各项里的两数之差依次为 1, 2, 3, … ，也就是说第 n 个数对里的两数之差恰好为 n 。这一点也是很容易看出来的。由于 φ 满足 1 + φ = φ²，因而 n + n · φ = n · φ²，即 n · φ 和 n · φ²正好相差 n 。如果两个数正好相差 n ，那么这两个数的整数部分显然也就正好相差 n 。这就证明了序列 W 满足性质 2 。

序列 W 的性质 3 则是， W 当中各项里的较小数依次递增，即 [1 · φ], [2 · φ], [3 · φ], … 依次递增。这就更显然了：在数列 1 · φ, 2 · φ, 3 · φ, … 中，后一项总比前一项大 φ ≈ 1.618 > 1 ，因此即使取整后，后一项也一定严格地大于前一项。注意到，性质 2 和性质 3 结合起来可以告诉我们， W 当中各项里的较大数也是依次递增的。

至此，我们就完整地证明了， Wythoff 提出的公式确实准确地给出了 Wythoff 游戏（也就是“挪动皇后”游戏）中后行者必胜的状态。这也顺便把我们之前挖的坑填上了。为什么把后行者必胜的状态标在棋盘上，会形成两条直线呢？看看序列 W 的公式，你就知道了：这是因为，每个数对里的前后两项之比（即横纵坐标之比）都是固定的。为什么棋盘的每行每列里都有且仅有一个标记呢？这其实完全是由序列 W 的性质 1 带来的结果。

不过，故事还远远没有结束。刚才我们给出了序列 W 的前几项，那时候你或许就已经发现了什么。让我们再多往后写几项：

(1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20), (14, 23), (16, 26), (17, 28), (19, 31), (21, 34), (22, 36), (24, 39), (25, 41), (27, 44), (29, 47), (30, 49), …

你发现了什么？有没有觉得， (1, 2) 、 (3, 5) 、 (8, 13) 、 (21, 34) 这几项都特别熟悉？没错，如果把 Fibonacci 数列里的数都依次写下来：

1, 2, 3, 5, 8, 13, 21, 34, …

然后把它们两个两个分成一组：

(1, 2), (3, 5), (8, 13), (21, 34), …

由此得到的所有数对都在序列 W 当中！事实上，我们还能预测出，上述数对都出现在了序列 W 当中的什么位置。 (1, 2) 后面的那个数对是 (3, 5) ，它就是 W 当中的第 2 个数对； (3, 5) 后面的那个数对是 (8, 13) ，它就是 W 当中的第 5 个数对； (8, 13) 后面的那个数对是 (21, 34) ，它就是 W 当中的第 13 个数对……所以， (21, 34) 后面的那个数对，就应该是 W 当中的第 34 个数对咯？简单算算你会发现，嘿，还真是！根据定义， W 当中的第 34 个数对为 [34 · φ], [34 · φ²] ，而 34 · φ ≈ 55.013 ，34 · φ²≈ 89.013 ，取整后正好就是 (55, 89) 。你或许会猜测，该不会当 n 是 Fibonacci 数时， [n · φ] 和 [n · φ²] 一定就是后面两个 Fibonacci 数吧。事实上并非如此。让我们代入 n = 21 看看： 21 · φ ≈ 33.979 ， 21 · φ²≈ 54.979 ，所得到的两个数确实很接近 21 后面的两个 Fibonacci 数，但却要偏小一些。因此，取整之后的结果是 33 和 54 ，而并不是 34 和 55 。这一切都是为什么呢？

这一切都是因为， Fibonacci 数列有一个神奇的通项公式： φⁿ/ √5– (1 – φ)ⁿ/ √5。注意，这个充满无理数的通项公式生成的并不是 Fibonacci 数的近似值，它生成的真的就是一个个的 Fibonacci 数。你可以试着把 n = 1, 2, 3, 4, 5, 6 代进去，得到的值将会精确地等于 1, 1, 2, 3, 5, 8 。

由于 φ ≈ 1.618 ，其绝对值大于 1 ，因此随着 n 的增加， φⁿ/ √5的绝对值将会迅速变得非常非常大；由于 1 – φ ≈ – 0.618 ，其绝对值小于 1 ，因此随着 n 的增加， (1 – φ)ⁿ/ √5的绝对值将会迅速变得非常非常接近于 0 。最终， φⁿ/ √5– (1 – φ)ⁿ/ √5将会无限接近于 φⁿ/ √5，一个以 φ 为公比的等比数列。这就解释了，为什么一个 Fibonacci 数的 φ 倍大致就等于下一个 Fibonacci 数。

但是，用这种方法推算出来的下一个 Fibonacci 数，究竟会偏大一些还是偏小一些呢？我们还得仔细分析一下误差。注意到 1 – φ 是个负数，因此随着 n 的增加， (1 – φ)ⁿ/ √5实际上是在正负交替地向 0 靠拢，因此 φⁿ/ √5– (1 – φ)ⁿ/ √5实际上是在一上一下地无限接近于 φⁿ/ √5。下表中的第一行依次是各个 Fibonacci 数，第二行是 n = 1, 2, 3, … 时 φⁿ/ √5的值，第三行则是二者之间的误差。

1	1	2	3	5	8	13	21	34	55	89
0.7236	1.1708	1.8944	3.0652	4.9597	8.0249	12.9846	21.0095	33.9941	55.0036	88.9978
-0.2764	0.1708	-0.1056	0.0652	-0.0403	0.0249	-0.0154	0.0095	-0.0059	0.0036	-0.0022

这就解释了，为什么 34 · φ 和 34 · φ²正好比 55 和 89 稍大一些。 34 和 55 非常接近 φ⁹/ √5和 φ¹⁰/ √5的值，其中后者是前者的 φ 倍。但 34 等于 φ⁹/ √5加上某个很小的数， 55 等于 φ¹⁰/ √5减去某个很小的数，因而 34 的 φ 倍就会比 55 略大一些了。 34 和 89 也都非常接近 φ⁹/ √5和 φ¹¹/ √5的值，其中后者是前者的 φ²倍。但 34 等于 φ⁹/ √5加上某个很小的数， 89 等于 φ¹¹/ √5加上某个更小的数，因而 34 的 φ²倍也会比 89 略大一些。类似地， 21 · φ 和 21 · φ²正好比 34 和 55 稍小一些，也是因为 21 等于 φ⁸/ √5减去某个很小的数， 34 等于 φ⁹/ √5加上某个很小的数， 55 等于 φ¹⁰/ √5减去某个更小的数。

这就回到了我们刚才观察到的现象：序列 W 中的第 2 个数对是 (3, 5) ，第 5 个数对是 (8, 13) ，第 13 个数对是 (21, 34) ，第 34 个数对是 (55, 89) ……我们也就算是证明了刚才提到的结论：把 Fibonacci 数列写下来，并且从 (1, 2) 开始，每两个数组成一个数对，则由此得到的所有数对都在序列 W 当中。

于是，我们挖的坑又只剩最后一个了：为什么 φⁿ/ √5– (1 – φ)ⁿ/ √5是 Fibonacci 数列的通项公式呢？这有一个非常具有启发性的推导方法。

让我们把满足递推式 a(n) = a(n – 1) + a(n – 2) 的数列叫作“广义 Fibonacci 数列”。而真正的 Fibonacci 数列，则可以看作是由初始条件 a(1) = 1 和 a(2) = 1 生成的。首先注意到，让广义 Fibonacci 数列里的每一项都乘上非 0 实数 c ，得到的仍然是一个广义 Fibonacci 数列。也就是说，如果数列

a(1), a(2), a(3), a(4), a(5), …

是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列，那么

c · a(1), c · a(2), c · a(3), c · a(4), c · a(5), …

就是一个由 c · a(1) 和 c · a(2) 生成的广义 Fibonacci 数列。

另外，两个广义 Fibonacci 数列之和必然也是一个广义 Fibonacci 数列。也就是说，如果数列

a(1), a(2), a(3), a(4), a(5), …

是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列，并且数列

b(1), b(2), b(3), b(4), b(5), …

是一个由 b(1) 和 b(2) 生成的广义 Fibonacci 数列，那么数列

a(1) + b(1), a(2) + b(2), a(3) + b(3), a(4) + b(4), a(5) + b(5), …

就是一个由 a(1) + b(1) 和 a(2) + b(2) 生成的广义 Fibonacci 数列。

最后， φ 和 1 – φ 是方程 1 + x = x²的两根，因而数列

φ, φ², φ³, φ⁴, φ⁵, φ⁶, …

和

1 – φ, (1 – φ)², (1 – φ)³, (1 – φ)⁴, (1 – φ)⁵, (1 – φ)⁶, …

就成了两个非常特别的广义 Fibonacci 数列。

把上面三点结合起来，我们将会得出结论：对于任意的实数 k 、 l ，数列

k · φ + l · (1 – φ), k · φ²+ l · (1 – φ)², k · φ³+ l · (1 – φ)³, k · φ⁴+ l · (1 – φ)⁴, …

都是一个广义 Fibonacci 数列。如果我们能找出合适的 k 和 l ，使得它们同时满足

k · φ + l · (1 – φ) = 1, k · φ²+ l · (1 – φ)²= 1

这两个方程，那么我们就相当于找到了 Fibonacci 数列的通项公式。解得 k = 1 / √5, l = – 1 / √5，因而 Fibonacci 数列实际上就是

φ / √5– (1 – φ) / √5, φ²/ √5– (1 – φ)²/ √5, φ³/ √5– (1 – φ)³/ √5, φ⁴/ √5– (1 – φ)⁴/ √5, …

这就是 Fibonacci 数列的通项公式。容易看出，事实上，一切的广义 Fibonacci 数列都可以表示成

k · φ + l · (1 – φ), k · φ²+ l · (1 – φ)², k · φ³+ l · (1 – φ)³, k · φ⁴+ l · (1 – φ)⁴, …

的形式，我们只需要求解关于 k 和 l 的二元一次方程组

k · φ + l · (1 – φ) = a(1), k · φ²+ l · (1 – φ)²= a(2)

即可。因此，各种广义 Fibonacci 数列也将继承 Fibonacci 数列的很多宏观特征。比方说，随着 n 的增加， k · φⁿ的绝对值将会迅速变得非常非常大（即使 k 本身的绝对值很小）， l · (1 – φ)ⁿ的绝对值将会正负交替地迅速向 0 靠拢（即使 l 本身的绝对值很大），最终 k · φⁿ+ l · (1 – φ)ⁿ将会一上一下地无限靠近 k · φⁿ。也就是说，足够多项之后，一切广义 Fibonacci 数列都会一上一下地无限近似于一个以 φ 为公比的等比数列。

Fibonacci 数列有很多神奇之处，它的通项公式只是其中之一。每次说到 Fibonacci 数列时，我都喜欢讲讲 Fibonacci 数列的另一个神奇之处，就是 Zeckendorf 定理。这是由比利时数学家 Edouard Zeckendorf 发现的：任何一个正整数都可以唯一地表示成若干个不相邻的 Fibonacci 之和。例如，100 可以表示成 89 + 8 + 3 。我们把正整数的这种表示方法叫作它的 Zeckendorf 表达。注意，虽然 100 也可以表示成 55 + 34 + 8 + 2 + 1 ，但 55 和 34 是相邻的 Fibonacci 数， 2 和 1 也是相邻的 Fibonacci 数，因此这不能算 100 的 Zeckendorf 表达。需要特别指出的是，由于 F₁和 F₂都是 1 ，因此选了 F₁和 F₃本质上就相当于选了 F₂和 F₃，根据规定，这也是不允许的。因此，接下来，我们假设每次选 1 的时候选的实际上都是 F₂，这不会改变问题的实质。换句话说，接下来，我们假设 F₁是不能选的。

为什么 Zeckendorf 表达总是存在的呢？这很容易看出来。只要不断地选取尽可能大的 Fibonacci 数，我们就能得到一个 Zeckendorf 表达。比如，如何得出 100 的一个 Zeckendorf 表达呢？不超过 100 的最大的 Fibonacci 数是 89 。从 100 里减去 89 后，剩下的部分是 11 。不超过 11 的最大的 Fibonacci 数是 8 。从 11 里减去 8 后，剩下的部分是 3 ，这已经是一个 Fibonacci 了。所以， 100 的 Zeckendorf 表达就是 89 + 8 + 3 。在这个过程中，我们肯定不会用到相邻的 Fibonacci 数。这是因为，如果正整数 N 介于 F_i和 F_i+1之间（其中 F_i表示第 i 个 Fibonacci 数），那么我们就有：

N – F_i< F_i+1– F_i= F_i-1

这说明，减去一个尽可能大的 Fibonacci 数，结果会比小一号的 Fibonacci 数更小。所以，在上面这种寻找 Zeckendorf 表达的过程中，我们会自动地跳过所有相邻的 Fibonacci 数。

Zeckendorf 定理真正最核心的，就是每一个正整数的 Zeckendorf 表达都是唯一的。为了证明这一点，让我们先来考虑两个问题。第一个问题是：从 F₂, F₃, …, F_n数中选出若干个不相邻的数，怎样选才能让它们的和最大呢？不断把较小的 Fibonacci 数往大了调，你会发现，和最大的选法显然就是

F_n+ F_n-2+ F_n-4+ …

如果 n 是偶数，上式将会以 … + F₄+ F₂结尾。如果 n 是奇数，上式将会以 … + F₅+ F₃结尾。这个数究竟等于多少呢？这个数与 F_n+1很接近。这是因为：

F_n+1

= F_n+ F_n-1

= F_n+ F_n-2+ F_n-3

= F_n+ F_n-2+ F_n-4+ F_n-5

= ……

不断像这样展开后，根据 n 的奇偶性的不同，我们要么会得到 F_n+ F_n-2+ F_n-4+ … + F₄+ F₂+ F₁，要么会得到 F_n+ F_n-2+ F_n-4+ … + F₅+ F₃+ F₂。不管是哪种情况，这都比刚才选出的最大和多了一个 1 。也就是说，从 F₂, F₃, …, F_n中选出若干个不相邻的数，最大的和为 F_n+1– 1 。

我们需要考虑的第二个问题是， n 个物体排成一排，从中选出若干个不相邻的物体（可以不选），一共有多少种不同的方案？不妨把答案记作 a(n) 。如果只有 1 个物体，我们要么选它，要么不选它，一共有 2 种选法。如果有 2 个物体，我们要么选这个，要么选那个，要么都不选，一共有 3 种选法。也就是说， a(1) = 2 ， a(2) = 3 。另外，面对 n 个物体，满足要求的选法分为两类：如果不选最后那个物体，那就完全得看前 n – 1 个物体怎么选，这里面的方案数为 a(n – 1） ；如果选了最后那个物体，那么剩下的就只能再在前 n – 2 个物体里选了，这里面的方案数为 a(n – 2) 。这说明， a(n) = a(n – 1) + a(n – 2) 。于是，数列 a(1), a(2), a(3), a(4), … 实际上就是 2, 3, 5, 8, …。换句话说， a(n) = F_{n + 2}

结合上面两点，我们得到了这样一个结论：从 F₂到 F_n这 n – 1 个数中选出若干个不相邻的数（可以不选），一共有 F_n+1种选法；而这些数的总和的取值范围，则在 0 到 F_n+1– 1 之间。所以，我们有 F_n+1种选法，有 F_n+1种可能的取值。另一方面，我们之前证明了，每个正整数都有至少一个 Zeckendorf 表达。所以， F_n+1种选法必须得既无重复又无遗漏地取遍 F_n+1种可能的取值。这就说明了，每一个正整数的 Zeckendorf 表达都是唯一的。

等等，我们是怎么扯到 Zeckendorf 表达的？让我想一想啊……哦！想起来了！想起来了！我们是从棋盘游戏，扯到与之等价的 Wythoff 游戏，扯到哪些状态后行者必胜，扯到 Wythoff 所定义的序列 W ，扯到序列 W 包含了一对一对的 Fibonacci 数，扯到 Fibonacci 数列那著名的通项公式，最后扯到了正整数的 Zeckendorf 表达。

扯远了，扯远了。我们再把整个思路捯回去。序列 W 的公式为：

([1 · φ], [1 · φ²]), ([2 · φ], [2 · φ²]), ([3 · φ], [3 · φ²]), ([4 · φ], [4 · φ²]), …

由此算出序列 W 的前几项：

(1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20), (14, 23), (16, 26), (17, 28), (19, 31), (21, 34), (22, 36), (24, 39), (25, 41), (27, 44), (29, 47), (30, 49), …

我们证明了，序列 W 满足以下三个重要的性质：

• 性质 1 ： W 里面正好既无重复又无遗漏地包含了每一个正整数
• 性质 2 ： W 当中各项里的两数之差依次为 1, 2, 3, …
• 性质 3 ： W 当中各项里的较小数依次递增

这三个性质保证了， W 当中的所有项正好是 Wythoff 游戏中后行者必胜的所有状态。然后，我们发现 W 当中有很多项里包含了 Fibonacci 数。把它们连在一起，正好就是完整的 Fibonacci 数列：

(1, 2), (3, 5), (8, 13), (21, 34), …

其中 (1, 2) 后面的 (3, 5) 正好是 W 当中的第 2 项， (3, 5) 后面的 (8, 13) 正好是 W 当中的第 5 项， (8, 13) 后面的 (21, 34) 正好是 W 当中的第 13 项，以此类推。

那么， W 当中的其他项呢？仔细观察 W 当中的其他项，你能看出什么端倪吗？答案是， W 当中的其他项还隐藏着别的广义 Fibonacci 数列！比方说， W 当中的

(4, 7), (11, 18), (29, 47), …

正好拼成一个以 4, 7 打头的广义 Fibonacci 数列！而且， (11, 18) 就是 W 当中的第 7 项， (29, 47) 就是 W 当中的第 18 项。来猜猜看， (76, 123) 会不会正好是 W 当中的第 47 项？计算可得 47 · φ ≈ 76.0476 ， 47 · φ²≈ 123.048 。根据序列 W 的定义，第 47 项真的就是 (76, 123) ！

接下来，我们就来证明这件事：如果 (a, b) 是序列 W 中的某个数对，那么序列 W 中的第 b 项就是 (a + b, a + 2b) 。由于第 b 项里的两数之差就是 b ，因此我们只需要证明：如果 (a, b) 是序列 W 中的某个数对，那么序列 W 中的第 b 项的较小数就是 a + b 。不妨假设 (a, b) 是序列 W 中的第 n 项。根据序列 W 的定义， a 就等于 [n · φ] ， b 就等于 [n · φ²] ，而第 b 项的较小数则是 [[n · φ²] · φ] 。所以，我们真正只需要证明的就是：对于任意正整数 n ，都有 [n · φ] + [n · φ²] = [[n · φ²] · φ] 。这本质上就是证明：

[n · φ] + [n · φ²] ≤ [n · φ²] · φ < [n · φ] + [n · φ²] + 1

不妨用 {x} 表示 x 的小数部分。上式就变为了

n · φ – {n · φ} + n · φ²– {n · φ²} ≤ (n · φ²– {n · φ²}) · φ < n · φ – {n · φ} + n · φ²– {n · φ²} + 1

也就是：

n · φ – {n · φ} + n · φ²– {n · φ²} ≤ n · φ³– {n · φ²} · φ < n · φ – {n · φ} + n · φ²– {n · φ²} + 1

然而， φ 满足 1 + φ = φ²，也就满足 n · φ + n · φ²= n · φ³。于是，上面的不等式进一步简化为

– {n · φ} – {n · φ²} ≤ – {n · φ²} · φ < – {n · φ} – {n · φ²} + 1

即

{n · φ} + {n · φ²} ≥ {n · φ²} · φ > {n · φ} + {n · φ²} – 1

最后，别忘了 φ 和 φ²正好相差 1 ，因而 n · φ 和 n · φ²正好相差一个整数，也就是说它们的小数部分是相等的。如果令它们的小数部分均为 r ，则上式变为

2 · r ≥ r · φ > 2 · r – 1

由于 r 是一个 0 到 1 之间的数，而 φ ≈ 1.618 ，所以上式显然成立。至此，我们就证明了，对于任意正整数 n ，都有 [n · φ] + [n · φ²] = [[n · φ²] · φ] 。

利用取整符号和常数 φ ，我们还能构造出很多类似的恒等式。用上面的这套方法来证明这些恒等式，则显得格外有效。为了说明这一点，我打算不惜文章的连贯性，在此处穿插一个习题。这是我最近见到的一个题目。讲完这个题目的解法后，我们会立即言归正传。题目是：求证，对于任意正整数 n ，都有 [[n · φ] · φ] = [n · φ²] – 1 。

解法和之前的几乎如出一辙。原等式等价于

[n · φ²] – 1 ≤ [n · φ] · φ < [n · φ²]

它又可以变成

n · φ²– {n · φ²} – 1 ≤ (n · φ – {n · φ}) · φ < n · φ²– {n · φ²}

即

n · φ²– {n · φ²} – 1 ≤ n · φ²– {n · φ} · φ < n · φ²– {n · φ²}

即

– {n · φ²} – 1 ≤ – {n · φ} · φ < – {n · φ²}

即

{n · φ²} + 1 ≥ {n · φ} · φ > {n · φ²}

由于 {n · φ} = {n · φ²} ，因此我们把它们都换成 r 。整个式子就变为了：

r + 1 ≥ r · φ > r

同样地，由于 r 是一个 0 到 1 之间的数，而 φ ≈ 1.618 ，所以上式显然成立。

如果序列 W 当中有 (a, b) 和 (a + b, a + 2b) 这么两项，我们就说， (a + b, a + 2b) 接在 (a, b) 后面。而我们刚才证明的实际上就是，序列 W 当中的第 [1 · φ²], [2 · φ²], [3 · φ²], … 项将会分别接在第 1, 2, 3, … 项的后面。把该接起来的数对全都接起来，我们就会得到很多链条，比如之前就已经观察到的

(1, 2), (3, 5), (8, 13), (21, 34), …

和

(4, 7), (11, 18), (29, 47), …

显然，每个链条里的数都构成了一个广义 Fibonacci 数列。而每个链条打头的数对，则是那些不能接在任何数对后面的数对，也就是第 [1 · φ²], [2 · φ²], [3 · φ²], … 项以外的数对。由 Beatty-Rayleigh 定理可知，它们正好就是 W 当中的第 [1 · φ], [2 · φ], [3 · φ], … 项。所以，我们把 W 当中的第 [1 · φ], [2 · φ], [3 · φ], … 项竖着写成一列，再不断地写出每个数对后面接着的数对，就能完整地给出 W 当中的数对产生的所有链条了。联想到 W 里面既无重复又无遗漏地包含了每一个正整数，因而我们相当于把全体正整数排成了一张无限大的数表，每个正整数都恰好只用了 1 次，使得数表中的每一行都是一个广义 Fibonacci 数列！我们把这个神奇的数表叫作 Wythoff 数表。

(1, 2) – (3, 5) – (8, 13) – (21, 34) – (55, 89) – (144, 233) – …

(4, 7) – (11, 18) – (29, 47) – (76, 123) – (199, 322) – (521, 843) – …

(6, 10) – (16, 26) – (42, 68) – (110, 178) – (288, 466) – (754, 1220) – …

(9, 15) – (24, 39) – (63, 102) – (165, 267) – (432, 699) – (1131, 1830) – …

(12, 20) – (32, 52) – (84, 136) – (220, 356) – (576, 932) – (1508, 2440) – …

(14, 23) – (37, 60) – (97, 157) – (254, 411) – (665, 1076) – (1741, 2817) – …

(17, 28) – (45, 73) – (118, 191) – (309, 500) – (809, 1309) – (2118, 3427) – …

… … … … … … …

真正神奇的事情出现了。现在，我们约定，接下来所说的广义 Fibonacci 数列一律限定在正整数范围内。如果两个广义 Fibonacci 数列的本质完全相同，只是下标被整体平移了一下，我们就认为它们俩是同一个数列。比方说，以 2, 1 打头的广义 Fibonacci 数列（这叫作 Lucas 数列）为：

2, 1, 3, 4, 7, 11, 18, 29, 47

它就是 Wythoff 数表中的第二行。接下来，我们来证明一个非常让人震惊的事实：在这个意义下， Wythoff 数表包含了所有可能的广义 Fibonacci 数列！

证明方法很简单。还记得吗，我们之前曾经得出，一切广义 Fibonacci 数列最终都会一上一下地无限地近似于一个以 φ 为公比的等比数列。所以，如果 a(1), a(2), a(3), … 是一个广义 Fibonacci 数列，那么我们一定能在找到某个 n ，使得 a(n + 1) = [a(n) · φ] ，并且 a(n + 2) = [a(n) · φ²] 。然而， ([a(n) · φ], [a(n) · φ²]) 就是序列 W 当中的第 a(n) 项，它出现在了 Wythoff 数表的某一行里。这一行所对应的广义 Fibonacci 数列，本质上就是数列 a(1), a(2), a(3), … 。

我们证明了一个如此优美的结论，将之前的所有东西都贯穿在了一起，一切都非常漂亮地完结了。再来一个简单的收尾后，这篇文章就该结束了。毕竟，我们之前挖过的所有坑都填上了，我们之前提过的所有东西都用到了。呃……是吗？

编故事有一个非常重要的原则，叫作“契科夫之枪”（Chekhov’s gun）。它说的是：如果你在第一章里提到了墙上挂着一把来复枪，那在第二章或者第三章里面它一定会开火，否则它就不应该挂在那里。举个例子：主人公踏上征途之前，一哥们儿给他递上一件东西并说：“把这个带上吧，没准儿能用上……”好，这玩意儿百分之百地会被用上。如果故事片里有一个镜头专门对着播报新闻的电视，记住了，这肯定和剧情有联系。如果枪战片里的人来到一个大房间，四壁都是养着鱼的大水缸……呵呵，我不说你都知道一会儿会出现啥。

这篇文章也挂着好几把契科夫之枪。比方说，刚才突然来的那个习题是怎么回事？在那个习题中，我们证明了 [[n · φ] · φ] = [n · φ²] – 1 恒成立。好了，现在考虑 Wythoff 数表的第 n 行，它是一个广义 Fibonacci 数列。如果再把这个数列往前推两项，会得到什么？注意到， Wythoff 数表的第 n 行是以序列 W 当中的第 [n · φ] 项打头的。也就是说， Wythoff 数表的第 n 行的头两个数是 [[n · φ] · φ], [[n · φ] · φ²] 。由于一个数的 φ 倍和 φ²倍（以及它们同时取整后的结果）正好相差这个数本身这么多，因此 [[n · φ] · φ²] – [[n · φ] · φ] = [n · φ] ，并且 [[n · φ] · φ] – [n · φ] = [n · φ²] – 1 – [n · φ] = n – 1 。这就说明， Wythoff 数表的第 n 行可以看作是由 n – 1, [n · φ] 生成的广义 Fibonacci 数列。所以，我们得到了 Wythoff 数表的一个等价定义：在第 -1 列依次写下 0, 1, 2, 3, … ，在第 0 列对应地依次写下 [1 · φ], [2 · φ], [3 · φ], … ，于是每一行里都有两个数了；在每一行里都不断往后面写下新的数，每个数都是它的前面两个数之和，最后得到的就是 Wythoff 数表——它既无重复又无遗漏地包含了所有正整数，也既无重复又无遗漏地包含了所有广义 Fibonacci 数列。

0	1	1	2	3	5	8	13	21	34	55	89	…
1	3	4	7	11	18	29	47	76	123	199	322	…
2	4	6	10	16	26	42	68	110	178	288	466	…
3	6	9	15	24	39	63	102	165	267	432	699	…
4	8	12	20	32	52	84	136	220	356	576	932	…
5	9	14	23	37	60	97	157	254	411	665	1076	…
6	11	17	28	45	73	118	191	309	500	809	1309	…
…	…	…	…	…	…	…	…	…	…	…	…	…

还记得 Zeckendorf 表达吗？接下来，该轮到它返场了！现在我们定义，把一个正整数的 Zeckendorf 表达里的所有 Fibonacci 数都往后移一位，得到的新的正整数就是原正整数的 “Fibonacci 后继” 。例如， 100 的 Zeckendorf 表达是 89 + 8 + 3 ，其中 89 的下一个 Fibonacci 数是 144 ， 8 的下一个 Fibonacci 数是 13 ， 3 的下一个 Fibonacci 数是 5 。那么， 100 的 Fibonacci 后继就是 144 + 13 + 5 ，也就是 162 。我们用 S(n) 来表示正整数 n 的 Fibonacci 后继。刚才我们演示的就是， S(100) = 162 。接下来，我们将证明这么一个结论：对于任意正整数 n 都有， 1 + S(n) 等于 [(n + 1) · φ] 。

如果 n 的 Zeckendorf 表达中各个 Fibonacci 数的下标为 i₁, i₂, i₃, … ，令

X = φ^i₁+ φ^i₂+ φ^i₃+ …

令

Y = (1 – φ)^i₁+ (1 – φ)^i₂+ (1 – φ)^i₃+ …

那么 n 就可以写成

X / √5– Y / √5

由于 1 – φ 是一个绝对值小于 1 的负数，因而当 i₁, i₂, i₃, … 正好是全体正偶数时， Y 的值达到最大。利用等比数列的求和公式可知， Y 的最大值是 φ – 1 ≈ 0.618 。对应地，当 i₁, i₂, i₃, … 正好是全体大于 1 的正奇数时， Y 的值则达到最小（注意，在 Zeckendorf 表达里， Fibonacci 数的下标不能取 1 ）。利用等比数列的求和公式可知， Y 的最小值是 φ – 2 ≈ – 0.382 。当然，对于任意一个有限大的 n 来说，刚才算出的最大值和最小值都是取不到的。

为了把 n 变成 S(n) ，我们只需要把 X 里的每一个 φ 和 Y 里的每一个 (1 – φ) 的指数都变大一号即可。于是， 1 + S(n) 就可以表示为：

1 + φ · X / √5– (1 – φ) · Y / √5

而我们要证明 1 + S(n) = [(n + 1) · φ] ，也就是

1 + φ · X / √5– (1 – φ) · Y / √5= [φ · X / √5– φ · Y / √5+ φ]

由于等式左边的式子是一个整数，因此我们只需要证明等式右边的取整符号内的式子比等式左边的式子更大，但不会大 1 或更多。也就是说，我们只需要证明：

0 ≤ (φ · X / √5– φ · Y / √5+ φ) – (1 + φ · X / √5– (1 – φ) · Y / √5) < 1

而

(φ · X / √5– φ · Y / √5+ φ) – (1 + φ · X / √5– (1 – φ) · Y / √5)

= (1 – φ) · Y / √5– φ · Y / √5+ φ – 1

= (1 – 2φ) · Y / √5+ φ – 1

是一个关于 Y 的一次函数，且当 Y = φ – 2 时函数值为 1 ， Y = φ – 1 时函数值为 0 。这就说明，这个一次函数的函数值永远在 0 和 1 之间。至此，我们就证到了， 1 + S(n) 等于 [(n + 1) · φ] 。

之前我们提到了 Wythoff 数表的等价定义：在第 -1 列依次写下 0, 1, 2, 3, … ，在第 0 列对应地依次写下 [1 · φ], [2 · φ], [3 · φ], … ，然后每一行都不断往后面接着写，使得每个数都是它的前面两个数之和。由于 1 + S(n) 等于 [(n + 1) · φ] ，因此上面这个等价定义可以进一步改成：在第 -1 列依次写下 0, 1, 2, 3, … ，在第 0 列对应地依次写下 1 + S(0), 1 + S(1), 1 + S(2), … （这里，我们规定 S(0) = 0 ），然后每一行都不断往后面接着写，使得每个数都是它的前面两个数之和。

所以，第 1 列的数就应该依次为 0 + (1 + S(0)), 1 + (1 + S(1)), 2 + (1 + S(2)), … 。仔细想一想， n + (1 + S(n)) 究竟是什么？容易观察到， n + S(n) 的 Zeckendorf 表达与 n 的 Zeckendorf 表达有非常直接的联系。如果 n 等于 F_i1+ F_i2+ … + F_ik，那么 S(n) 就等于 F_i1+1+ F_i2+1+ … + F_ik+1，于是 n + S(n) 就等于 F_i1+2+ F_i2+2+ … + F_ik+2。可见， n + S(n) 的 Zeckendorf 表达就是 n 的 Zeckendorf 表达中所有 Fibonacci 数都往后移两位而得的，显然它里面不包含 F₂和 F₃，最小的一项至少都是 F₄。因此，为了得到 n + (1 + S(n)) 的 Zeckendorf 表达，我们只需要在 n + S(n) 的 Zeckendorf 表达里直接添加一个 F₂就行了。

举个例子，如果某一行的第 -1 个数是 F₂+ F₄+ F₉，那么第 0 个数就是 1 + F₃+ F₅+ F₁₀，第 1 个数就是 F₂+ F₄+ F₆+ F₁₁。那么，这一行的第 2 个数是多少呢？由于第 2 个数是第 0 个数和第 1 个数之和，因此第 2 个数就是 F₃+ F₅+ F₇+ F₁₂，其中 1 和 F₂合并后得到了 F₃。类似地，由于第 3 个数是第 1 个数和第 2 个数之和，因此第 3 个数就是 F₄+ F₆+ F₈+ F₁₃；由于第 4 个数是第 2 个数和第 3 个数之和，因此第 4 个数就是 F₅+ F₇+ F₉+ F₁₄……规律已经非常明显了：在 Wythoff 数表当中，每一行的第 1 个数的 Zeckendorf 表达的最小项都是 F₂，并且今后的每一个数都是它前一个数的 Fibonacci 后继，其 Zeckendorf 表达的最小项依次升级为 F₃, F₄, F₅, … ！

回想 Wythoff 数表最早最早的定义：不断把那些不能接在任何数对后面的数对拎出来打头所得的一行一行的链条。因此，每一行打头的数都是在前面从来没有出现过的数中最小的数。所以，我们有了一种另类的生成 Wythoff 数表的方式。先在第一行的开头写下 1 。在它的右边不断写下 S(1), S(S(1)), S(S(S(1))), … 此时，在所有仍未出现的数中，最小的数是 4 。接下来，我们就在第二行的开头写下 4 ，并在它的右边不断写下 S(4), S(S(4)), S(S(S(4))), … 。此时，在所有仍未出现的数中，最小的数是 6 。接下来，我们就在第三行的开头写下 6 ，并在它的右边不断写下 S(6), S(S(6)), S(S(S(6))), … 。此时，在所有仍未出现的数中，最小的数是 8 。接下来，我们就在第四行的开头写下 8 ……不断这样做下去，我们就会得到一张无限大的数表，它就是 Wythoff 数表。这是 Wythoff 数表的另一个等价定义。

另外， Wythoff 数表的第 -1 列为 0, 1, 2, 3, … ，第 0 列依次为 [1 · φ], [2 · φ], [3 · φ], … ，这两列都是递增的。第 1 列的数等于第 -1 列的数和第 0 列的数之和。由于大点儿的数加上大点儿的数，和肯定也会更大，所以第 1 列的数也是递增的。同理，第 2 列，第 3 列，以至于今后的每一列，都是递增的。于是， Wythoff 数表还有这么一种生成方式：在第 1 列从小到大列出所有 Zeckendorf 表达的最小项为 F₂的数，在第 2 列从小到大列出所有 Zeckendorf 表达的最小项为 F₃的数，在第 3 列从小到大列出所有 Zeckendorf 表达的最小项为 F₄的数……不断这样做下去，我们就会得到一张无限大的数表，它就是 Wythoff 数表。这是 Wythoff 数表的又一个等价定义。

最后让我们回到“挪动皇后”和 Wythoff 游戏。 Wythoff 游戏的所有后行者必胜的状态构成了序列 W ，它的公式为：

([1 · φ], [1 · φ²]), ([2 · φ], [2 · φ²]), ([3 · φ], [3 · φ²]), ([4 · φ], [4 · φ²]), …

反过来，如果你面对的状态在序列 W 以外，那么你就是必胜的。但是，必胜的策略是什么呢？必胜的策略自然就是，把当前状态变成序列 W 当中的某个状态。但是，到时候你怎么才能算出，究竟应该变成序列 W 当中的哪个状态呢？早些时候，我们证明了，变法确实是存在的（见序列 W 所满足的第 3 个条件）。但是，利用当时的证明方法，很难得出一套固定的、易实施的具体策略，可以帮我们每次都准确地找出这个变法。毕竟，在没有高精度计算器的情况下，你甚至连 W 里的每一项具体是多少都搞不出来。然而，最后那几个 Wythoff 数表的等价定义是非常离散的，这给上述问题的解决开辟了一条新路。比如，我们可以立即得出，数对 (a, b) 在序列 W 当中，当且仅当 a 的 Zeckendorf 表达的最小项的下标是一个偶数，并且 b = S(a) 。所以，我们就有了一种判断数对是否在 W 当中的方法。刚才证明过恒等式 1 + S(n) = [(n + 1) · φ] ，据此可以推出 S(n – 1) + 1 = [n · φ] ；于是，序列 W 当中的第 n 项就是 (S(n – 1) + 1, S(S(n – 1) + 1)) 。再结合之前给出的序列 W 满足条件 3 的证明，最终得出的结论将会正好与 1977 年 Robert Silber 对 Wythoff 游戏的分析结果完全一致：若数对 (a, b) 不在序列 W 当中（其中 0 < a < b ），则按照下述三种情况进行分类讨论，一定能把它变成序列 W 当中的某个数对。三种情况分别如下：

• 若 a 的 Zeckendorf 表达的最小项的下标是一个奇数，则把 b 变成 S^-1(a) 。这里 S^-1(x) 表示把 x 的 Zeckendorf 表达里的所有 Fibonacci 数都往前移一位之后得到的结果。
• 若 a 的 Zeckendorf 表达的最小项的下标是一个偶数，并且 b > S(a) ，则 b 变成 S(a) 。
• 若 a 的 Zeckendorf 表达的最小项的下标是一个偶数，并且 b < S(a) ，那该怎么办呢？先计算出 b – a 的值，不妨把它记作 n ；然后，把 (a, b) 变成 (S(n – 1) + 1, S(S(n – 1) + 1)) 即可。

在写这篇文章的过程中，我看了很多资料。 1907 年， Willem Abraham Wythoff 在 A Modification of the Game of Nim 一文中提出了 Wythoff 游戏。 1977 年， Robert Silber 在 Wythoff’s NIM and Fibonacci Representations 一文中给出了基于 Fibonacci 数的分析。 Martin Gardner 在 Penrose Tiles to Trapdoor Ciphers 一书中对它们做了介绍。这三位作者的名字之前都有提过。 Wythoff 数表最早是 1980 年由 David Morrison 在 A Stolarsky Array of Wythoff Pairs 一文中提出的。它和 Zeckendorf 表达的关系则可以参见 Clark Kimberling 的 The Zeckendorf Array Equals the Wythoff Array 一文。与 Zeckendorf 表达本身有关的一些证明，尤其是 Zeckendorf 定理的证明，参考了 Tamás Lengyel 的 A Counting Based Proof of the Generalized Zeckendorf’s Theorem 一文。利用取整符号和常数 φ 能够构造出很多的恒等式，其证明方法参考了 Ian Connell 的 Some Properties of Beatty Sequences I 一文。我最早是因为看了 Neil Sloane 的 My Favorite Integer Sequences 一文后，了解到 Wythoff 数表，才打算写这篇文章的。为了把这一切联系在一起，形成一篇完整的文章，我写下了很多自己的理解，甚至有些地方的证明过程也是我自己的思考。如果有不对的地方，请网友们及时提出。

在数学世界里，各种数学研究对象织成了一张纵横交错的大网，捡石子游戏、 Wythoff 数表和 Fibonacci 数列只是其中的三个非常小的顶点而已。 2 万多字之后，我们终于把它们之间的种种关系理了个半清。但是，它们各自还能继续向外延伸，这些恐怕再花 20 万字也说不完。 Wythoff 游戏是 Nim 游戏的一个变种，后者在组合游戏理论中占据着非常核心的地位。对 Wythoff 游戏本身进行推广，还可以得到一系列类似的游戏。例如，把两堆石子换成三堆石子、四堆石子甚至 n 堆石子，情况又会怎样？很多数学家都对此有过研究。本文提到了 Wythoff 数表的很多令人意想不到的等价定义和非常让人震撼的数学性质，但这并不是 Wythoff 数表的全部。例如，在 Wythoff 数表中，下一行的每个数的大小正好夹在上一行数的空隙之间。这背后会涉及到非常有趣的 interspersion 和 dispersion 理论。 Wythoff 数表里既无重复又无遗漏地包含了所有正整数，那么从 1 开始的每个正整数究竟出现在了 Wythoff 数表中的哪一行呢？这个问题的答案就又构成了一个数列：

0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, …

这里我们规定， Wythoff 数表的首行为第 0 行。这个数列本身又有很多可圈可点之处，例如删掉数列中的第一个 0 、第一个 1 、第一个 2 等等，剩下的数列其实就是原数列本身。因此，这个数列具有分形的特征！当然，考察每个正整数究竟出现在了 Wythoff 数表中的哪一列，我们又可以得到一个数列，它也有很多独特的性质。

Fibonacci 数列和 Zeckendorf 表达里面的水就更深了。我之前曾经介绍过 Hofstadter 的非线性递推数列（https://www.cdsy.xyz/study/readingroom/221117/cd37985.html），里面就涉及到了它们之间的各种更深层的联系。