数学兴趣大讲堂Ramsey 问题 有这么一个定理：六个人参加一场会议，其中某些人之间握过手，那么一定存在三个人互相之间都握过手，或者三个人互相之间都没握过手。我们可以借助鸽笼原理很快证明这个结论。选出其中一个人 A ，然后把剩下的五个人分成两组，和 A 握过手的，以及没和 A 握过手的。显然，其中一组至少有三个人。不妨假设和 A 握过手的那一组至少有三个人吧。把这一组里的三个人分别记作 B 、 C 、 D（如果这一组的人数大于 3 ，任意选三个人就行了）。如果 B 、 C 、 D 三个人之间有两个人握过手，那么这两个人和 A 就成了互相之间握过手的三人组；如果 B 、 C 、 D 三个人之间都没握过手，那么他们本身就成了互相之间都没握手的三人组。如果至少有三个人的是没和 A 握手的那一组，根据类似的推理也能得出，总能找到互相之间都握过手或者都没握过手的三个人。 1930 年，英国数学家 Frank Ramsey 证明了一个更强的结论：给定两个正整数 r 和 s ，总能找到一个 n ，使得一场 n 人会议中，或者存在 r 个人互相之间都握过手，或者存在 s 个人互相之间都没握过手。用图论的语言来叙述，就是对于任意给定的 r 和 s ，总存在一个 n ，使得在完全图 Kn 的任意一种红蓝二染色方案中，要么存在一个大小为 r 的红色完全子图，要么存在一个大小为 s 的蓝色完全子图。我们把满足条件的最小的 n 记作 R(r, s) 。 前面我们已经证明了，六个人足以产生互相都握过手的三个人或者互相都没握手的三个人，也就是说 R(3, 3) ≤ 6 。但五个人是不够的，比方说如果只有 A 和 B 、 B 和 C 、 C 和 D 、 D 和 E 、 E 和 A 之间握手，容易看出不管选哪三个人，握过手的和没握过手的总是并存。因此， R(3, 3) 精确地等于 6 。 求出 R(r, s) 的精确值出人意料地难。目前已经知道 R(4, 4) = 18 ，但对于 R(5, 5) ，我们只知道它介于 43 到 49 之间，具体的值至今仍未求出来。如果要用计算机硬求 R(5, 5) ，则计算机需要考虑的情况数大约在 10300 这个数量级，这是一个不可能完成的任务。而 R(6, 6) 就更大了，目前已知它在 102 到 165 的范围内。它的准确值是多少，恐怕我们永都不可能知道了。 Erdős 神牛曾经说过，假如有一支异常强大的外星人军队来到地球，要求人类给出 R(5, 5) 的准确值，否则就会摧毁地球。Erdős 建议，此时我们应该集结全世界所有数学家的智慧和全世界所有计算机的力量，试着求出 R(5, 5) 来。但是，假如外星人要求人类给出 R(6, 6) 的准确值，那么 Erdős 建议，我们应该试着摧毁外星人军队。