都认识或都不认识-拉姆赛理论

拉姆赛是位英国的天才科学家，他只活了26岁，却对数理逻辑和经济学做出不可磨灭的贡献。而作为研究逻辑的副产品，以他命名的拉姆赛理论已成为组合理论乃至数学的一个重要分支，在各个领域特别是计算机科学中有着重要应用。拉姆赛的出发点非常奇特，看起来同数学没什么关系。任何一个集会、聚会或者宴会，参加者都是四面八方来的人，两人可能相互认识或相互不认识。拉姆赛的定理是讲，如果集会的总人数等于或超过6个人，那么其中至少有3人，这3个人互相都认识或者都不认识。但是如果人数少于6人，则这种情况不一定出现。有数学训练的人与没有数学训练的人之间的不同在于前者能把这样一个说起来模糊的问题变成为一个非常清楚的数学问题。6个人我们可以用6 个点来代表，而每两人之间的关系只有两种可能。
     两人相互认识或相互不认识。如果两人认识，我们在代表他们的这两点之间连上一条红线，如果两人不认识，则连上一条蓝线。这样对任何情况，我们就得到一个6个点以及每两点之间共有 15 条连线的图。因此，这个定理是说不管两点之间的连线你如何选，那么这个图中一定存在一个三角形，它的三边都是同一颜色，或都是红色，或都是蓝色。道理很简单，如图，从A点出发有5条线。这5条线涂上两种颜色，无论怎样涂，至少有三条是一种颜色，其实这就是抽屉原理。假设AB，AC，AD三条边是红色，我们看BC，CD，BD这三条边，当然有这两种可能性：一种可能是BC，CD，BD中有一条红边，例如BD是红色，那么ABD就是全红三角形。另一种可能是BC，CD，BD中没有一条红边，那它们都是蓝边，这样一来BCD就是全蓝三角形。
     因此，不管怎么说，总有一个同一颜色的三角形。由于在我们的证明中只用到抽屉原理，所以后来由拉姆赛定理也称为广义抽屉原理。不过我们还得补充两点：如果只有五个点或更少，拉姆赛定理不一定成立。这只要找一个图，没有同色三角形。五边形和它中间的五角星是两个颜色，那这图中就没有全色三角形。如果多于六个点，当然拉姆赛定理一样成立。6就是存在同色三角形的最小数目，称为拉姆赛数，记作r（3， 3）＝6。拉姆赛定理只不过是拉姆赛理论的出发点，它已经有了许多推广，但求拉姆赛数是一个极为困难的问题。现在只知道 r（4，4）＝18，也就是只有18人或18 人以上的集会中才一定有四个人互相认识或互相不认识。更大的拉姆赛数尚不知道。