珠子游戏：n 种颜色的珠子最多能排几轮？

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

1、一、规则

• 有 $n$ 种颜色的珠子。
• 第 $i$ 轮，你写一串珠子——下面把这一串叫一个词——长度不超过 $i$ 颗。
• 只有一条规矩：任何更早的词，都不许是更晚的词的子序列。「子序列」的意思是：从后面那个词里按顺序挑几颗珠子（可以跳着挑、可以漏掉中间的），能正好拼出前面那个词。能拼出来就说「含」。下面用 $w\subset w'$ 表示「$w$ 含于 $w'$」。

问：最多能写多少轮？这个数记作 $H(n)$。

为什么要有「长度不超过 $i$」这条限制？因为不加它，游戏可以无限玩下去：$A^{100}$、$A^{99}$、……、$A$（$A^{100}$ 就是 100 颗 A 连着写），想写多长写多长。有了这条限制，「最长多少轮」才有确定答案。

两个约定，后面反复用：

1. $b^3$ 表示连着写 3 颗 b （也就是 bbb）；$b^0$ 就是一颗 b 都没有。
2. 要讲「为什么涨得快」，得看一个更一般的版本：把每轮的上限从 $i$ 放宽成 $i+s$（$s$ 是每轮额外多给的珠子数，下面直接叫它预算）。$k$ 种颜色、预算为 $s$ 时的最长轮数记作 $G(k,s)$。于是

（原版就是 $s=0$ 的情形。下面看到 $G(2,1)$ 这种写法，意思都是： 2 种颜色、每轮多给 1 颗。）

2、二、1 种颜色： 1 轮

第一轮最多写 1 颗珠子（空词不算词），只能写 A。

之后任何非空的词都含 A，也就是都含第一轮那个词，所以第二轮写不出来。

3、三、2 种颜色： 3 轮

一种最长玩法是

• 第一轮写 A，等于把 A 永久封杀：后面的词里只要出现一颗 A，它就含 A。
• 所以第二轮起只能用 B。而两串纯 B 之间，$B^j$ 含于 $B^i$ 当且仅当 $j\le i$（珠子少的那串，总能从多的那串里按顺序挑出来）。也就是说：后面每一轮的长度必须严格递减。
• 第 $i$ 轮的上限是 $i$ 颗，所以最多只能再有 $BB$ 和 $B$ 两轮。

4、四、3 种颜色： 27 轮

一个最长的玩法是（c×14 表示 14 颗连续的 c ，以此类推）：

 1 a              8 cccccb          15 c×13         22 cccccc
 2 bb             9 ccccb           16 c×12         23 ccccc
 3 bcc           10 cccb            17 c×11         24 cccc
 4 ccbc          11 ccb             18 c×10         25 ccc
 5 cbc           12 cb              19 c×9          26 cc
 6 bc            13 b               20 c×8          27 c
 7 ccccccb       14 c×14            21 c×7

读这段序列，骨架很清楚：第 1 步 a 把 a 封杀掉；第 2 到 13 步是「2 种颜色、每轮预算多 1」的同款游戏；第 14 到 27 步是最朴素的尾巴，只用一种珠子、长度从 14 一路递减到 1。

于是 $H(3)=27$：第一步封掉一个字母，剩下的就是 $G(2,1)$（ 2 种颜色、预算 1 的同款游戏），它的答案是 26 ，所以 $1+26=27$。（ 27 可以一小步一小步数清楚；下面会说明为什么再多一种颜色就数不动了。）

5、五、这些数是怎么推出来的：四种机制

小值可以数清楚，但真正要理解这个游戏，靠的是四条能证明的机制。它们解释了这些数为什么按这个速度涨，也解释了为什么 4 种颜色就已经没法写。

5.1、机制 1 ：一种颜色，就是一只只会往小里数的计数器

只有 $A$ 一种珠子时，$A^j$ 含于 $A^i$ 当且仅当 $j\le i$。所以后面每一轮的长度必须严格递减，而第 $j$ 轮的上限是 $j+s$。于是

而且这是刚好达到的：$A^{1+s}\to A^{s}\to A^{s-1}\to\cdots\to A$，一轮不浪费。这一条后面反复要用，一句话记住：一条递减链能走多少轮，等于它起步那一轮的预算。

5.2、机制 2 ：让一段游戏带一个「只属于它自己的字母」

这是拼接的工具（ TREE 那边的下界正是这么用的），但它本身不给大数，先把这一点看清楚。

假如前面一段里，每个词都带一个后面永远不再出现的字母 $x$。那么前面任何词都不可能含于后面的词——因为「含」必须一个字母一个字母对上，而后面的词里根本没有 $x$。于是后面那一段可以当成全新的一局来玩；而且它的预算已经被前面那一段抬高了（前面走了 $L$ 轮，后面就从第 $L+1$ 轮起步）。

