TREE(3)：一个能玩的游戏，为什么一定有尽头，又为什么大到写不出来

作者: , 共 7749 字

葛立恒数是用箭头一层层堆出来的。还有一个数，定义简单到可以用纸笔画出来，却比葛立恒数大得多 —— 它叫 TREE(3)。

它回答的是这样一个问题：一个画树的小游戏，最多能玩几个回合？

答案有两半，都很反常识：

  1. 回合数一定是有限的（游戏一定会结束）；
  2. 这个回合数大到没有人写得出来。

这篇文章分三步走。第一步先玩最简单的版本（字母躲猫猫），亲手验证几个小数字；第二步玩正片（树躲猫猫），亲手验证 $\mathrm{TREE}(1)=1$、$\mathrm{TREE}(2)=3$；第三步讲两件事：为什么一定有尽头，以及为什么尽头那么远。

1、一、热身：字母躲猫猫

规则只有三条：

  1. 你有一张字母表，上面有 $k$ 个字母。
  2. 第 $i$ 回合，你写一个词，长度不超过 $i$ 个字母。
  3. 新词里不能藏着前面写过的任何一个词。

「藏着」的意思是：从新词里按顺序挑出一些字母（可以跳过中间的字母），正好拼出那个旧词。比如旧词是 AB，新词是 AABB，那新词的第 1 个和第 4 个字母正好是 AB，新词就犯规了。

玩到写不出新词为止，最长的回合数记作 $T(k)$。

1.1、1 个字母：$T(1)=1$

  • 第 1 回合：只能写 A。
  • 第 2 回合：长度不超过 2 ，但里面不能藏着 A，也就是不能出现 A。可是字母表里只有 A，什么也写不出来。

游戏结束，$T(1)=1$。

1.2、2 个字母：$T(2)=3$

字母表是 A、B。

  • 第 1 回合：只能写 A（写 B 完全对称，我们固定成 A）。
  • 第 2 回合：不能出现 A（否则藏着 A），所以只能用 B。长度上限是 2 ，写 BB 比只写 B 更划算。
  • 第 3 回合：不能出现 A，也不能藏着 BB。要藏着 BB，需要有两个按顺序出现的 B，所以这一回合最多只能写一个 B：写 B。
  • 第 4 回合：不能出现 A，不能有两个 B（否则藏着 BB），也不能有一个 B（否则藏着上一回合的 B）—— 什么都不能写。

所以 $T(2)=3$，一种最长的玩法是：

$$\texttt{A}\ \longrightarrow\ \texttt{BB}\ \longrightarrow\ \texttt{B}$$

剧透一句：把字母数加到 3 ，这个热身游戏的答案会跃升到 27 轮（可以用程序穷举出来）；到 4 个字母就冲出可算范围了。细节和计算脚本见另一篇 「珠子游戏」。

这里已经出现了全篇文章的钥匙：第一回合被迫写下的那个「单字母」，把它永久禁用了。 因为一个字母的词，能藏进任何含这个字母的词里。到了树的游戏里，一模一样的诅咒会落在颜色上。

2、二、正片：树躲猫猫

2.1、规则

  1. 有 $k$ 种颜色（先玩 1 色、2 色，最后玩 3 色）。
  2. 第 $i$ 回合画一棵树：点最多 $i$ 个（第 1 回合最多 1 个点，第 2 回合最多 2 个点，第 3 回合最多 3 个点……），每个点涂一种颜色。树至少要有 1 个点，空树不算。
  3. 规矩还是只有一条：新树里不能「塞」着前面画过的任何一棵树。

最长能玩多少回合，就记作 $\mathrm{TREE}(k)$。这就是 TREE(3) 里的那个 TREE。

2.2、「塞进去」是什么意思

把一棵树想成一张家谱：点是家里人，颜色是姓氏，连线是父子关系。要把旧树 X 塞进新树 Y ，就是给 X 的每个点，在 Y 里找一个「替身」，要求：

  1. 一对一： X 里不同的点，替身也必须是 Y 里不同的点；
  2. 姓氏一样： X 里是红点，替身也得是红点；
  3. 辈分不能反： X 里爸爸在儿子上方，到了 Y 里，替身也得在儿子替身的上方。中间隔几代没关系（可以把爷爷和孙子直接接起来，这叫「压扁」），但不许把父子关系倒过来；
  4. 分叉不能粘： X 里两个不同的分支，到了 Y 里也必须落在两个不同的分支上，不许把两根树枝粘成一根。

