第2章 鸽巢原理

组合数学

第二章 鸽巢原理

组合数学

内容提要 鸽巢原理：简单形式 鸽巢原理： 鸽巢原理：加强形式 鸽巢原理： Ramsey 定理

组合数学

鸽巢原理又称抽屉原理或鞋盒原理, 鸽巢原理又称抽屉原理或鞋盒原理, 这 个原理最早是由Dirichlet提出的 提出的. 个原理最早是由Dirichlet提出的. 鸽巢原理是解决组合论中一些存在性 鸽巢原理是解决组合论中一些存在性 问题的基本而又有力的工具. 问题的基本而又有力的工具. 它是组合 数学中最简单也是最基本的原理之一, 数学中最简单也是最基本的原理之一, 从这个原理出发, 从这个原理出发, 可以导出许多有趣结 而这些结果常常是令人惊奇的. 果,而这些结果常常是令人惊奇的. Ramsey理论对组合数学发展产生过重 Ramsey理论对组合数学发展产生过重 要的影响. 要的影响.

组合数学

1928年 年仅24岁的英国杰出数学家 1928年, 年仅24岁的英国杰出数学家 Ramsey发表了著名论文 Ramsey发表了著名论文《论形式逻辑 发表了著名论文《 中的一个问题》 他在这篇论文中, 中的一个问题》, 他在这篇论文中, 提 出并证明了关于集合论的一个重大研 究成果, 现称为Ramsey定理 定理. 究成果, 现称为Ramsey定理. 尽管两年后他不幸去世, 尽管两年后他不幸去世, 但是他开拓的 这一新领域至今仍十分活跃, 这一新领域至今仍十分活跃, 而且近年 来在科技领域获得了成功的应用. 来在科技领域获得了成功的应用. 本讲主要介绍鸽巢原理、Ramsey数及 本讲主要介绍鸽巢原理、Ramsey数及 性质、 Ramsey定理及应用 定理及应用. 性质、 Ramsey定理及应用.

组合数学

鸽巢原理定理1 若有n+1只鸽子飞回 个鸽巢, 定理1 若有n+1只鸽子飞回n个鸽巢,则至 只鸽子飞回n 少有两只鸽子飞入了同一个鸽巢. 少有两只鸽子飞入了同一个鸽巢. 这个原理的证明非常容易, 这个原理的证明非常容易, 只要使用 反证法马上就可以得到结论. 反证法马上就可以得到结论. 这个原理也可以表述为: 这个原理也可以表述为: 如果把n+1件东西放入 个盒子中, 件东西放入n 如果把n+1件东西放入n个盒子中, 则至少有一个盒子里面有不少于两件 的东西. 的东西.

组合数学

鸽巢原理不能用来寻找究竟是哪个盒 子含有两件或更多件东西. 子含有两件或更多件东西. 该原理只能证明某种安排或某种现象 存在,而并未指出怎样构造 构造这种安排或 存在,而并未指出怎样构造这种安排或 怎样寻找这种现象出现的场合. 怎样寻找这种现象出现的场合. 从鸽巢原理出发, 对于许多实际问题, 从鸽巢原理出发, 对于许多实际问题, 我们可以导出非常有趣的结果. 我们可以导出非常有趣的结果. 利用鸽巢原理解决实际问题的关键是 要看出这是一个鸽巢问题 建立“ 鸽

巢问题, 要看出这是一个鸽巢问题, 建立“鸽 寻找“鸽子” 巢”,寻找“鸽子”.

组合数学

例1. 如果有13个人其中必然有两个人出 如果有13个人其中必然有两个人出 生在同一个月. 生在同一个月. 如果鞋架上放10双鞋 从中任意取11 双鞋, 例2. 如果鞋架上放10双鞋, 从中任意取11 其中至少有两只恰好是配对的. 只, 其中至少有两只恰好是配对的. 从整数1,2,…,100中选 个数 中选51个数, 例3. 从整数1,2,…,100中选51个数, 证明 在所选的数中间必然存在两个整数, 在所选的数中间必然存在两个整数, 其 中之一可以被另一个整除. 中之一可以被另一个整除. 对于任何一个整数x 总可以把x 证明 对于任何一个整数x, 总可以把x写 形式, 其中a是奇数, 成x=2n a形式, 其中a是奇数, n≥0.

组合数学

