浅议ramsey问题在奥数中应用

《浅议ramsey问题在奥数中应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浅议Ramsey问题在奥数中应用　　摘要：Ramsey问题是抽屉原理的推广和进一步应用，在奥数中占有重要地位。本文分析了奥数中出现的Ramsey问题的基本形式，并着重分析了其中题目本身并未出现染色，但要转化为染色的Ramsey问题，并进一步通过实例说明了对于该类问题的处理方法。关键词：抽屉原理；Ramsey问题抽屉原理是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个重要的原理。定理1抽屉原理[28]（基本形式）：将个物体放入到个抽屉中，则至少有一个抽屉中的物品数不少于两个。1930年

2、，英国逻辑学家Ramsey将抽屉原理进行了推广，得到了Ramsey定理（又称广义抽屉原理）。定理2世界上任意六个人中，必有三个人，两两认识或两两不认识。1959年，《美国数学月刊》又进一步提出[28]：定理3任意18个人的集会上，一定有4人互相认识，或者互不认识。在图论中，将个点中的任意的两点均用线段连接，得的图形称为点完全图，记作。在中，这8个点称为“顶点”，连接顶点的线段叫做“边”。这样，如果将每个人视为平面上无三点共线的点，并做完全图。在完全图中，如果两人相识，则两人连线涂以红色，否则涂以蓝色，则上述定理问题也可表述为：定理2’在平面上

3、无三点共线的六个点组成的完全图中，对其每条边随意涂以红蓝两色之一，那么中一定可以找到同色的。定理3’在平面上无三点共线的18个点组成的完全图中，对其每条边随意涂以红蓝两色之一，则中一定可以找到同色的。以下证明该定理2’：证明：任取一个顶点，因为以它为端点的5条边染了两种颜色，所以一定有一种颜色的边数大于3。不妨设，，是红边。再看，，，如果这三条边中出现一条红边，例如是红边，那么是红三角形（如图3.1，这里实线表示红色，虚线表示蓝色，下同）。否则，这三条边全是蓝边，图3.2，就有了蓝三角形。证毕。一般地，对于任意一对自然数，可以提出这样的问题；

4、在任意阶双色完全图中，要么有红色的完全子图，有么有蓝色的完全子图，问的最小值应是多少？这个非负整数，被记为，称为关于的Ramsey数。8以下定理说明了Ramsey数的一个重要性质：定理4.证明令，可以证明，对于的边用红、蓝着色后，其中必存在红色的或蓝色的，从而可知。原因如下任取的一个顶点，根据抽屉原理，顶点与其它顶点的连线中，有以下结果之一成立1、红边不少于2、蓝边不少于当（1）成立时，即由顶点出发与之以红边相连的顶点有，按照的定义，这个顶点本身所构成的完全图即可导出蓝色的或红色的，而在加上顶点即可构成红色的。当（2）成立时，与上面分析相类似

5、，由与顶点以蓝边相连的个顶点有在加上顶点所构成的完全图中存在红色的或蓝色的。证毕。通常，往往把与图的染色、Ramsey数、抽屉原则关联的问题称为Ramsey问题。8在数学竞赛中，该类问题的提法一般有两种：其一是染色问题，即题目叙述中有染色，需要我们去判断图形具有某种性质尸的方案是否存在（存在性问题），若存在，有时要计算染色方案（计数问题），有时要具体找出来（构造性问题），有时还要寻找最优方案（最优化问题）。其二是染色方法，即题目本身并未出现染色，我们在解题中作为解题手段进行了染色。而相对而言，后者出现的次数更多。以下例题即属于后者。例1：17

6、名科学家中，每人都和其它人通信。在他们的通信中只讨论三个题目。而且任意两名科学家通信时，只讨论一个题目。证明，其中至少有三名科学家，他们相互通信时，讨论的是同一个题目。（6届IMO试题）证：用顶点代表科学家，两人相互通信则连上一条边。若两人在通信中讨论题，则在此边上染色。根据抽屉原理，在这个三色完全图中，任取一个顶点，从它“伸出”的16条边中，至少有一种颜色的边的数目不小于6。从其中取出6条色边，则有以下两种情况：（1）如果这些边的另一端点所构成的子图中含色边，则该边的两端点与所取的顶点构成色三角形（三边分别为中含色边，以及前面所取的顶点“伸

7、出”的与中色边的端点连线）。（2）如果这些边的另一端点所构成的子图中不含含色边，就是双色完全图。根据定理1.1，其中必有单色三角形。这就是说，有三位科学家在通信中讨论的是同一题目。8证毕。上例将问题等价地转化为对的边染3色的问题，进一步证明了其中必然存在同色。从而证明了结论。事实上，该问题也可以简单地等价记为：广义Ramsey数[44]。例2两个航空公司为10个城市通航，使得任何两个城市间恰有一个公司开设直达航班进行服务，试证至少有一个公司能提供两个互不相交的旅游圈，每圈可游览奇数个城市。（31届IMO备选题）证用两种颜色分别标记两个公司服务

8、的航线，于是本题用图论语言叙述为：任何一个10阶二色完全图中，必存在两个无公共顶点的同色奇圈（顶点个数为奇数的圈）。下面，来证明这个命题。（i）因为，所以10阶二色