从这几条规矩，马上能得到三个每次都能用的判断法：

  • 单点法则：一个只有 1 个点、颜色 $c$ 的树，能塞进任何一棵含 $c$ 色点的树。
  • 两点法则：一棵「爸爸颜色 $c_1$、儿子颜色 $c_2$」的两点树，能塞进新树，当且仅当新树里能找到一对祖先—后代，祖先是 $c_1$ 色、后代是 $c_2$ 色。
  • 带儿子的法则：一棵「颜色 $c$ 的爸爸带三个颜色 $d$ 的儿子」，能塞进新树，当且仅当新树里有一个 $c$ 色点，它下面有三个互不同分支的 $d$ 色点。

2.3、1 种颜色： 1 回合，$\mathrm{TREE}(1)=1$

  • 第 1 回合被迫画 1 个点，颜色 A。
  • 第 2 回合：任何一棵非空的树都有一个点，而且只有 A 色，所以都能塞进第 1 回合那个点里。什么也画不了。

所以 $\mathrm{TREE}(1)=1$。

2.4、2 种颜色： 3 回合，$\mathrm{TREE}(2)=3$

  • 第 1 回合： 1 个点，红色。红色被永久封杀。
  • 第 2 回合：最多 2 个点，不能用红，所以只能用蓝。可以选择「单独一个蓝点」，也可以选择「蓝爸爸 + 蓝儿子」。
  • 画「单独一个蓝点」→ 蓝色也被封杀 → 第 3 回合没法画，总共只有 2 回合。
  • 所以画「蓝爸爸 + 蓝儿子」，记作 B(B)。
  • 第 3 回合：最多 3 个点，只能用蓝，而且不能出现「祖先—后代都是蓝」的一对（否则塞进 B(B)）。只画 1 个蓝点：合法。
  • 第 4 回合：最多 4 个点，只能用蓝，不能出现「祖先—后代都是蓝」的一对，也不能含单独一个蓝点（否则塞进第 3 回合）—— 可是任何非空的蓝树都含蓝点。画不出来。

于是 $\mathrm{TREE}(2)=3$，一种最长玩法是：

$$\texttt{A}\ \longrightarrow\ \texttt{B(B)}\ \longrightarrow\ \texttt{B}$$

对照一下：字母版是 $T(1)=1$、$T(2)=3$，树版本是 $\mathrm{TREE}(1)=1$、$\mathrm{TREE}(2)=3$，一模一样。可是到了 3 种颜色，情况就完全变了。

3、三、3 种颜色：天翻地覆

3.1、开场五步，你可以自己检查

3 种颜色里，规则唯一「放宽」的地方是：第 $i$ 回合可以画 $i$ 个点，点数一直在长。多出来的那一种颜色，让下面这种玩法成为合法：

  1. 第 1 回合：一个红点 A。（红色封杀）
  2. 第 2 回合：B(B)，蓝爸爸 + 蓝儿子。
  3. 第 3 回合：C(B,B)，绿爸爸 + 两个蓝儿子。
  4. 检查：没有红点，所以塞不下第 1 回合；两个蓝点是兄弟，不是祖先—后代关系，所以塞不下第 2 回合的 B(B)。
  5. 第 4 回合：B(C,C,C)，蓝爸爸 + 三个绿儿子。
  6. 检查：没有红点；整棵树里只有一个蓝点，所以塞不下 B(B)；三个绿点都是叶子，所以塞不下 C(B,B)（那需要一个绿点下面挂着两个不同分支的蓝点）。
  7. 第 5 回合：C(B,C,C)，绿爸爸 + 一个蓝儿子 + 两个绿儿子。
  8. 检查：没有红点；蓝点只有一个，塞不下 B(B)；绿点要么是根、要么是叶子，都不满足 C(B,B) 的要求；唯一那个蓝点是叶子，也塞不下 B(C,C,C)。合法。

每走一步，后来者的「形状自由」就被砍掉一块：第 2 步砍掉「祖先—后代是同色的蓝蓝」，第 3 步砍掉「绿点下面两个不同分支的蓝点」，第 4 步砍掉「蓝点下面三个不同分支的绿点」……

可是同时，点数上限一直在涨。 第 10 回合，光是「点数不超过 10 的树」的形状就有 1205 种（树的形状数是 1、1、2、4、9、20、48、115、286、719 累加起来），配上有 3 种颜色可选的点，这一回合的候选已经有 4896 万种。到第 20 回合，候选大约是 $5.1\times 10^{16}$ 种，也就是五亿亿种。

砍掉一小块，长出极多块。 这个拉锯，就是游戏能撑很久的秘诀。

3.2、到底能撑多久

没有人知道确切值。已经证明的是：

