登陆注册
33360600000053

第53章 都认识或都不认识

拉姆赛是位英国的天才科学家,他只活了26岁,却对数理逻辑和经济学做出不可磨灭的贡献。而作为研究逻辑的副产品,以他命名的拉姆赛理论已成为组合理论乃至数学的一个重要分支,在各个领域特别是计算机科学中有着重要应用。

拉姆赛的出发点非常奇特,看起来同数学没什么关系。任何一个集会,聚会或者宴会,参加者都是四面八方来的人,两人可能相互认识或相互不认识。拉姆赛的定理是讲,如果集会的总人数等于或超过6个人,那么其中至少有3人,这3个人互相都认识或者都不认识。但是如果人数少于6人,则这种情况不一定出现。

有数学训练的人与没有数学训练的人之间的不同在于前者能把这样一个说起来模糊的问题变成为一个非常清楚的数学问题。6个人我们可以用6个点来代表,而每两人之间的关系只有两种可能。两人相互认识或相互不认识。如果两人认识,则连上一条蓝线。这样对任何情况,我们就得到一个6个点以及每两点之间的连线你如何选,那么这个图中一定存在一个三角形,它的三边都是同一颜色,或都是红色,或都是蓝色。

道理很简单,如图79,从A点出发有5条线,这5条线涂上两种颜色,无论怎样涂,至少有三条是一种颜色,其实这就是抽屈原理。假设AB,AC,AD三条边是红色,我们看BC,CD,BD这三条边,当然有这两种可能性:

一种可能是BC,CD,BD中有一条红边,例如BD是红色,那么,ABD就是全红三角形。

另一种可能是BC,CD,BD中没有一条红边,那它们都是蓝边,这样一来BCD就是全蓝三角形。

因此,不管怎么说,总有一个同一颜色的三角形。由于在我们的证明中只用到抽屉原理,所以后来由拉姆赛定理也称为广义抽屉原理。不过我们还得补充两点:如果只有五个点或更少,拉姆赛定理不一定成立。这只要找一个图,没有同色三角形。如果图80中的五边形和它中间的五角星是两个颜色,那这图中就没有全色三角形。如果多于六个点,当然拉姆赛定理一样成立。6就是存在同色三角形的最小数目,称为拉姆赛数,记作r(3,3)=6。

拉姆赛定理只不过是拉姆赛理论的出发点,它已经有了许多推广,但求拉姆赛数是一个极为困难的问题。现在只知道r(4,4)=18,也就是只有18人或18人以上的集会中才一定有四个人互相认识或互相不认识。更大的拉姆赛数尚不知道。

同类推荐
  • 新课标名人阅读-中外文学家(插图版)

    新课标名人阅读-中外文学家(插图版)

    本文主要介绍李白、杜甫、韩愈、曹雪芹、苏轼、冰心、雨果、丹尼尔·笛福、莎士比亚、莫里哀、歌德、高尔基等文学家。
  • 新课程师资培训教程-高一化学优秀课例

    新课程师资培训教程-高一化学优秀课例

    为新课程实施和提高教师专业化水平而精心编写,选取了大量教案,内容上充分体现了知识性和趣味性。接受课改新理念,感受课改新思维,使用课改新教材,至始至终课改给人一种焕然一新的感觉。它是一次革命,一场对话,一座平台,一把迈向成功教育的钥匙。
  • 妙不可言的人体奥秘

    妙不可言的人体奥秘

    本书内容包括:构成人体的细胞;神经系统的结构;脊髓和脊神经;脑的组成;脑神经;神经系统指挥人体活动;脑的高级机能等内容。
  • 植物组织培养

    植物组织培养

    本书按照植物组织培养育苗的生产过程将教学内容分为六个项目:植物组织培养工厂(实验室)建立、植物组织培养基本操作、离体培养体系建立、脱毒苗培育、植物组织培养工厂化育苗,以及植物组织培养育苗生产管理。通过这些项目将植物组织培养的理论知识和操作技能有机地结合在一起,从而达到教、学、做一体化的教学目的,使学生充分享受学中做、做中学的乐趣。
  • 语文新课标课外必读·第六辑:爱丽丝漫游奇境记

    语文新课标课外必读·第六辑:爱丽丝漫游奇境记

    国家教育部颁布了最新《语文课程标准》,统称新课标,对中、小学语文教学指定了阅读书目,对阅读的数量、内容、质量以及速度都提出了明确的要求,这对于提高学生的阅读能力,培养语文素养,陶冶情操,促进学生终身学习和终身可持续发展,对于提高广大人民的文学素养具有极大的意义。