写成式子（颜色数从 $k$ 加到 $k+1$）：

• 前一段：拿 $k$ 种颜色玩一局，每个词末尾都补一颗 $x$。补同一个字母不改变「谁含谁」，但每个词都长了 1 颗，所以相当于预算少 1 ，能走 $L=G(k,s-1)$ 轮。
• 后一段：用原来那 $k$ 种颜色重开一局，起点预算 $L+s$。

泼一盆冷水：这条式子看着像「自己放大自己」，其实不给大数。把 $G(1,s)=s+1$ 代进去，得 $G(2,s)\ge 3s+1$；再套一层大约 $12s$——每套一层只是把系数乘个常数，所以光靠拼接，永远只得到「和预算成正比」。它讲的只是「几段可以拼起来、后面的起点预算被前面抬高」这个形式。数值变大得靠下面两条。

5.3、机制 3 ：收尾链——把预算一比一换成回合

一段游戏里还能塞进「递减链」。比如 $b^{i}a$ 含于 $b^{i'}a$ 当且仅当 $i\le i'$，所以

可以连着走 7 轮，一轮不浪费。纯 $b$ 的链也一样，能从 $b^{14}$ 一路走到 $b$， 14 轮。链能走多长，取决于链起步那一轮的预算。

要把它写成递推，得再加一个符号：记 $P(k,s)$ 为「每个词都必须含指定的那个字母 $a$」的同款游戏的最长轮数（$P$ 表示每个词都带这个"枢轴字母"）。那么

为什么：先用 $P(2,s)$ 步走完「都含 $a$」的前缀（它本身就是合法的一局）；再接一条纯 $b$ 的递减链。纯 $b$ 的词不可能含 $a$，所以绝不会踩到前缀；而这条链能走 $P(2,s)+1+s$ 轮，因为链起步那一轮的预算正是「前面的步数 $+\,1+s$」。

在预算 1 （也就是 $s=1$）的真实最优解上，这条式子两头一夹还能给出一个干净的数：

• 把 $G(2,1)=26$ 代进去，得 $P(2,1)\le 12$；
• 而最优解的前 12 个词（aa、abb、bbab、bab、ab、b⁶a、……、ba、a）恰好每个都含 $a$，所以 $P(2,1)\ge 12$。

于是 $P(2,1)=12$，并且 $26=2\times 12+1+1$——取等：预算换成回合是一比一、不浪费的。

不过机制 3 只做了一半的事：把预算换成回合。要真正放大，还差另一半——换来的那些回合，得能被当成新的预算再用一次。这一半靠维数。

5.4、机制 4 ：维数——真正的「放大」

维数藏在哪？就藏在机制 3 那个「都含 $a$」的前缀里。

恰好含一颗 $a$ 的词，都能写成 $b^{i}a\,b^{j}$ 的样子（$a$ 前面有 $i$ 颗 $b$，后面有 $j$ 颗 $b$）。两个这样的词，一个含于另一个当且仅当 $i\le i'$ 并且 $j\le j'$——也就是两个数分别比大小，很像平面上一个点的坐标 $(i,j)$，谁也不许在两个方向上都更大。

如果一颗词里有 $m$ 颗 $a$，它就分成 $m+1$ 段 $b$：

对应一串 $m+1$ 个数 $(i_0,\ldots,i_m)$，也就是 $m+1$ 维空间里的一个点。同样地：两个词里 $a$ 的颗数一样时，一个含于另一个，当且仅当每一段 $b$ 的颗数都不大于对方。

现在定一个新符号：玩这些「坐标点」，最长能走多少轮，记作 $g_d(s)$。其中 $d$ 是坐标的个数（维数），$s$ 还是每轮多给的预算。（例如 $d=2$ 就是「恰好一颗 $a$」的情形：每个词对应两个数 $(i,j)$。）

有了维数，一段游戏就能切成两半：

• 最后一个数 $\ge 1$ 的那些点：把最后一个数各自减 1 ，就变成同一个游戏（维数不变），只是每个词都短了 1 颗，相当于预算少 1。所以这一半能走 $g_d(s-1)$ 步。
• 最后一个数 $=0$ 的那些点：这少了一个坐标，退化成 $d-1$ 维的游戏。妙处有两点：这些点绝不会压住前一阶段的点（前面那些的最后一个数 $\ge 1$，比 0 大），所以自动合法；而它们起步那一轮的预算，已经被前面走掉的那些步数抬到了 $g_d(s-1)$ 这个量级。

于是

盯住这里下标的 $d-1$：不是「同一个游戏再套一次」，而是把低一维的那个游戏，喂给它自己产出的那个大数。这才是「越套越高」的标准形状。

而且这个坐标游戏不在别处，它就在 2 种颜色的游戏里面：「恰好含一颗 $a$」的词就是 $d=2$ 的那些点。所以

（左边是那个子游戏，中间是「都含 $a$」的版本，右边是完整的 2 色游戏；限制越多、能玩的越少，所以是 $\le$。）机制 3 递推里那个前缀装的，就是它。

5.5、五个档位：越往上越大

只有 2 种颜色就够造任意多维——有预算，就有地方放那些 $a$。所以 2 色的版本本身就能往上爬（$G(2,2)$ 数不完，正是这个原因）；多一种颜色，等于多一套「大块套小块」的搭法可以同时用，档位再往上抬。

在真实的最优解上能直接看到这些机制：$G(2,1)=26$ 拆成 $1+11+14$——1 是开场的 aa（把 $a$ 的颗数压到不超过 1 ）， 11 是「一颗 $a$」的坐标段， 14 是纯 b 的收尾链；而 14 恰好等于它起步那一轮的预算（第 13 轮，$13+1=14$）；内层的 11 再拆一次， 7 也恰好等于内层链起步的预算。

5.6、4 种颜色为什么大到写不出来

4 种颜色的同款游戏， Deedlit 把它记作 $F(4)$（规则是： 4 种颜色、第 $i$ 个词长 $i+1$ 颗）。要说它有多大，得先认识两样东西：

• $f_\alpha$：快增长层级里的函数。下标 $\alpha$ 越大，它长得越快；其中 $\alpha=\omega$ 这一档就是大家熟悉的 Ackermann 函数。而 $\omega$ 是数学里「最小的无穷」的记号。
• $\mathrm{tree}(\cdot)$：只有一种颜色的弱版游戏（见另一篇）。

Deedlit 构造出了它的一个下界（是证出来的，不是估算）：

也就是说，$F(4)$ 已经落在 $\omega^2+\omega+1$ 这一档——比 Ackermann 所在的 $\omega$ 档高出一大截。而

这个珠子游戏，正是给 TREE(3) 做下界用的零件。

所以： 4 种颜色的珠子游戏大到写不出来，不是「涨得慢」，而是它落在的档位本身就比 Ackermann 高出一大截。

上界一侧说的是同一件事：这类游戏在文献里叫「受控坏序列」（ controlled bad sequences ），长度上界随颜色数按 $\omega^{\omega^{k-1}}$ 这样的档位上升——颜色数每加 1 ，档位往上跳一层（ Cichoń 与 Tahhan Bittar 1998 ； Schmitz 与 Schnoebelen 2011 ）。

6、六、为什么一定有尽头

Higman 引理（ 1952 ）：颜色数有限时，不存在无限长的「坏序列」——坏序列就是每个新词都不含前面所有词的那种写法。

证明骨架：假设真有一条无限长的坏序列。在所有坏序列里，挑一条最省力的（数学上叫极小坏序列）。再看每个词的首字母：首字母只有有限多种，所以无限多个词里必有某一种首字母出现无限多次，把它们抽出来。然后看它们的尾巴：

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

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

再加一步（ König 引理）：「不存在无限长的玩法」和「存在一个最长的玩法」，中间差一步。把所有可能的开局拼成一棵游戏树：每个节点是一种合法开局，它的孩子是下一步能选的所有词。每一轮的候选只有有限多个（颜色有限、长度有限），所以这棵树每个分岔都只有有限多个分支。要是长度没有上限，这棵树就无限高；有限分岔加无限高，必定存在一条无限长的路（ König 引理），那就是一局无限长的玩法，与 Higman 引理矛盾。于是最长轮数是一个确定的有限数。

7、七、有限，却算不到头

有限性是 Higman 引理那种「对所有坏序列整体挑最小」的手法证明的，而这种手法给不出能计算的上界——它只能告诉你「存在一个最长的局」，说不出它有多长。上面四条机制则说明：这个「最长的局」落在很高的档位上，档位本身就决定了它不可能被一项一项数出来。

两件事其实是同一件事的两面：证明有限性的手段越强，它给出的界就越远。 这正是 TREE(3) 的处境，珠子游戏不过是它的小号版本。

8、附一、符号表

9、附二、小值怎么核

$H(1)$、$H(2)$、$H(3)$ 三个小值可以用程序逐项核（scripts/word_game_exact.py 穷举，scripts/word_game_verify.py 独立校验给出的序列）。再往大不用试：那里不是「算得慢」，而是档位问题——真要往大走，只能像 Deedlit 那样去构造，而不是去数。

Q. E. D.