$$\mathrm{TREE}(3) > n(4) > G$$

其中 $G$ 就是葛立恒数，$n(4)$ 是 Friedman「方块游戏」给出的数（那是一个同样能上手玩的游戏，它的 $n(4)$ 已经大过葛立恒数）。所以 TREE(3) 不只是比葛立恒数大，而是大得多。

还有一条更让人吃惊的结论：把游戏放宽成「只有 1 种颜色，但每回合的点数上限从 $i$ 改成 $i+4$」（也就是每次多给 4 个点的预算），这个弱版本的 $\mathrm{tree}(4)$ 就已经超过葛立恒数了，甚至满足

$$\mathrm{tree}(4) > f_{\varepsilon_0}(G)$$

（ Kihara ， 2020 年。$f_{\varepsilon_0}$ 是「快增长层级」里的第 $\varepsilon_0$ 级函数。）

只多给 4 个点的预算，就换来这么大的数 —— 那么 3 种颜色的版本有多远，可以想象。

4、四、为什么一定有尽头：两件武器

4.1、武器一： Kruskal 定理（ 1960 ）

Kruskal 定理：不存在一局能永远玩下去的树躲猫猫。

换个说法：不管你多会躲，迟早会撞墙。它的证明思路很漂亮，骨架是这样。

先看更简单的字母版（ Higman 引理， 1952 ）：字母表有限，就不可能写出无限长的「坏序列」（坏序列就是每一步都成功躲开前面所有词的写法）。

证明的办法是反证 + 挑一个「最省力的坏蛋」：假设真的存在一条无限长的坏序列。在所有坏序列里，挑一条「最省力」的（数学上叫极小坏序列）。然后看每个词的首字母 —— 字母表只有有限个字母，所以无限多个词里，一定有某一种首字母出现无限多次，把它们抽出来排成一列（这一步叫「抽牌」）。再看它们的尾巴：

  • 如果这些尾巴自己还能组成坏序列，那就说明我们挑的这条不是最省力的，矛盾；
  • 如果这些尾巴之间已经出现了「藏着」的关系，那把它们拼回整词，原来那串词也就不是坏序列了，矛盾。

两边都是矛盾，所以坏序列只能有限长。

树版只多两步：一棵树 = 根的颜色 + 一串子树。先把「一串子树」这个更小的游戏证明是好的，再对它套用上面的字母版结论，就得到 Kruskal 定理。

请记住这一步：证明里用到的「在所有坏序列里挑一条最省力的」，是对一个无限多的对象整体下判断。这种手法在数学里叫非直谓。它是 Kruskal 定理这么强的原因 —— 强到有一类数学系统（比如 $\mathrm{ATR}_0$）根本证不出它。第五节的最后，我们还要回到这里。

4.2、武器二：康尼引理 —— 从「没有无限局」到「有一个最大回合数」

「不存在无限长的一局」和「存在一个最大的回合数」，听起来像同一句话，其实中间差一步。补上这一步用的是康尼引理。

先把所有可能的开局整理成一棵游戏树：每个节点表示一种合法的开局，节点的孩子表示下一步可以选的所有树。第 $i$ 回合可以选的树只有有限多个（点数不超过 $i$，颜色只有 $k$ 种），所以游戏树的每个分岔都只有有限多个分支。

现在假设「没有最大回合数」：随便给你一个 $n$，都有一局能玩 $n$ 回合。也就是说游戏树有任意长的路，即无限高。

康尼引理：一棵树如果每个分岔都只有有限多个分支，而且无限高，那么它一定有一条无限长的路。

道理很直白：如果每条路都只走有限步就到了头，那么在所有路的长度里一定有个最大值（有限多个有限数里总有最大的），树就不可能是无限高的。

这条无限长的路，就是一局能永远玩下去的躲猫猫 —— 撞上武器一。所以：

$$\mathrm{TREE}(k)\ \text{是有限的}$$

顺便说一句：如果每回合可选的分支是无限多，康尼引理就不成立了。 比如让根有无限多个孩子，第 $n$ 个孩子往下接一条长度为 $n$ 的路：这棵树无限高，但每一条路都是有限的。所以「每个分岔只有有限多个分支」这个条件，一个字都不能省。

5、五、为什么有限，却又那么大

5.1、它有限，是被「证明」出来的，不是被「算」出来的

$\mathrm{TREE}(3)$ 是有限的，这一点铁板钉钉： Kruskal 定理加康尼引理，两步就把它钉住了。但这两件武器都不给你具体的数，它们只说「有一个最大的回合数」，不说它是多少。这种证明叫非构造性证明。

