liu的小天地 世间百态 拉姆赛定理 朋友,还是陌生人

拉姆赛定理 朋友,还是陌生人

朋友,还是陌生人 : 一次数学家集会上,休息时,有人提出一条定理:“世界上任何六个人中,必有三人或者互相认识或者互相不认识。”
多么不可思议的命题!你相信它是正确的吗?读了下面的证明,你就不能不相信了。
我们用空间任意六个点: A0、 A1、 A2、 A3、 A4、 A5表示这六个人(其中无三点共线),在每两点间连接的15条线段中,或涂上红色(表示线段两端点代表的人互相认识),或涂上蓝色(表示线段两端点代表的人互相不认识)。这样上述定理就是要求证明必存在三点,以此三点为顶点的三角形的三边涂有相同的颜色(即或均为红色,或均为蓝色)。
从任意一点(不失普遍性)A0出发,与余下的五点A1、 A2、 A3、 A4、 A5连接得五条线段,在此五条线段中只有两种颜色,故必存在三条是同色的。设A0A1、 A0A2、 A0A3均为红色,则在A1A2、 A2A3、 A3A1三条线段中可分为两种情形:
(1) A1A2、 A2A3、 A3A1均为蓝色,则△A1A2A3三边同为蓝色,即A1、 A2、 A3三人互相不认识,如图1,图中实线表示红色,虚线表示蓝色;
(2) A1A2、 A2A3、 A3A1三条中至少有一条是红色的,如A1A2为红色,则△A0A1A2的三边同为红色,即A0、 A1、 A2三人互相认识,如图2。

图1

 

图2

所以,无论怎样的六个人中,必有三人或者互相认识,或者互相不认识。
这一命题很快被推广,发展成为组合数学中著名的拉姆赛问题。拉姆赛(F.P. Ramsey, 1903—1930)是英国数理逻辑学家,他把“抽屉原则”推广,得出广义抽屉原则,也称拉姆赛定理。本题就是拉姆赛定理的特殊形式。

上一篇
下一篇
返回顶部