多色 Ramsey 数——六个人的聚会，和无穷多种颜色

这是「AI 正在攻克的数学问题」系列的第 5 篇。上一篇《单位距离问题》里的老朋友埃德奥斯（Paul Erdős）又出现了，这一次，他悬赏多年的第 183 号问题，被 AI 画上了句号。

一、问题是什么

先说一个大多数人都能上手的结论。六个人参加聚会，必然有三个人两两相识，或者三个人两两不相识。 这听起来像句废话，但它不是巧合，它是组合数学里最著名的"躲不掉"定理的一个特例，记作 $R(3,3)=6$。

把它翻译成图论的语言。六个人看成六个点，任意两人之间连一条线。相识染成红色，不相识染成蓝色。六个点两两之间都要连线，一共是 $\binom{6}{2}=15$ 条。结论就变成一句很干净的话。无论这 15 条线怎么染成红蓝两色，必然会出现一个三条边同色的三角形。

为什么躲不掉？任取一个人甲。其余五个人和甲要么相识、要么不相识，抽屉原理保证。五个人里至少有三人跟甲是同一种关系。假设这三人恰好都跟甲相识。再看这三个人彼此之间。只要其中有两人相识，加上甲，就是"三人两两相识"；如果这三个人彼此全不相识，那他们自己就是"三人两两不相识"。两种情况，必中其一。这就是 $R(3,3)=6$ 的完整证明。

顺带说明 6 这个数为什么"恰恰好"。5 个点是可以躲开的。把五点排成正五边形，五条边染红、五条对角线染蓝，图里既没有纯红三角形，也没有纯蓝三角形。所以 $R(3,3)$ 至少是 6，又证出至多是 6，正好等于 6。

现在做一个小小的推广，问题就一下子"爆炸"了。把"相识 / 不相识"这两种关系换成 $k$ 种关系，想象用 $k$ 种颜色给两两之间的线染色。$R_k(3)$ 记的是这样一个数。至少要多少个点，才能保证无论用 $k$ 种颜色怎么染，都必然出现一个三边同色的三角形。 这就是"多色 Ramsey 数"。

它的数值涨得极快。

• $R_2(3)=6$，就是开头的聚会；
• $R_3(3)=17$，三色版本的精确值，也是至今算出的唯一一个多色精确值；
• $R_4(3)$，只知道在 51 和 62 之间，没人知道它到底等于几。

颜色每多一种，这个数就换一个量级。它问的是"点数要涨到多大，躲都躲不掉"，而不是"最多能有多少种染法"。

二、它从哪来

问题先挂在一个英国人名下。弗兰克·拉姆齐（Frank Ramsey），英国数学家兼哲学家，1930 年在一篇论文里证明了一个非常一般的定理，无论给足够多点的两两连线怎么染色，总有一片"单色结构"出现。这就是 Ramsey 定理。他当年 26 岁，同年因病去世。他自己大概没想过，这个定理会变成一个具体到"6 个人聚会"的话题。

把它变成"估值游戏"的是埃德奥斯（Paul Erdős，也译作厄尔多斯）。这位匈牙利数学家是组合数学的灵魂人物，一生发表一千五百多篇论文、合作者超过五百人，酷爱给难题设悬赏。他把 Ramsey 数从"存在性定理"变成了一连串"这个数到底多大"的谜题。

埃德奥斯给多色版本设了赏格。他悬赏 250 美元，问 $\lim_{k\to\infty}R_k(3)^{1/k}$ 等于多少；又悬赏 100 美元，问一个更基础的问题。这个极限到底是不是有限的？ 换句话说，$R_k(3)$ 的增长是指数级，还是比任何指数都快的"超指数级"。这个悬赏问题在埃德奥斯问题目录里编号 183，即"多色三角形 Ramsey 数"。