热门推荐
  • 秀甲天下

    秀甲天下

    萧天战是一个剑客,却又不是一个真正的剑客,因为即便是再锋利的剑,到了他的手上,伤的永远是自个!爱上不该爱的人,比喝醉了酒还要难受。而等待他的所谓江湖,不过是一场场精心设计耳朵阴谋,他终于明白,为什么自个那个不可一世的剑圣老子,会在声名如日中天的时候抛弃妻子,退隐江湖。可就算明白了又有何用?该来的终究要来,想躲的也注定躲不掉,这就是一个剑客不得不去面对的劫数!
  • 风暴的诗

    风暴的诗

    或随兴,或慨叹……有时候顾虑前后,有时候又似颠似狂,这就是我,真实的我!——《叠夕集》,记录着我日常生活的点点滴滴……
  • 杰克·伦敦短篇小说集

    杰克·伦敦短篇小说集

    杰克·伦敦是美国著名的现实主义作家,在现代美国文学和世界文学中享有崇高的地位。他擅长以人物的行动来表现主题思想,人物形象具有鲜明的个性,故事情节紧凑,文字精练生动,有相当的感染力。他一生热爱奋斗和冒险,创作了50多部短篇小说、长篇小说和故事,其中许多作品堪称短篇小说的经典,为人们了解美国人及其性格提供了生动的素材。
  • 重聆

    重聆

    她白千沫,一名来自福利院的孤儿,受恩人所养,从此认恩人为自己的姑姑,她把她当成自己最亲的人,甚至因为她宁可与所有人反目成仇。而她却没有想到她的恩人竟然就是自己最大的仇人的母亲,沦为孤儿,从小百毒缠身,病发时,她的身体如千蛇万蚁筮血,她须饮血解除痛苦,却不料一切竟是拜所谓的姑姑所赐。他陌上寒御,全球前三首富之一,为了她成为世界第一,他爱惨了她,因血型与她所需的不一致而去换血,他爱她着了魔。自己被她认为是杀害自己姑姑的凶手,残酷到不惜杀害自己的亲生骨肉更是撞死了她爱的男人的恶魔。而他却被她亲手在盛大的婚礼捅死。他爱她,她恨他。婚礼上烈阳下飞起了雪花,那一刻她才知道她爱他。原来孩子没有死,自己之前所爱的人是先来撞他的,姑姑是被人害死的,一切的主谋居然是自己的好闺蜜大明星,她后悔了却无力回天,看着怀中的儿子,在婚礼上自刎了。陌上寒御,若有来生,定不负你……有第二册呀~
  • 沉思录

    沉思录

    《沉思录》,古罗马唯一一位哲学家皇帝马可?奥勒留?安东尼所著,是一本写给自己的书,内容大部分是他在鞍马劳顿中写成的。它来自作者对身羁宫廷的自己和自己所处混乱世界的感受,追求一种冷静而达观的生活。这本书是斯多葛学派的一个里程碑。
  • 天行

    天行

    号称“北辰骑神”的天才玩家以自创的“牧马冲锋流”战术击败了国服第一弓手北冥雪,被誉为天纵战榜第一骑士的他,却受到小人排挤,最终离开了效力已久的银狐俱乐部。是沉沦,还是再次崛起?恰逢其时,月恒集团第四款游戏“天行”正式上线,虚拟世界再起风云!
  • 天行

    天行

    号称“北辰骑神”的天才玩家以自创的“牧马冲锋流”战术击败了国服第一弓手北冥雪,被誉为天纵战榜第一骑士的他,却受到小人排挤,最终离开了效力已久的银狐俱乐部。是沉沦,还是再次崛起?恰逢其时,月恒集团第四款游戏“天行”正式上线,虚拟世界再起风云!
  • 狼族:暑假的惊悚之旅

    狼族:暑假的惊悚之旅

    玄幻的飘渺和悬疑的惊悚……
  • 天神之体

    天神之体

    叶天,天玄大陆史上第一废物,却拥有整个宇宙唯一的天神之体!在他师傅韩雪吟的指导下,最终改变了他废物的命运,踏上了成神的道路!阴玄、阳玄、地王、天王、天尊、武尊、帝尊、神
  • 桂宫

    桂宫

    桂宫非宫,而是一个天下人都梦寐以求的巨大宝藏。一位很雷人的女同学穿越成一位很雷人的女侠,在见识过江湖内外各色美男为争夺桂宫吵嚷不休之后,立志要改行当一名龟公。