Ramsey数.doc

抽屉原理与拉姆塞（Ramsey）定理 教学安排的说明章节题目：抽屉原理与拉姆塞定理学时分配：2课时本章教学目的与要求：理解抽屉原理，能够用抽屉原理解决简单的数学问题，理解拉姆塞数的含义，理解抽屉原理与拉姆塞定理间的联系其它：本部分为补充内容课 堂 教 学 方 案课程名称：抽屉原理与拉姆塞（Ramsey）定理授课时数：2学时授课类型：理论课教学方法与手段：讲授法教学目的与要求：理解抽屉原理，能够用抽屉原理解决简单的数学问题，理解拉姆塞数的含义，理解抽屉原理与拉姆塞定理间的联系教学重点、难点：抽屉原理与拉姆塞定理间的联系教学内容：补充：抽屉原理与拉姆塞（Ramsey）定理抽屉原理抽屉原理又叫鸽巢原理.　　 桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果这一现象就是我们所说的抽屉原理　　抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n＋1或多于n＋1个元素放到n个集合中去，其中必定至少有一个集合里至少有两个元素。

　　抽屉原理有时也被称为鸽巢原理（“如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2只鸽子”）它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原理它是组合数学中一个重要的原理　　一． 抽屉原理最常见的形式1.抽屉原理的最简单形式：如果把十l件东西放入个盒子，则至少有一个盒子含有两件或更多件东西[证明]（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+1，矛盾. 例１：400人中至少有两个人的生日相同. 　　解：将一年中的365天视为365个抽屉，400个人看作400个物体，由抽屉原理可以得知：至少有两人的生日相同. 　　又如：我们从街上随便找来13人，就可断定他们中至少有两个人属相相同. 　　“从任意5双手套中任取6只，其中至少有2只恰为一双手套　　“从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同2.抽屉原理的加强形式设是个正整数，如果将件东西放入个盒子里，则必有第个盒子里至少装有件东西特别地，当时，则有：若将个物体放入个盒子中，则必存在一个盒子至少装个物体取，则有：把多于mn个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。

如果个非负整数的平均数大于，那么至少有一个整数大于或等于，这是平均原理， 抽屉原理多用于证明题或作出某种判断或最好决策二．应用抽屉原理解题　　抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用许多有关存在性的证明都可用它来解决　 例2 在小于或等于2的任意+1个不同的正整数中，一定存在两个正整数，使得它们是互素的证明：构造如下个抽屉，放1，2；放3，4；…；放2-1，2n根据抽屉原理，这+1个小于或等于2的正整数放入这个抽屉中可以断定，必有两个数被放入同一个抽屉中，且这两个数相邻比如有和-1在同一抽屉中，可以证明和-1是互素的设为和-1的任意正整数因子，则必存在正整数，使得，于是，.因此，即和-1是互素的拉姆塞（Ramsey）定理抽屉原理的一个深刻而又重要的推广就是以英国逻辑学家Frank Plumpton Ramsey命名的定理——Ramsey定理弗兰克·普伦普顿·拉姆塞(Frank Plumpton Ramsey,1903-1930)是位天才的英国科学家，只活了27岁但在经济学中做出极重要贡献，包括概率论，赋税论，最优储蓄理论，在他去世的1930年，他发表了一篇学术论文，其副产物就是所谓拉姆塞理论。

1、拉姆塞（Ramsey）定理简介在1953年美国的William Lowell Putnam数学竞赛中，包含着这样一个问题 ：对于一个阶为6的完全图，其每条边用红色或蓝色两种颜色染色证明：必定可以找到3个顶点，使得连接它们的三条边都有相同的颜色其通俗解释为：如果认识是相互的，在某个宴会上，6人中必有三个人相互认识或三个人相互不认识分析:上述两问题等价的该问题反映出人与人之间或相互认识或相互不认识这种二元关系，这正好符合用图论方法研究问题的特征由于所证结果是存在三人相互认识或相互不认识于是，我们可以常用另外的刻画方式进行处理：若两人认识，在相应顶点之间连一条边，并染成红色（即连一条红边）；若两人不认识，也在相应顶点之间连条边，并染成蓝色（即连一条蓝边），从而就形成了一个染有红、蓝两色的于是，可将待证问题转化为：在二色中一定存在同色三角形（红色三角形或蓝色三角形）证明：用表示这任何6个人，若两人认识，在相应顶点之间连一条红边；否则，在相应顶点点之间连一条蓝边从而就形成一个染有红、蓝两色的完全图考察，从所连的5条边中，由抽屉原理知至少有3条边染同种颜色，不妨假设染红色现在考察由所构成的子图，若三边中有一条染红色，不妨设染红色，则是红色三角形；否则三边均染蓝色，则是蓝色三角形。

