鸽巢原理及其应用.ppt

鸽巢原理及其应用.ppt

ID:48148481

大小:482.50 KB

页数:28页

时间:2020-01-17

鸽巢原理及其应用.ppt_第1页
鸽巢原理及其应用.ppt_第2页
鸽巢原理及其应用.ppt_第3页
鸽巢原理及其应用.ppt_第4页
鸽巢原理及其应用.ppt_第5页
资源描述:

《鸽巢原理及其应用.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、鸽巢原理及其应用陈淑贞2011.11.22主要内容1.引言2.鸽巢原理3.鸽巢的构造及其应用4.鸽巢原理在国内外数学竞赛中的应用5.鸽巢原理的推广——Ramsey定理(介绍)1.引言鸽巢原理为组合学中的一个重要原理。鸽巢原理最早是由19世纪的德国数学家迪里赫莱(Dirichlet)运用于解决数学问题而提出来的,所以又称为“迪里赫莱原理”,也有称“抽屉原理”的。应用它可以解决许多有趣的问题,并且常常得到一些令人惊异的结果。它常被用来证明一些存在性的数学问题,并且在数论和密码学中也有着广泛的应用。对于一些比较特

2、殊的问题,若用一般的数学方法去研究,很复杂或根本解决不了,但用鸽巢原理往往能起到事半功倍的效果,所以鸽巢原理也是国际国内数学竞赛中的重要内容,在数学竞赛中具有很大的应用意义。2.鸽巢原理2.1鸽巢原理的简单形式若有n+1只鸽子飞到n个鸽巢里面,则至少有一个鸽巢里至少有两只鸽子。2.2鸽巢原理的加强形式注:n+1为结论成立的最小数。将q1+q2+…+qn-n+1个物品放入n个抽屉中,则至少存在某个抽屉i(1≤i≤n),使得这个抽屉里至少有qi个物品。注:q1+q2+…+qn-n+1为结论成立的最小数,记为N(

3、q1,q2,…,qn;1)。显然,当q1=q2=…=qn=2时,加强形式即为简单形式。即N(q1,q2,…,qn;1)=q1+q2+…+qn-n+1.推论1n·(r-1)+1只鸽子飞入n个巢里,则至少有一个鸽巢里至少有r只鸽子。当qi=r时,得:推论3:设m1,m2,…mn均为正整数,且满足,则m1,m2,…,mn中至少有一个数不小于r。推论2:m只鸽子飞入n个巢里,则至少有一个鸽巢里至少有只鸽子,其中是不小于的最小整数。3鸽巢的构造及其应用虽然鸽巢原理十分简单明了,但不是所有的问题都一眼就可以看出什么是鸽

4、子,什么是鸽巢。在应用它的时候却涉及很多技巧,这是利用鸽巢原理解题的魅力所在。常用的构造鸽巢的方法有:利用整数分组、余数分类,划分集合,分割区间、分割图形,利用染色等。下面给出几类常用的构造鸽巢的方法。3.1利用整数分组构造“鸽巢”例1试证明从{1,2,…,kn}中选n+1个数,总存在2个数,它们之间最多相差k-1。证明:把{1,2,…,kn}分为n部分{1,2,3,…,k},{k+1,k+2,…,2k},…,{(n-1)k+1,(n-1)k+2,…,kn},即做n个鸽巢,从中任选n+1个数,由鸽巢原理,必

5、有2个数选在同一个鸽巢中,所以它们的差最大为k-1。路易·波萨是匈牙利数学家,在他11岁时匈牙利大数学家厄杜斯给他出了个问题:“如果你手头上有n+1个整数,这些整数是小于或等于2n的,那么你一定会有一对数是互素的。你知道这是什么原因吗?”波萨仅思考了半分钟就巧妙地回答了这个问题。例2在一条笔直的马路上种树,从起点起,每隔1米种一棵数。如果把三块“爱护树木”的小牌分别挂在三棵树上,那么不管怎么挂,至少有两棵挂牌的树它们之间的距离是偶数(以米为单位)。解从起点开始给每课树编号,树上的号码依次为1,2,3,…,n

6、,把这些号码分为奇数和偶数两类,当作两个鸽巢,把三块牌分别挂在三棵树上,那么不管怎么挂,这三棵挂牌的树至少有两棵树的号码同为奇数或偶数,而这两棵树的差必为偶数,所以至少有两棵挂牌的树它们之间的距离是偶数(以米为单位)。3.2利用划分图形构造“鸽巢”例1边长为1的正方形中,任意放入9个点,求证这9个点中任取3个点组成的三角形中,至少有一个的面积不超过.解:将边长为1的正方形等分成边长为1/2的四个小正方形,视这四个正方形为鸽巢,9个点任意放入这四个正方形中,由鸽巢原理必有三点落入同一个正方形内.现特别取出这个

7、正方形来加以讨论.图1把落在这个正方形中的三点记为D、E、F.如图1,通过这三点中的任意一点(如E)作正方形边平行线S△DEF=S△DEG+S△EFG所以,结论成立。如果8个点无一个在圆心上,可将圆分成7个相等的扇形,由鸽巢原理,这8个点至少有两个在同一个扇形内,则这两点之间的距离小于半径。例2在圆内(包刮圆周)有8个点,则其中必有两个点,它们之间的距离小于圆的半径。证明分两种情况考虑。A1A2A3A4A6A5o2.如果8个点有一个点在圆心,可将圆分成6个相等的扇形,如图,取扇形OA1A2不包含OA2,扇形

8、OA2A3不包含OA3,…,扇形OA6A1不包含OA1,由鸽巢原理,余下的7个点至少有两个在在同一个扇形内,则这两点之间的距离小于半径。由于圆上相邻两点Ai,Aj间的弦长恰好为圆的半径,所以在边长为1的正方形内任取5个点,则其中至少有两点,它们之间的距离不超过2.证明:(1)在一边长为1的三角形中任取10个点,则其中至少有两点,它们之间的距离不超过1/3.(2)确定mn,使得在一边长为1的三角形中任取mn个点,则

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。