5.2、数值为什么必然巨大：源头就是那个「非直谓」

回到第四节里那个动作：为了证明有限，我们不得不在所有坏序列里整体地挑一条「最省力」的。这种手段的强度超过了某些数学系统能处理的范围。后果是：

  • 它给出的界，不可能由任何「人类还能写出公式」的增长函数给出；
  • Friedman 证明了 TREE 这个函数最终大过所有能被数学系统 $\mathrm{ACA}_0+\Pi^1_2\text{-BI}$ 证明一定会停机的程序。换句话说：你随便写一个能被这个系统证明「一定会停」的程序，让它跑，它跑出来的数最终都追不上 TREE。

所以：「有限」和「大得离谱」其实是同一件事的两面。 正因为证明有限的办法这么高级，它给出的界才必然远到看不见。这也是为什么 TREE(3) 只能被「比较」，不能被「计算」。

5.3、一条数字阶梯

数 大小关系 说明
$T(1)=1$，$\mathrm{TREE}(1)=1$ 1 回合 只有 1 种字母（颜色）时立刻死
$T(2)=3$，$\mathrm{TREE}(2)=3$ 3 回合 手就能算完，见第二节
$\mathrm{tree}(4)$ $> G$ 只有 1 色，但每回合多给 4 个点的预算
$n(4)$ $> G$ Friedman 的方块游戏
$\mathrm{TREE}(3)$ $> n(4) > G$ 本文的主角， 3 种颜色

（$G$ 是葛立恒数。）

6、六、几个常问的问题

问： TREE(3) 到底等于几？

答：没有人知道。它是一个有限的正整数，但确切的值、位数、末位数字，全都不知道。已知的只是它比上面那些巨大的数更大。

问：能不能像 TREE(2) 那样用电脑算出来？

答：不能。TREE(2) 能算，是因为候选实在太少（第 4 回合就能全部试完）。TREE(3) 的候选数每一步都在爆炸，第 20 回合单回合候选就超过 $5\times 10^{16}$ 种，穷举到天荒地老也走不了几步。

问：那它是最大的数吗？

答：不是。$\mathrm{TREE}(3)+1$ 就比它大。数学里还有更大的「游戏数」，比如 $\mathrm{SCG}(13)$（子立方图游戏的数）。

问：为什么第 1 回合一定要画 1 个点？

答：因为第 1 回合最多只允许 1 个点，而空树不算树。这个「被迫」，就是整篇文章里那把钥匙：第一回合的单点，会把一种颜色永久封杀。

7、七、留一道题给你

3 种颜色的开场五步是：

$$\texttt{A}\ \to\ \texttt{B(B)}\ \to\ \texttt{C(B,B)}\ \to\ \texttt{B(C,C,C)}\ \to\ \texttt{C(B,C,C)}$$

你能不能在第 6 回合画出一棵 6 个点以内的树，让它躲开前面所有五棵树？（用第二节那三条判断法，一棵一棵地检查。）

提示：往后走，限制会越来越多，可点数上限也一直在涨。这个「限制涨得慢、自由涨得快」的拉锯，就是 TREE(3) 那么大、却仍然有限的原因。

8、附：名词对照

名词 一句话
子序列 从词里按顺序挑字母，可以跳过中间的字母
Kruskal 定理 树的躲猫猫不能无限玩下去
Higman 引理 字母版的同一件事
康尼引理 有限分岔 + 无限高 ⟹ 存在一条无限长的路
非直谓 对一个无限多的对象整体下判断，这种手法很强
$\mathrm{TREE}(k)$ 树躲猫猫的最长回合数（$k$ 种颜色）
$\mathrm{tree}(n)$ 弱版：只有 1 种颜色，但每回合的点数上限放宽到 $i+n$

资料出处： Kruskal （ 1960 ）； Friedman （ TREE 序列、方块游戏 $n(k)$）； Kihara （ 2020 ，弱版 tree 函数的下界）； Googology Wiki 与维基百科 「Kruskal's tree theorem」条目。文中那些小数字（$T(1)=1$、$T(2)=3$、$\mathrm{TREE}(1)=1$、$\mathrm{TREE}(2)=3$）都可以按文章里的推理亲手复核。

Q. E. D.

前一篇：
数学 » 组合数学, 大数, 良拟序
写 TREE(3) 那篇的时候，开头有个热身小游戏（把树换成珠子串）。当时只手算了 1 种和 2 种颜色，这回把它算到底，并且把「为什么涨得这么快」讲清楚。文中的符号都是随用随定义的，末尾还附了一张符号表，忘了可以回头查。