2 第2章 鸽巢原理整理ppt.ppt

第二章 鸽巢原理 内容提要 鸽巢原理：简单形式 鸽巢原理：加强形式 Ramsey 定理 鸽巢原理又称抽屉原理或鞋盒原理, 这个原理最早是由Dirichlet提出的. 鸽巢原理是解决组合论中一些存在性问题的基本而又有力的工具. 它是组合数学中最简单也是最基本的原理之一, 从这个原理出发, 可以导出许多有趣结果,而这些结果常常是令人惊奇的. Ramsey理论对组合数学发展产生过重要的影响. 1928年, 年仅24岁的英国杰出数学家Ramsey发表了著名论文《论形式逻辑中的一个问题》, 他在这篇论文中, 提出并证明了关于集合论的一个重大研究成果, 现称为Ramsey定理. 尽管两年后他不幸去世, 但是他开拓的这一新领域至今仍十分活跃, 而且近年来在科技领域获得了成功的应用. 本讲主要介绍鸽巢原理、Ramsey数及性质、 Ramsey定理及应用. 鸽巢原理 例1. 如果有13个人其中必然有两个人出生在同一个月. 例2. 如果鞋架上放10双鞋, 从中任意取11只, 其中至少有两只恰好是配对的. 例3. 从整数1,2,…,100中选51个数, 证明在所选的数中间必然存在两个整数, 其中之一可以被另一个整除. 证明 对于任何一个整数x, 总可以把x写成x=2n?a形式, 其中a是奇数, n?0. 1到100之间一共有50个奇数, 由所选的51个数利用上述方式可以得到51个奇数, 其中必然有两个相同, 设这两个数为: x=2ra, y=2sa, 如果r?s, 那么x|y; 如果rs, 那么y|x. 本例中: 鸽子=去掉2因子得到的奇数; 鸽巢=1到100之间奇数. 这个例子可以推广到从1,2,…,2n中任意取n+1个数, 其中必然存在两个数, 其中一个整除另外一个, 证法类似. 例4. 在一个边长为1的正三角形中任意取 5个点, 必然有两个点之间距离不超过1/2. 在边长为1的正六边形中, 任意选取7个点, 必然有两个点之间的距离不超过1. 只要通过画图, 找出相应的鸽子和鸽巢 就可以解决问题. 利用鸽巢原理解决问题的关键在于: 辨认问题, 建立鸽巢, 寻找鸽子. 一般形式鸽巢原理 定理2 设m1,m2,?,mn均为正整数,如果有m1+m2+?+mn-n+1只鸽子飞回n个鸽巢,则或者第1个鸽巢至少有m1只鸽子,或者第2个鸽巢至少有m2只鸽子,?,或者第n个鸽巢至少有mn只鸽子. 证明 用反证法. 假若第1鸽巢少于m1只鸽子, 第2鸽巢少于m2个鸽子, …, 第n鸽巢少于mn只鸽子, 则鸽子总数至多为: (m1-1)+(m2-1)+…+(mn-1) =m1+m2+…+mn-n, 这比假定的鸽子数少了一个, 矛盾. ? 从定理2可得出以下推论： 推论1 如果m1=m2=?=mn=r, 若将n(r-1)+1个球放入n个盒子中, 则至少有一个盒子含有不少于r个球. 推论2 如果n个正整数m1,m2,?,mn的平均数(m1+m2+?+mn)/nr-1,则m1,m2, ?,mn中至少有一个正整数不会小于r. 推论3 有m个球放入n个盒子,则至少有一个盒子中有不少于[(m-1)/n]+1个球. 例8. 随意给一个正十边形的10个顶点标上号码1,2,…,10, 求证: 必然有一个顶点, 该顶点及与之相邻的两个顶点的标号之和不小于17. 证明 设v1,v2,…,v10是正十边形的10个顶点, ai表示顶点vi及与vi相邻的两个顶点标号之和, 则 a1+a2+…+a10=(1+2+…+10)?3 =165(17-1) ? 10+1 这样必然有某个ak?17. ? 定理3 (Erd?s)由n2+1个不同实数构成的 序列中, 至少存在由n+1个实数组成一个 单调递增子序列或单调递减子序列. 证 设原序列为: 如果全部的min+1, 则这些整数必定在1 到n之间, 相当于把n2+1个球放入n个盒 子.由定理2的推论1可知, 这是r=n+1的特 殊情况, 这n2+1个mi中至少有n+1个数 相等.不妨设 Ramsey数 在引出Ramsey数之前,先给出几个引理. 引理1 若集合S由6个人组成, 那么S中或者存在至少3个人互相认识,或者存在至少3个人互不认识. 证明 在6个人中, 任意固定一个人A, 则其 余的5人可以分成两部分, 一部分是由与 A认识的人组成的F, 另外一部分是由与 A不认识的人组成的T, 由鸽巢原理, 这两 部分至少有一部分含有3个人. |F|=3. 这时候, 如果F中3个人都互相不认识, 自然命题得证; 如果其中至少有2个人互相认识, 则这