1到100之间一共有50个奇数, 由所选的 100之间一共有 个奇数 之间一共有50个奇数, 51个数利用上述方式可以得到51个奇 51个数利用上述方式可以得到 个奇 个数利用上述方式可以得到51 其中必然有两个相同, 数, 其中必然有两个相同, 设这两个数 如果r 那么x 为: x=2ra, y=2sa, 如果r≤s, 那么x|y; 如 那么y|x 果r>s, 那么y|x. 本例中: 鸽子=去掉2因子得到的奇数; 本例中: 鸽子=去掉2因子得到的奇数; 鸽巢= 鸽巢=1到100之间奇数. 100之间奇数 之间奇数. 这个例子可以推广到从1,2,…,2n 这个例子可以推广到从1,2,…,2n中任 意取n+1个数 其中必然存在两个数, 个数, 意取n+1个数, 其中必然存在两个数, 其 中一个整除另外一个, 证法类似. 中一个整除另外一个, 证法类似.

组合数学

例4. 在一个边长为1的正三角形中任意取 在一个边长为1 5个点, 必然有两个点之间距离不超过1/2. 个点, 必然有两个点之间距离不超过1/2. 在边长为1的正六边形中, 任意选取7个点, 在边长为1的正六边形中, 任意选取7个点, 必然有两个点之间的距离不超过1. 必然有两个点之间的距离不超过1. 只要通过画图, 只要通过画图, 找出相应的鸽子和鸽巢 就可以解决问题. 就可以解决问题. 利用鸽巢原理解决问题的关键在于: 利用鸽巢原理解决问题的关键在于:

辨认问题, 建立鸽巢, 寻找鸽子. 辨认问题, 建立鸽巢, 寻找鸽子.

组合数学

例5、从1到2n的正整数中任取n+1个， 个数中至少有一对数， 则这n+1个数中至少有一对数，其中一 个数是另一个数的倍数( 个数是另一个数的倍数(n≥1) 。证明：设所取n+1个数是a1,a2,…,an,an+1, 证明： 的因子， 对该序列中的每一个数去掉一切2的因子，直至剩下一个奇 数为止， 数为止，即 ri = ai / 2x ,x = 0,1,2,…。 结果得由奇数组成的序列R:r1,r2,…,rn,rn+1。 1到2n中只有n个奇数，故序列R中至少有两个数是相同的。 个奇数， 中至少有两个数是相同的。 设为 ri

= rj = r , i ≠ j , α ai = 2α i r,a j = 2 j r,不妨设α i > α j , 对应的有 的倍数。 则ai是aj的倍数。

组合数学

是正整数的序列， 例 6 、 设 a1a2…am 是正整数的序列 ， 则至少存在整数 k 和 l , 1≤k<l≤m,使得和ak+1+ak+2+…+al是m的倍数。 (m≥2) 的倍数。 证明：构造一个序列 s1 = a1 , s2 = a1 + a2 , ..., sm = a1 + a2 + ... + am。 证明： 则 s1 < s2 < ... < sm 此时有两种可能： 此时有两种可能： 的倍数，则结论成立。 (1)若这m个和中有一个sh(1≤h≤m)是m 的倍数，则结论成立。 的倍数， (2)若这m个和中没有一个 是m 的倍数，则这些和被m除时必有 这样的余数。 1,2,…,m-1这样的余数。 个和， 个余数， 个盒子， 由于有m个和，且只有m-1个余数，于是我们可以构造m-1个盒子， 盒子” 的数， 第i个“盒子”是被m除余数为i的数，(i=1,2,…,m-1)。 由鸽笼原理知， 除各和时，至少有两个和的余数是相同的。 由鸽笼原理知，用m除各和时，至少有两个和的余数是相同的。 除有相同的余数， 则存在整数k和l (k<l) ,使得sk和sl 被m除有相同的余数， 即 sk≡sl mod m 。 故 sl sk = ak +1 + ak + 2 + ... + al ≡ 0mod m

组合数学

证明： 例7、证明：把5个顶点放到边长为2的正方 形中，至少存在两个顶点， 形中，至少存在两个顶点，它们之间的距离 小于或等于 。 2 证明： 证明：把边长为2的正方形分成四个全等的边长为1的小正方形， 则每个小正方形的对角线长为 2 。 如果把每个小正方形当作一个盒子，由鸽笼原理知， 如果把每个小正方形当作一个盒子，由鸽笼原理知，把5个顶点 放到4个盒子中，必有一个盒子中放入了两个顶点。 个盒子中，必有一个盒子中放入了两个顶点。 个顶点； 即必有一个小正方 …… 此处隐藏：3990字，全部文档内容请下载后查看。喜欢就下载吧 ……