漫长却有限的游戏——古德斯坦序列

不久前我讲过一些序数方面的知识，今天跟大家聊一个序数的应用。这个应用本身也是一个非常好玩的大数。关于这个大数，我先回顾一个可能大家已经非常熟悉的，有关国际象棋的故事：

古代印度某个国王很喜欢下国际象棋，他决定给国际象棋的发明者一点奖赏。他就把这个发明者叫到了皇宫来，问他要什么奖赏。这个发明者说：“陛下，我要这样的一个奖励。请你在棋盘的第一个格子里放上一粒麦子，第二格放两粒麦子，第三格放四粒麦子。以此类推，每一格都放上前一格两倍数量的麦子，直到把64格都放满，这就是我要的奖励。”

国王一听，这还不简单吗，马上让人来把麦子拿进来，开始往棋盘上放麦子。但是很快，国王发现麦子完全不够用了，填满64格是一个不可能完成的任务。如果你具体算一下大概需要多少麦子的话，你会发现这个奖励需要地球上两千年的麦子产量。

这个故事我小时候看过之后，印象是很深的，它说明人对指数增长的数字大小感受能力是有限的。故事里实际需要的麦子数量，如果写出来也就是 $2^{64}-1$ 粒麦子，这个数字看上去一点都不大，但是实际大小已经远超过了常人的感受能力了。

那么现在我把这个故事稍微改造下，改成一个拿走麦子的游戏，并且可以构造出一个更大的数字。方法是这样：

一开始先在棋盘的64格里，每一格放一粒麦子。然后按如下规则，从棋盘上拿走麦子。每一步执行如下的操作：

开始时步数为1.
如果第一个格里有麦子，则从第一格拿走1粒麦子。当前步骤完成，步数增加1，重复执行下一步。
如果第一格里没有麦子，则从第二格“借麦子”。借麦子的规则是：如果当前在执行第n步，第a格里的麦子，可以转换成第a-1格里的n粒麦子。比如第二格里的1粒麦子，可以转换成第一格里的n粒麦子。第三格里的1粒麦子，可以转换成第二格里的n粒麦子等等。其实这个规则就是类似于减法借位规则，只不过借位不是固定以10进制为转换单位，而是以当前步数为单位。不管怎样，借位转换完成后，当第一个里有麦子了，那么就从第一格里拿走一粒麦子，当前步骤完成，步数增加1，重复执行下一步。

稍微推演下这个流程：

(上图：拿走麦子游戏中，对1-4格在前65步情况的推演。数字为该步骤开始时，格子里的麦子数)

第一步时，第一格有一粒麦子，那么直接拿走，进入第二步。

第二步时，第一格没有麦子，需要向第二格借。按规则，因为现在是第二步，所以第二格的那一粒麦子可以转换为第一格的2粒麦子。那么就拿走第二格的那粒麦子，在第一格放入两粒麦子。现在第一格有麦子了，那么从第一个拿走一粒麦子。

第三步：第一格里还有一粒麦子，直接拿走，进入第四步。

第四步时：第一格没有麦子了，向第二格借。第二格此时也没有麦子了，那么要向第三格借。则拿走第三格的一粒麦子，转换成第二格的4粒麦子，因为现在是第4步，转换比例是1比4。再拿走第二格的1粒，转换成第一格的4粒麦子。此时再从第一格拿走1粒麦子。这一步结束。结束状态就是第三格空了，第二格有3粒麦子，第一格也有3粒麦子。

之后的推演就不一一解说了，可以想象到，到第8步时，第一格又空了，要向第二格借。此后每次到了 $2^n$ 步时，第一个格会为空，需要向第二格借。每次约到了 $2^{2^n}$ 步（读者可以自己考虑推导一下准确的表达式）时，第一格和第二格会空，需要向第三格借，等等。

现在的问题是，如此操作，有可能把棋盘上所有麦子拿空吗？稍微想一下，你会发现肯定能拿空。