为什么"越大越难猜"？因为数值膨胀得太快，连最小的几档都算不动。两色版本里 $R(4,5)=25$ 是 1995 年靠大规模计算才敲定的，而 $R(5,5)$ 至今只知道在 43 和 46 之间，上下界只差 3，却没人能补上。埃德奥斯有句广为流传的话，大意是这样。假如外星人要求人类一年内算出 $R(5,5)$，集结全世界最聪明的头脑和最快的电脑，或许能做到；可要是他们要求 $R(6,6)$，那还不如直接准备迎接末日。连小数字都这么难，所以"增长到底有多快"本身就成了一个值 100 美元的数学问题。

三、卡在哪

先分清两个方向，这是读懂这类问题的关键。

下界，是"造得出来多少"。 思路是亲手构造一个"用 $k$ 种颜色染色、却没有任何纯色三角形"的点配置。这个配置有多少个点，$R_k(3)$ 就至少比它大一点。构造得越大，下界越高。

上界，是"躲不掉的最少点数"。 思路是证明这样一件事。点数一旦达到某个值，无论怎么染色都必然出现纯色三角形。证明越强，上界越低。

精确值 = 下界和上界碰头。 $R(3,3)=6$ 之所以能算出来，是因为"5 个点躲得开"（下界 6）和"6 个点躲不开"（上界 6）正好对接。但绝大多数 Ramsey 数，两头隔着一个巨大的缝。

• $R(5,5)$。下界 43，上界 46，缝只剩 3，卡了几十年没合上；
• $R_4(3)$。只知道在 51 和 62 之间；
• 多色版本越往后，缝越夸张。上界那边是阶乘量级，经典估计给 $R_k(3)\le (e-\frac16)k!+1$；下界那边，几十年的最好构造来自一种叫"无和集"（Schur 数）的技巧，只做到 $380^{k/5}$ 这种指数量级。指数和阶乘之间隔的是天堑，而且这个缝还在越拉越大。

为什么下界这么难？因为要证明"能躲开"，就得真的造出一个没有纯色三角形的染色方案，而这个方案本身就要有指数多个顶点，还要逐一确认没有三角形。过去最常用的构造叫"积构造"。把两个小的无三角形染色拼成大的，它本质上是指数级的，天花板就卡在"指数"上。想突破，必须换一套全新的构造思路。

用一句话钉住。下界是"造出来的最低保证"，上界是"躲不掉的最强承诺"。这道题卡在两头，构造不出更大的，也证明不了更小的。

四、现在到哪了

2026 年 8 月，OpenAI 发布《数学与理论计算机科学的十项进展》报告，第 9 项就是多色 Ramsey 数。AI 给出的结果是一个超指数下界。存在常数 $c>0$，使得

$R_k(3)\ge \left(\frac{c\,k^{1/3}}{\log k}\right)^k,$

也就是 $R_k(3)\ge k^{k/3-o(k)}$。这里要注意区分。指数级就是底数固定的幂，比如 $2^k$、$380^{k/5}$。底数不变；而这里的 $k^{1/3}$ 会随 $k$ 一起涨，所以整个式子涨得比任何指数都快。这种增长速度叫超指数。

配上经典的阶乘上界，这个下界把增长量级钉死为 $R_k(3)=k^{\Theta(k)}$。量级确定了，只剩指数里的常数还没定。 埃德奥斯那个 100 美元的问题。"增长到底是不是指数级"。答案揭晓了，不是，它比任何指数都快。这就是"解决 Erdős 第 183 号问题"的含义。

必须把话说清楚。这是下界，不是精确值。 这个结果没有告诉我们 $R_k(3)$ 具体等于几，哪怕 $k=4$ 的精确值至今无人知晓。它证明的是这个数至少按 $k^{k/3}$ 的量级暴涨。下界和精确值之间，还隔着指数里那个未知的常数。把"下界"误读成"精确值"，是读这类新闻最容易犯的错。

