noski 发表于 2009-8-14 09:57:17

一个有趣的定理:拉姆齐定理

在组合数学上,拉姆齐(Ramsey)定理是要解决以下的问题:要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识。
这个定理以弗兰克·普伦普顿·拉姆齐命名,1930年他在论文On a Problem in Formal Logic(《形式逻辑上的一个问题》)证明了R(3,3)=6。

已知的拉姆齐数非常少,保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。”

R(3,3)等于6的证明
证明:在一个K6的完全图内,每边涂上红或蓝色,必然有一个红色的三角形或蓝色的三角形。
任意选取一个端点P,它有5条边和其他端点相连。
根据鸽巢原理,3条边的颜色至少相同,不失一般性设这种颜色是红色。
在这3条边除了P以外的3个端点,它们互相连结的边有3条。
若这3条边中任何一条是红色,这条边的两个端点和P相连的2边便组成一个红色三角形。
若这3条边中任何一条都不是红色,它们必然是蓝色,因此,它们组成了一个蓝色三角形。
而在K5内,不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点 的线是红色,和其余两个端点的连线是蓝色即可。


这个定理的通俗版本就是友谊定理。

友谊定理

友谊定理(Friendship Theorem)说明:在一群不少于三人的人中,若任何两人都刚好只有一个共同认识的人,这群人中总有一人是所有人都认识的。
在图论的角度来说,一幅图,若每个顶点都跟另一个顶点刚好只有一个共同相邻的顶点,这幅图中有一个顶点和其他顶点都相邻。

(来源Wiki)

黑桃Q 发表于 2009-8-14 10:04:20

沙发顶一下能看明白的人会觉得有趣:loveliness:

☆文☆ 发表于 2009-8-14 10:54:46

:o 那么强,太顶了~

yang_bigarm 发表于 2009-8-16 21:15:36

一般性的 R(n,n)  等于多少是世界级的难题,目前人类对它还只是甚少,不亚于哥德巴赫猜想。

关于这个定理,我在组合数学的书上看到过一个趣题,可以发在这个版上,不过我想等这个帖沉底了再发。

[ 本帖最后由 yang_bigarm 于 2009-8-16 21:17 编辑 ]

conwood 发表于 2009-8-16 22:40:13

这个东西很有趣,有一个故事说,如果外星人人攻打地球,要求人类算出来R(5,5)否则就毁灭地球,人类的应对方案就是召集全世界的数学家和计算机,拼命的算出来,如果让人类算R(6,6),就只有跟外星人决一死战了。

东莞的8 发表于 2009-8-16 22:43:55

组合数学教程里有说到过这个定理,但本人的数学基础巨差,一点都看不明白:lol ,甚至这个分支都不了解:lol

Paracel_007 发表于 2009-8-18 21:43:40

其实K6里是必存在两个同色三角形的

aubell 发表于 2009-10-11 20:03:38

看了这个才知道人类的智能还是如此的局限

kschiew 发表于 2012-12-14 23:56:55

yang_bigarm 发表于 2009-8-16 21:15 static/image/common/back.gif
一般性的 R(n,n)  等于多少是世界级的难题,目前人类对它还只是甚少,不亚于哥德巴赫猜想。

关于这个定理 ...

你可以发了,反正这贴基本上已经沉底了...

qijiaoxing 发表于 2012-12-15 08:49:12

这个先收藏一下
页: [1] 2
查看完整版本: 一个有趣的定理:拉姆齐定理