所以，在二色中一定存在同色三角形六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例，这个简单问题的证明思想可用来得出另外一些深入的结论这些结论构成了组合数学中的重要内容-----拉姆塞理论Ramsey：定理对于任意个正整数，都存在一个正整数，使得下面命题成立：若集合的每一个元子集都用种颜色的一种颜色染色，则对某一个整数，存在的包含个元素的子集S，使得S的每个元子集都染色为为了理解Ramsey定理与图论的联系，设为完全图的顶点集，首先考虑的情形根据Ramsey定理，存在正整数，使得下列命题成立：若集合的每一个1元子集（完全图的顶点）都用种颜色的一种颜色染色，则对某一个整数，存在个染色为的顶点这是抽屉原理的一种简单变形事实上，整数满足条件Ramsey定理在时的情形是相当迷人的，这时，集合的任意2元子集用种颜色的一种颜色染色，可解释为完全图的边染色Ramsey定理：对于任意个正整数，都存在一个正整数，使得下面命题成立：若的每一条边都用种颜色的一种颜色染色，则对某一个整数，存在一个完全子图，使得的每条边都染色为Ramsey定理可直观解释为：对于任意充分大的结构，无论它表现得多么无序，该结构必定表现为给定基数的有序子结构拉姆塞定理也称广义抽屉原理。

2、拉姆塞数首先介绍两个概念团：简单图的一个团是指图的顶点集合的一个子集S，其诱导的子图是完全图独立集：若S为图G的顶点集合的子集，且S中任两点在G中不邻接，则称S为G的一个独立集拉姆塞理论还有进一步的推广，一个最简单的推广是拉姆塞数(Ramsey Number)，也就是集会至少有多少人，才能有个人互相都认识或者个人互相都不认识用图论的语言描述： 给定正整数和，令是保证任意的阶图中必存在包含个顶点的团或个顶点的独立集的最小自然数，具有这样性质的就称为一个拉姆塞数 注：1、由定义知：=，2、由于对任意的阶图，若有边，则必含有两个点的团，否则含有个点的独立集，这样3、如果只有五个点或更少，拉姆塞定理不一定成立如果多于六个点，当然拉姆塞定理一样成立下面证明：对于任意的9阶图，必存在3个点的团，或存在含4个点的独立集亦即在一个晚会上9人中，必有三个人相互认识或有四个人相互不认识证明：因为图中奇数阶顶点个数为偶数，所以中不可能所有顶点的度数均为3从而必存在一点其度数不是3，以下我们证明中若不存在含3个点的团，则必存在含4个点的独立集情形1 ，此时与不邻接的点至少有6个，设这六个顶点组成的集合为，由于含六个点的图已经假设不存在含3个点的团,则必存在含3个点的独立集，则为含4个点的独立集。

情形2 ，此时与相邻接的点至少有4个，设为，因假设中不存在含3个点的团，所以互不相邻，即含4个点的独立集这个例题只能说明既然=，我们不妨假定现在知道的精确的的值极少，只有如下的9种情形: ，， ， ，，，， ， 对于确定后面几个数值难度是很大的，例如确定，是1993年罗彻斯特理工学院的拉齐斯佳威斯基（S·P·Radziszowski）和澳大利亚国立大学的麦凯（B·D·Mckay）用计算机求得他们的计算量相当于一台标准计算机11年的工作量可见运算量有多么巨大保证有3个人，他们或者彼此者认识或者彼此都不认识的最小的数就是6，进一步集会有多少人，才能有5个人都彼此认识或都不认识呢？至今为此，的精确数目我们还不知道，目前已知的结果为43≦≦49，计算量是不可想象的，因为如果用计算机检验43是否正确，需要画一个图，这个图有903条边，其中把任意一条边染为红色或蓝色，有种情形即使应用运算速度为每秒1万亿次的超级计算机，也要运算10亿年！太不可想象了至于其他的 当然就更不清楚了不过，我们的确证明是一个有限数，的确存在，甚至有精确的上界和下界只是其中究竟哪一个是拉姆塞数，就不得而知了著名的匈牙利数学家厄尔多斯（Erdos）曾经这样比喻求拉姆塞数的困难程度：一伙外星强盗在地球着陆，威胁人类说，如果不能在一年内求出，他们将动手灭绝人类！此时人类的最佳对策是调用地球上所有的计算机和计算机专家，日以继夜地来计算的值，以求人类免于灭顶点之灾；如果外星人威胁说要求得，那我们已别无选择，只能同仇敌忾，在外星人灭绝人类之前先把他们给杀死。

确定拉姆塞数的道路任重而道远。