因为无论第一格有多少粒麦子，总能拿空。第一格拿空的话，总需要向第二格借。那么无论第二格有多少粒麦子，也迟早能拿空，第二格也总需要向上一格借。如此，有点像数学归纳法，我们知道第64格也总能被拿空。第64格能拿空，后面的格子自然也会拿空，总体必然能在有限步骤内结束。

如果要定量分析的话，也很简单。你会发现其实棋盘在任何一步的状态其实是表示了一个64位的数字，这个数字的进制数就是当前的步数。比如第10步的时候，这个棋盘第64格里的1粒麦子就相当于 $10^{63}$ 粒麦子，第11步的时候就变成 $11^{63}$ 粒。所以，这个棋盘就相当于一个64位的数字，但是进制数是每步递增1，所以整个数字一开始增加是非常快的。

但你也会发现，这个过程中，最高位的数字是不会增加，只是底数在增加，所以它迟早最会被拿空。虽然需要的步数大的非常恐怖了，但是还是有限的。

那么以上游戏中，我们的整个操作步骤，等价于“弱古德斯坦序列”。

对于任意正整数n，第n个弱古德斯坦序列 { $g_1$ , $g_2$ , $g_3$ , …}按如下方式定义：

$g_1 = n$

对于k > 1，将 $g_{k-1}$ 写成k进制表示，然后将其视为k+1进制的数，最后减去1，得到 $g_k$ 。

当 $g_k$ 变为0时序列终止。

例如，第6个弱古德斯坦序列为{6, 11, 17, 25, …}：

$g_1 = 6$

$g_2 = 11$ ，因为 $6 = 110_2$ (下标的2表示2进制表示)，然后 $110_3 = 12$ ，最后 $12 - 1 = 11$ 。

$g_3 = 17$ ，因为 $11 = 102_3$ ，然后 $102_4 = 18$ ，最后 $18 - 1 = 17$ 。

$g_4 = 25$ ，因为 $17 = 101_4$ ，然后 $101_5 = 26$ ，最后 $26 - 1 = 25$ 。

依此类推。

如果用g(n)表示以n开始的弱古德斯坦序列的长度，即游戏结束所需步数，则有如下上下界：

$g(7)=2045$

$g(8)=3 \times 2^{402,653,211}-3$

$2\uparrow ^{n-1} n <g(2^n)<2\uparrow ^{n} n$

(“ $\uparrow$ ” 为 “高德纳箭号表示法”)

当然它是一个增长很快的大数序列，但是既然它叫“弱古德斯坦序列”，那么必然还有一个比它更强的原版的古德斯坦序列。

原版的古德斯坦序列是对弱古德斯坦序列进行这样一个扩展：

假设一开始的国际级象棋棋盘的每个格子里，又有一个更小的有若干格子的棋盘，这个小棋盘的每一格里，又可以嵌套若干层更小的棋盘，其他规则不变，那么情况会如何？

稍微思索一下，你会发现这样一个惊人事实：

无论一开始的棋盘有多少个格子，每个格子里嵌套了多少重棋盘，在每个格子里放入了多少粒麦子，只要一开始的状态是确定，那么最终总能拿走所有麦子！

其实这个道理还是很容易想的，因为我们分析过弱古德斯坦序列的情况，我们知道只要任意一格能拿完，那么它的上一格就能拿完。上一格能拿完，这一层的棋盘就能拿完。这一层能拿完，那么就表示承托这一层棋盘的格子能拿完，那么就又回到开始的推理了。这一层层递归推理下去，整个棋盘必能拿完。

数学中古德斯坦序列的确切构造方法（文字部分参考了 https://zhuanlan.zhihu.com/p/106647826）：

（1）随便给出一个自然数，比如本文题图中的那个数——100，设为 $M_1$ ；

（2）把 $M_1$ 表示成以2为底数的各个幂的和，也就是表示为二进制的形式；然后把所有的大于2的指数也表示成二进制的形式；如果指数上的指数还有大于2的，也将其表示为二进制的形式，以此类推，直到出现的所有数都小于等于2:

$M_1=100 = 2^{6}+2^{5}+2^2=2^{2^{2} + 2} + 2^{2^{2} + 1} + 2^{2}$

