组合数学讲义.ppt

1、 组合数学组合数学 第八讲第八讲鸽巢原理鸽巢原理 Ramsey数数djwang 王殿军王殿军2003.11.12.1第八讲第八讲 : 内容提要内容提要III. 一般形式的鸽巢原理一般形式的鸽巢原理IV. Ramsey 数数V*. Ramsey 定理定理 II. 鸽巢原理鸽巢原理 I. 本讲引言本讲引言 VI*. Ramsey 数的应用数的应用 2I. 本讲引言本讲引言l鸽巢原理又称抽屉原理或鞋盒原理鸽巢原理又称抽屉原理或鞋盒原理 , 这个原理最早是由这个原理最早是由 Dirichlet提出的提出的 . l鸽巢原理是解决组合论中一些鸽巢原理是解决组合论中一些 存在性存在性问题的基本而又有力的工具

2、问题的基本而又有力的工具 . 它是组它是组合数学中最简单也是最基本的原理之合数学中最简单也是最基本的原理之一一 , 从这个原理出发从这个原理出发 , 可以导出许多有可以导出许多有趣结果趣结果 ,而这些结果常常是令人惊奇的而这些结果常常是令人惊奇的.lRamsey理论它对组合数学发展产生理论它对组合数学发展产生过重要的影响过重要的影响 . 3l1928年年 , 年仅年仅 24岁的英国杰出数学家岁的英国杰出数学家Ramsey发表了著名论文发表了著名论文 论形式逻论形式逻辑中的一个问题辑中的一个问题 , 他在这篇论文中他在这篇论文中 , 提出并证明了关于集合论的一个重大提出并证明了关于集合论的一个重

3、大研究成果研究成果 , 现称为现称为 Ramsey定理定理 .l尽管两年后他不幸去世尽管两年后他不幸去世 , 但是他开拓但是他开拓的这一新领域至今仍十分活跃的这一新领域至今仍十分活跃 , 而且而且近年来在科技领域获得了成功的应用近年来在科技领域获得了成功的应用 .l本讲主要介绍鸽巢原理、本讲主要介绍鸽巢原理、 Ramsey数数及性质、及性质、 Ramsey定理及应用定理及应用 .4II. 鸽巢原理鸽巢原理定理定理 1 若有若有 n+1只鸽子飞回只鸽子飞回 n个鸽巢个鸽巢 ,则则至少有两只鸽子飞入了同一个鸽巢至少有两只鸽子飞入了同一个鸽巢 .l这个原理的证明非常容易这个原理的证明非常容易 , 只

4、要使用只要使用反证法马上就可以得到结论反证法马上就可以得到结论 . l这个原理也可以表述为这个原理也可以表述为 : 如果把如果把 n+1件东西放入件东西放入 n个盒子中个盒子中 , 则至少有一个盒子里面有不少于两则至少有一个盒子里面有不少于两件的东西件的东西 . 5l鸽巢原理不能用来寻找究竟是哪个鸽巢原理不能用来寻找究竟是哪个盒子含有两件或更多件东西盒子含有两件或更多件东西 .l该原理只能证明某种安排或某种现该原理只能证明某种安排或某种现象象 存在存在 ,而并未指出怎样而并未指出怎样 构造构造 这种安这种安排或怎样寻找这种现象出现的场合排或怎样寻找这种现象出现的场合 .l从鸽巢原理出发从鸽巢原

5、理出发 , 对于许多实际问题对于许多实际问题 , 我们可以导出非常有趣的结果我们可以导出非常有趣的结果 . l利用鸽巢原理解决实际问题的关键利用鸽巢原理解决实际问题的关键是要看出这是一个是要看出这是一个 鸽巢问题鸽巢问题 , 建立建立 “鸽巢鸽巢 ”，寻找，寻找 “鸽子鸽子 ”. 6例例 1. 如果有如果有 13个人其中必然有两个人出个人其中必然有两个人出生在同一个月生在同一个月 .例例 2. 如果鞋架上放如果鞋架上放 10双鞋双鞋 , 从中任意取从中任意取11只只 , 其中至少有两只恰好是配对的其中至少有两只恰好是配对的 .例例 3. 从整数从整数 1,2,100 中人选中人选 51个数个数

6、 , 证证明在所选的数中间必然存在两个整数明在所选的数中间必然存在两个整数 , 其中之一可以被另一个整除其中之一可以被另一个整除 .证明证明 对于任何一个整数对于任何一个整数 x, 总可以把总可以把 x写写成成 x=2na形式形式 , 其中其中 a是奇数是奇数 , n0. 7l1到到 100之间一共有之间一共有 50个奇数个奇数 , 由所选由所选的的 51个数利用上述方式可以得到个数利用上述方式可以得到 51个个奇数奇数 , 其中必然有两个相同其中必然有两个相同 , 设这两个设这两个数为数为 : x=2ra, y=2sa, 如果如果 rs, 那么那么 x|y; 如果如果 rs, 那么那么 y|

7、x. l本例中本例中 : 鸽子鸽子 =去掉去掉 2因子得到的奇数因子得到的奇数 ; 鸽巢鸽巢 =1到到 100之间奇数之间奇数 .l这个例子可以推广到从这个例子可以推广到从 1,2,2 n中任中任意取意取 n+1个数个数 , 其中必然存在两个数其中必然存在两个数 , 其中一个整除另外一个其中一个整除另外一个 , 证法类似证法类似 .8例例 4. 在一个边长为在一个边长为 1的正三角形中任意的正三角形中任意取取5个点个点 , 必然有两个点之间距离不超过必然有两个点之间距离不超过1/2. 在边长为在边长为 1的正六边形中的正六边形中 , 任意选取任意选取 7个个点点 , 必然有两个点之间的距离不超

8、过必然有两个点之间的距离不超过 1.l只要通过画图只要通过画图 , 找出相应的鸽子和鸽找出相应的鸽子和鸽巢巢就可以解决问题就可以解决问题 .l利用鸽巢原理解决问题的关键在于利用鸽巢原理解决问题的关键在于 : 辨认问题辨认问题 , 建立鸽巢建立鸽巢 , 寻找鸽子寻找鸽子 .9III.一般形式鸽巢原理一般形式鸽巢原理定理定理 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,这比假定的鸽子数少了一个这比假定的鸽子数少了一个 , 矛盾矛盾 . 10