这个结果的意义，是把埃德奥斯那类"增长是快还是爆炸"的猜想，天花板又往上推了一截。过去几十年最好的下界是指数级，现在被证明是超指数级，方向定了，剩下的只是"到底有多超"。更值得注意的是，这个构造很快被其他数学家接住。Steiner 等人在 arXiv 上把它推广到所有奇数圈（三角形、五边形、七边形……）的多色 Ramsey 数，同样得到超指数下界。AI 挖出的这个结果带出了一条新构造思路的入口，不是孤例。

验证与成本也很清楚。OpenAI 把论证在 Lean 证明助手里形式化，仓库在 github.com/openai/ten-proofs，机器可逐行核验。报告说明这些结果出自 Astra 的内部版本，解决全部十个问题所消耗的 token，按 Sol API 费率折算大约 2000 美元。

回头看第一篇《单位距离问题》，这十项进展里两件大事都挂着埃德奥斯的名字。那篇是 AI 直接证伪了一个猜想（方向错了）；这篇是把一个"量级问题"从"不知道"推进到"知道了，是超指数"（量级定了）。两篇都在"界"的博弈里做文章，而这，恰恰是最适合组合数学新手的战场。

这个专题怎么走

本讲是「AI 正在攻克的数学问题」系列的第 5 篇，也是其中最好上手的一篇，六人聚会的例子不超纲，高中生就能完整读懂证明。后续几讲会继续沿报告走。高维球堆积、算术电路下界、群论里的非 sofic 群（那里连"是否存在"都是 2026 年才被 AI 凿开的新大陆）。

给你的入口建议。如果读到"超指数""阶乘上界"这些词还觉得陌生，不用慌，你只需要抓住第一节那个六人聚会的抽屉论证，以及最后一节那句"下界不是精确值"。中间的估值细节，等你学完计数原理和抽屉原理再回来看，会豁然开朗。

思考与拓展

1. （热身） 把六人聚会的证明完整写一遍。任取一人，说明其余五人里必有三人与他有同一种关系，再分两种情况推出"三人两两相识"或"三人两两不相识"。你用到的最关键的一步是什么？

2. （动手） 画五个点成正五边形。五条边染红、五条对角线染蓝。数一数图里有没有纯红或纯蓝的三角形？由此说明为什么 $R(3,3)$ 不能小于 6。五个点是怎么"躲开"的？

3. （进阶） $R_3(3)=17$ 是至今唯一算出的多色精确值。试着体会一下，为什么两色版本三言两语就能证明，三色版本却要算到 17 才确定？把抽屉原理往上推一层，想想"16 个人可能躲开、17 个人躲不开"这个分界难在哪里。

4. （回扣教材） 打开人教A版选择性必修第三册第六章「计数原理」（或竞赛讲义里的抽屉原理、鸽巢原理）。把第 1 问的证明抽象成一句话。"把 $N$ 件东西放进 $k$ 个抽屉，必有一个抽屉里至少有 $\lceil N/k\rceil$ 件。" 现在把"朋友/陌生人"两种关系扩成 $k$ 种，用抽屉原理推一推 $R_k(3)$ 的一个上界。你会发现它走到了阶乘量级。写完想一想。为什么抽屉原理只能给上界，永远给不出精确值？

一句话总结

多色三角形 Ramsey 数 $R_k(3)$ 的精确值仍然无人知晓，但 AI 在 2026 年证明了它至少按 $k^{k/3}$ 的量级增长，超指数，比任何指数都快，解决了埃德奥斯第 183 号问题中"是否指数级"之问；请记住，这是下界，不是精确值。

---

原始报道 OpenAI《Ten advances in mathematics and theoretical computer science》，2026 年 8 月。

延伸阅读

• 埃德奥斯问题目录第 183 号（UCSD）。Multi-color Ramsey number for triangles
• 维基百科 Ramsey's theorem
• OpenAI 官方 PDF（含第 9 章定理）。Ten advances in mathematics