Ramsey数

抽屉原理与拉姆塞（Ramsey）定理教学安排的说明章节题目：抽屉原理与拉姆塞定理学时分配：2课时本章教学目的与要求：理解抽屉原理，能够用抽屉原理解决简单的数学问题，理解拉姆塞数的含义，理解抽屉原理与拉姆塞定理间的联系。其它：本部分为补充内容课堂教学方案课程名称：抽屉原理与拉姆塞（Ramsey）定理授课时数：2学时授课类型：理论课教学方法与手段：讲授法教学目的与要求：理解抽屉原理，能够用抽屉原理解决简单的数学问题，理解拉姆塞数的含义，理解抽屉原理与拉姆塞定理间的联系。教学重点、难点：抽屉原理与拉姆塞定理间的联系教学内容：补充：抽屉原理与拉姆塞（Ramsey）定理抽屉原理抽屉原理又叫鸽巢原理.桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n＋1或多于n＋1个元素放到n个集合中去，其中必定至少有一个集合里至少有两个元素。”抽屉原理有时也被称为鸽巢原理（“如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2只鸽子”）。它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原理。它是组合数学中一个重要的原理。一．抽屉原理最常见的形式1.抽屉原理的最简单形式：如果把n十l件东西放入n个盒子，则至少有一个盒子含有两件或更多件东西。[证明]（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+1，矛盾.例１：400人中至少有两个人的生日相同.解：将一年中的365天视为365个抽屉，400个人看作400个物体，由抽屉原理可以得知：至少有两人的生日相同.又如：我们从街上随便找来13人，就可断定他们中至少有两个人属相相同.“从任意5双手套中任取6只，其中至少有2只恰为一双手套。”“从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同。”2.抽屉原理的加强形式设12,,,nqqq是n个正整数，如果将121nqqqn件东西放入n个盒子里，则必有第i个盒子里至少装有iq件东西。特别地，当12nqqqr时，则有：若将11nr个物体放入n个盒子中，则必存在一个盒子至少装r个物体。取1mr，则有：把多于mn个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。如果n个非负整数12,,,nqqq的平均数大于1r，那么至少有一个整数大于或等于r，这是平均原理，抽屉原理多用于证明题或作出某种判断或最好决策。二．应用抽屉原理解题抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。例2在小于或等于2n的任意n+1个不同的正整数中，一定存在两个正整数，使得它们是互素的。证明：构造如下n个抽屉，1R放1，2；2R放3，4；…；nR放2n-1，2n。根据抽屉原理，这n+1个小于或等于2n的正整数放入这n个抽屉中。可以断定，必有两个数被放入同一个抽屉中，且这两个数相邻。比如有k和k-1在同一抽屉中，可以证明k和k-1是互素的。设m为k和k-1的任意正整数因子，则必存在正整数,,pqpq，使得,1kpmkqm，于是，11kkpqm.因此1m，即k和k-1是互素的。拉姆塞（Ramsey）定理抽屉原理的一个深刻而又重要的推广就是以英国逻辑学家FrankPlumptonRamsey命名的定理——Ramsey定理弗兰克·普伦普顿·拉姆塞(FrankPlumptonRamsey,1903-1930)是位天才的英国科学家，只活了27岁。但在经济学中做出极重要贡献，包括概率论，赋税论，最优储蓄理论，在他去世的1930年，他发表了一篇学术论文，其副产物就是所谓拉姆塞理论。1、拉姆塞（Ramsey）定理简介在1953年美国的WilliamLowellPutnam数学竞赛中，包含着这样一个问题：对于一个阶为6的完全图，其每条边用红色或蓝色两种颜色染色。证明：必定可以找到3个顶点，使得连接它们的三条边都有相同的颜色。其通俗解释为：如果认识是相互的，在某个宴会上，6人中必有三个人相互认识或三个人相互不认识。分析:上述两问题等价的。该问题反映出人与人之间或相互认识或相互不认识这种二元关系，这正好符合用图论方法研究问题的特征。由于所证结果是存在三人相互认识或相互不认识。于是，我们可以常用另外的刻画方式进行处理：若两人认识，在相应顶点之间连一条边，并染成红色（即连一条红边）；若两人不认识，也在相应顶点之间连条边，并染成蓝色（即连一条蓝边），从而就形成了一个染有红、蓝两色的6K。于是，可将待证问题转化为：在二色6K中一定存在同色三角形（红色三角形或蓝色三角形）。证明：用621,,,AAA表示这任何6个人，若两人认识，在相应顶点之间连一条红边；否则，在相应顶点点之间连一条蓝边。从而就形成一个染有红、蓝两色的完全图6K。考察1A，从1A所连的5条边6151413121,,,,AAAAAAAAAA中，由抽屉原理知至少有3条边染同种颜色，不妨假设413121,,AAAAAA染红色。现在考察由432,,AAA所构成的3K子图，若244332,,AAAAAA三边中有一条染红色，不妨设32AA染红色，则321AAA是红色三角形；否则244332,,AAAAAA三边均染蓝色，则234AAA是蓝色三角形。所以，在二色6K中一定存在同色三角形。六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例，这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。Ramsey：定理对于任意k13k个正整数12,,,knnn，都存在一个正整数N，使得下面命题成立：若集合1,2,,N的每一个t元子集都用k种颜色1,2,,k的一种颜色染色，则对某一个整数1iik，存在1,2,,N的包含in个元素的子集S，使得S的每个t元子集都染色为i。为了理解Ramsey定理与图论的联系，设1,2,,N为完全图NK的顶点集，首先考虑1t的情形。根据Ramsey定理，存在正整数N，使得下列命题成立：若集合1,2,,N的每一个1元子集（完全图NK的顶点）都用k种颜色1,2,,k的一种颜色染色，则对某一个整数1iik，存在in个染色为i的顶点。这是抽屉原理的一种简单变形。事实上，整数111kiiNn满足条件。Ramsey定理在2t时的情形是相当迷人的，这时，集合1,2,,N的任意2元子集用k种颜色1,2,,k的一种颜色染色，可解释为完全图NK的边染色Ramsey定理：对于任意2k个正整数12,,,knnn，都存在一个正整数N，使得下面命题成立：若NK的每一条边都用k种颜色1,2,,k的一种颜色染色，则对某一个整数1iik，存在一个完全子图inK，使得inK的每条边都染色为i。Ramsey定理可直观解释为：对于任意充分大的结构，无论它表现得多么无序，该结构必定表现为给定基数的有序子结构拉姆塞定理也称广义抽屉原理。2、拉姆塞数。首先介绍两个概念团：简单图G的一个团是指图G的顶点集合的一个子集S，其诱导的子图是完全图。独立集：若S为图G的顶点集合的子集，且S中任两点在G中不邻接，则称S为G的一个独立集。拉姆塞理论还有进一步的推广，一个最简单的推广是拉姆塞数(RamseyNumber),Rab，也就是集会至少有多少人，才能有a个人互相都认识或者b个人互相都不认识。用图论的语言描述：给定正整数a和b，令,Rab是保证任意的n阶图中必存在包含a个顶点的团或b个顶点的独立集的最小自然数n，具有这样性质的,Rab就称为一个拉姆塞数。注：1、由定义知：,Rab=,Rba，1,1Ra2、由于对任意的a阶图G，若G有边，则必含有两个点的团，否则含有a个点的独立集，这样,22,RaRaa3、如果只有五个点或更少，拉姆塞定理不一定成立。如果多于六个点，当然拉姆塞定理一样成立。且3,36R。下面证明：对于任意的9阶图G，必存在3个点的团，或存在含4个点的独立集。亦即在一个晚会上9人中，必有三个人相互认识或有四个人相互不认识。证明：因为图G中奇数阶顶点个数为偶数，所以G中不可能所有顶点的度数均为3。从而必存在一点v其度数不是3，以下我们证明G中若不存在含3个点的团，则必存在含4个点的独立集。情形1deg2v，此时与v不邻接的点至少有6个，设这六个顶点组成的集合为123456,,,,,vvvvvv，由于含六个点的图已经假设不存在含3个点的团,则必存在含3个点的独立集123,,vvv，则123,,,vvvv为含4个点的独立集。情形2deg4v，此时与v相邻接的点至少有4个，设为1234,,,vvvv，因假设中不存在含3个点的团，所以互不相邻，即G含4个点的独立集这个例题只能说明3,49R。既然,Rba=,Rab，我们不妨假定ab。现在知道的精确的,Rab的值极少，只有如下的9种情形:3,36R，3,49R，3,514R，3,618R，3,723R，3,828R，3,936R，4,418R，4,525R对于确定后面几个数值难度是很大的，例如确定4,525R，是1993年罗彻斯特理工学院的拉齐斯佳威斯基（S·P·Radziszowski）和澳大利亚国立大学的麦凯（B·D·Mckay）用计算机求得。他们的计算量相当于一台标准计算机11年的工作量。可见运算量有多么巨大。保证有3个人，他们或者彼此者认识或者彼此都不认识的最小的数就是6，进一步集会有多少人，才能有5个人都彼此认识或都不认识呢？至今为此，5,5R的精确数目我们还不知道，目前已知的结果为43≦5,5R≦49，计算量是不可想象的，因为如果用计算机检验43是否正确，需要画一个图，这个图有903条边，其中把任意一条边染为红色或蓝色，有2719031032种情形。即使应用运算速度为每秒1万亿次的超级计算机，也要运算10亿年！太不可想象了。至于其他的,Rnn当然就更不清楚了。不过，我们的确证明,Rnn是一个有限数，的确存在，甚至有精确的上界和下界。只是其中究竟哪一个是拉姆塞数，就不得而知了。著名的匈牙利数学家厄尔多斯（Erdos）曾经这样比喻求拉姆塞数的困难程度：一伙外星强盗在地球着陆，威胁人类说，如果不能在一年内求出5,5R，他们将动手灭绝人类！此时人类的最佳对策是调用地球上所有的计算机和计算机专家，日以继夜地来计算5,5R的值，以求人类免于灭顶点之灾；如果外星人威胁说要求得6,6R，那我们已别无选择，只能同仇敌忾，在外星人灭绝人类之前先把他们给杀死。确定拉姆塞数的道路任重而道远。