鸽巢原理、Ramsey数.pptVIP

3.4 鸽巢原理 鸽巢原理，又叫抽屉原理，是一个重要而又初等 的组合学原理，它能够解决各种有趣的问题，常 常得出一些令人惊奇的结论. 它指的是一个简单的 事实：如果鸽子的数目比巢穴的数目多，那么至 少要有一个鸽巢被两只或多只鸽子占据(简单的说, 即“若有n个鸽子巢，n+1个鸽子，则至少有一 个巢内有至少有两个鸽子。”). 下面我们将给出更 精确的叙述，以及鸽巢原理的应用举例. 3.4 鸽巢原理 证明: 设这n+1个数是 a1,a2,…,an+1 3.4 鸽巢原理 对此序列中的每一个数去掉一切2的因子，直至剩下一个 奇数为止. 例如，68＝2×2×17，则去掉2×2，只 留下17. 那么我们会得到一个由奇数组成的序列 b1,b2,…,bn+1 1到2n之间只有n个奇数，故序列{ b1,b2,…,bn+1}中至少有 两个是相同的. 设bi = bj = b，则bi = 2pa，bj = 2qa,由于 bi≠bj，显然，其中一个是另一个的倍数. 3.4 鸽巢原理 定理 3.4.2 设a1,a2,…,an都是正整数. 如果把a1+a2+…+an- n+1个鸽子住入n个鸽巢，那么或者第一个鸽巢至少住入 a1个鸽子，或者第二个鸽巢至少住入a2个鸽子，……，或 者第n个鸽巢至少住入an个鸽子。 证明 设将a1+a2+…+an-n+1个鸽子住入n个鸽巢中. 如果对 于每个i =1,2,…,n，第i个鸽巢都不能住入ai个或更多的鸽 子，那么所有鸽巢中的鸽子的总数不超过 (a1-1) + (a2-1) + … + (an-1) = a1+a2+…+an-n 比原鸽子数少1. 因此，必存在某个i ，使得第i个鸽巢至少含有ai个鸽子. 3.4 鸽巢原理 3.4 鸽巢原理 推论 3.4.3 设a1,a2,…,an是n个整数，而且 则a1,a2,…,an中至少有一个数不小于r. 3.5 Ramsey数问题 3.5 Ramsey数问题 证明 设v1, v2, v3, v4, v5, v6,是该完全图的6个顶点，v1与v2, v3, v4, v5, v6所连的5条边着红色或蓝色. 由鸽巢原理知， 其中至少有3条边同色. 不妨设v1与v2, v3, v4所连 的3条边均为红色，如图所示.若v2, v3, v4间有一条红边， 不妨设为v2v3，则△v1v2v3是一红色三角形. 否则，v2, v3, v4间均为蓝边， △v2v3v4是一蓝色三角形. 3.5 Ramsey数问题 3.5 Ramsey数问题 类似于命题3.5.1，还有命题3.5.2和命题3.5.3如下 命题 3.5.2 对6个顶点的完全图任意进行红、蓝两边着 色，都至少存在两个同色的三角形. 命题 3.5.3 对10个顶点的完全图K10任意进行红、蓝两 边着色，都或者存在一个红色K4，或者存在一个蓝色K3. 命题3.5.3还可以加以更严格的限制： 命题 3.5.4 对9个顶点的完全图K9任意进行红、蓝两边 着色，都或者存在一个红色K4，或者存在一个蓝色K3. 3.5 Ramsey数问题 定义 3.5.1 对于任意给定的两个正整数a和b，如果存在最 小的正整数R(a,b)使得当N≥R(a,b)时，对KN任意进行红、 蓝两边着色，KN中均有红色Ka，或蓝色Kb，则R(a,b)称为 Ramsey数. 3.5 Ramsey数问题 证: 令N＝R(a-1,b) + R(a,b-1), 对KN进行任意红、蓝两边着色. 设x是KN的一个顶点,在KN中与x相关联的边共有R(a-1,b) + R(a,b-1)-1条,这些边要么为红色,要么为蓝色. 由鸽巢原理知,与x相关联的这些边中,要么至少有 R(a-1,b)条红色的边,要么有至少R(a,b-1)条蓝色的边. 3.5 Ramsey数问题 （1）这些边中有R(a-1,b)条红边. 在以这些红边相关联的 R(a-1,b)个顶点构成的完全图KR(a-1,b)中,必有一红色Ka-1或蓝色Kb. 若有红色Ka-1，则它加上顶点x以及x与Ka-1之间的红边，即构成一个红色Ka；否则，就有一个蓝色Kb. （2）这些边中有R(a,b-1)条蓝边. 在以这些蓝边与x相关联的R(a,b-1)个顶点构成的完全图KR(a,b-1)中，必有一个红色Ka或一个蓝色Kb-1，若有蓝色Kb-1，则它加上顶点x以及x与Kb-1之间的蓝边，即构成一个蓝色Kb；否则，就有一个红色Ka. 综合（1）、（2），知R(a,b)≤N. 3.5 Ramsey数问题 证： 对a+b作归纳. 当a+b≤5时，a=2或b=2，由定理3.5.1知定理3.5.3成立. 假设对一切满足5≤a+bm+n的a,b，