（3）把（2）里面表达形式中的数字2替换为3，然后把得到的新的数再减去1，得到 $M_2$ :

$M_2=3^{3^{3} + 3} + 3^{3^{3} + 1} + 3^{3}-1$

$=3^{3^{3} + 3} + 3^{3^{3} + 1} + 2\cdot 3^{2} + 2\cdot 3 + 2\cdot 1$

$=228767924549636$

（4）再把得到的$M_2$表示成以3为底数的各个幂的和，也就是表示为三进制的形式；然后把所有大于3的指数也表示成三进制的形式；以此类推，直到出现的所有数都小于等于3；

（5）把（4）中的表达形式中的数字3替换为4，然后把得到的新的数再减去1，得到 $M_3$ ；

$M_3=4^{4^{4} + 4} + 4^{4^{4} + 1} + 2\cdot 4^{2} + 2\cdot 4$

$+ 2\cdot 1 -1$

（6）一直按照这种模式做下去……，得到的数列 ${M_{1}, M_{2}, M_{3}, \ldots \ldots}$ 被称为以 $M_1$ 为初始值的古德斯坦数列；

（7）古德斯坦定理预言，无论初始值是哪个自然数，古德斯坦数列都会在有限步之后收敛到 0 ！

如果G(n)记作以n开始的古德斯坦序列的长度，那么n=1到10时，有如下上下界：

更有意思的一点是，古德斯坦序列有一个性质，它的有限性在皮亚诺算术公理系统中是无法证明的。这一点粗看有点令人惊讶，因为之前用那种启发性的思考，我们已经可以相信这个拿走麦子的游戏可以在有限步骤内结束。但如果仔细想想，你还是能发现它不能用皮亚诺算术证明的蛛丝马迹。

皮亚诺算术公理介绍（转自维基百科）：

皮亚诺的这五条公理用非形式化的方法叙述如下：

0是自然数；
每一个确定的自然数a，都有一个确定的后继数a’ ，a’ 也是自然数；
对于每个自然数b、c，b=c当且仅当b的后继数=c的后继数；
0不是任何自然数的后继数；
任意关于自然数的命题，如果证明：它对自然数0是真的，且假定它对自然数a为真时，可以证明对a’ 也真。那么，命题对所有自然数都真。

其中，一个数的后继数指紧接在这个数后面的数，例如，0的后继数是1，1的后继数是2等等；公理5保证了数学归纳法的正确性，从而被称为归纳法原理。

对这种命题，你可能直接能想到的就是数学归纳法。数学归纳法的基本方法就是，对某个命题在n-1的情况你假设命题成立，然后考虑在n的情况，命题仍然成立。但是对这个拿走麦子的游戏，有个问题是，无法准确的说出n-1和n的情况到底是啥？因为每个棋盘上的每个格子里可能存在另一个拿走麦子的游戏，这种层层嵌套的结构，形成了一种你中有我，我中有你的形式，使得用数学归纳法的时候总是陷入循环论证的困境。

就是说，当假设n-1的成立的时候，似乎就是在假设原命题成立了，这是不允许的。所以皮亚诺算数公理证明不出这个命题。

而如果序数理论的话，证明古德斯坦序列的有限性则是出奇得简单。这里我们要用到序数的两个简单性质：

第一个：序数是良序集。也就是序数本身都可以比较大小，并且任何一组序数在一起比较少时，总有一个最小的序数。这个性质有一个推论：序数序列中，不存在无穷递降链。当把一群序数从大到小排列，那么这个序列就叫递降链，且这个递降序列长度必然是有限的，因为总有一个最小的序数。这个性质也是所有良序集的性质，即：良序集中不存在无穷递降链。

第二：序数可以做加法和乘法运算，而且运算规则与我们的常规熟悉很像。但我们要特别关注 $\omega$ 这个序数。 $\omega$ 这个序数是最小的一个无穷序数，它比所有的有穷序数都大，也就是“比所有的自然数都大”，这使它在比大小时，大小关系的判定上非常简便。

那我们看看怎么用序数证明那个拿走麦子的游戏可以在有限步骤内结束。仍以之前 $M_1=100$ 的情况为例。

那么我们考虑对这个数列的每一个数，如果把底数换成序数里的 $\omega$ 会怎样？并且我们比较一下变换前的数字和改成 $\omega$ 为底的数字的大小。

$M_1=100 = 2^{6}+2^{5}+2^2=$

$2^{2^{2} + 2} + 2^{2^{2} + 1} + 2^{2}$

底数换成 $\omega$ 后：

$O_1=\omega^{\omega^{\omega} + \omega} + \omega^{\omega^{\omega} + 1} + \omega^{\omega}$

原先的 $M_2$ :

$M_2=3^{3^{3} + 3} + 3^{3^{3} + 1} + 3^{3}-1$

底数换成 $\omega$ 后：

$O_2=\omega^{\omega^{\omega} + \omega} + \omega^{\omega^{\omega} + 1} + \omega^{\omega}-1$

原先的 $M_3$ :

$M_3=4^{4^{4} + 4} + 4^{4^{4} + 1} + 2\cdot 4^{2} + 2\cdot 4 + 1$

底数换成 $\omega$ 后:

$O_3=\omega^{\omega^{\omega} + \omega} + \omega^{\omega^{\omega} + 1} + 2\cdot \omega^{2} + 2\cdot \omega +1$

原版游戏的每一步的 $M_n$ ，当改成 $\omega$ 为底时，它都会小于对应的 $O_n$ 。

那么再看一下转换过后的 $O_n$ 序列。你会发现，因为每一次的减一操作，它构成了一个递降序列！

前面说了良序集有个特性，不存在无穷的递降序列，那么就说明 $O_n$ 序列只能是有限长度的。

而一个正数构成的数列 $M_n$ 的每一项都小于另一个数列 $O_n$ ，且 $O_n$ 长度是有限的，那只能说明 $M_n$ 也是有限长度的，这样古德斯坦序列的有限性得证！

从以上过程中，我们会发现序数理论是非常有用，它甚至能证明皮亚诺算数中不能证明的命题，比全体自然数更大的数是有用的！这是非常令人吃惊但有意思的事情。

更有意思的是序数理论还能帮我们做定量分析。从之前的分析你可以看出，在古德斯坦序列中，每次底数的增加完全可以不是递增1的模式。实际上，对任何递增的自然数序列 ${a_{1}, a_{2}, a_{3}, \ldots \ldots}$ ，在古德斯坦序列中，底数以 $a_n$ 的方式增加，最终还是会在有限步骤内会到0.

最后解答一个问题，既然皮亚诺算术公理不能证明古德斯坦序列有限，那在以上的证明中一定用到了皮亚诺算术里没有的公理。这个公理是啥呢？

这个公理就是对皮亚诺算术里的“数学归纳法”的扩展。皮亚诺算术公理中，只说数学归纳法对自然数有效，而没有说对序数集有效。而之前的证明用到的一个前提就是，数学归纳法可对包含 $\omega$ ，及直到 $\omega$ 幂次的序数的情况都有效，这是皮亚诺算术公理没有的。

这种数学归纳法数数学里有个名称：叫超限或者超穷归纳法(transfinite induction)，就是超越无穷大之后的归纳法。有兴趣的可以自行研究一下。

总结：

文章中向大家介绍一个拿走麦子的游戏，这个游戏虽然步骤长，但却总是有限的。甚至游戏本身可以像套娃一样嵌套，它仍然是有限步骤内可以结束的游戏。这个游戏等价于古德斯坦序列。

古德斯坦序列的有限性，已经不能用皮亚诺算术公理系统来证明，但却可以用来序数理论非常简单的证明，这是序数理论的一个强大之处。

参考资料:

https://zh.wikipedia.org/zh/%E5%8F%A4%E5%BE%B7%E6%96%AF%E5%9D%A6%E5%AE%9A%E7%90%86

http://blog.kleinproject.org/?p=674

https://googology.wikia.org/wiki/Goodstein_sequence

Share this:

Related