毕业论文（设计）-鸽巢原理及其应用.doc

《毕业论文（设计）-鸽巢原理及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、鸽巢原理及其应用摘要如果n+1个物体被放进n个盒子，则必有一个盒子包含两个或者更多的物体，或者说把多于kn个东西任意放进n个空盒子（是正整数），那么一定每一个盒子中放进了至少k+1个东西，若问题的讨论对象是无限多个，则有把无限多个东西任一放进n个空盒子（n是自然数），那么一定有一个盒子中放进了无限多个东西。关键词鸽巢原理代数问题数论问题儿何问题—引言鸽巢原理又称抽屉原理或鞋盒原理，它由徳国数学家狄利克雷（Dirichlet）首先发现，因此又叫狄利克雷原理。它的概念是这样的：“如果有五个鸽子笼，养鸽人养了6只鸽子，那么当鸽子飞冋笼中后，

2、至少有一个笼子中装有2只鸽子”。抽屉原理是组合数学中--个垠基本的原理，是解决纽合论中一些存在性问题的基本而又有力的工具，它是纽•合数学瑕简讥也是瑕基本的原理，从这个显而易见的原理出发，可以导出许多并非显『U易见的有趣结果，而这些结果常制是令人惊奇的，在数学的学习研究中，我们也可以把它看作是一种重要的非常规解题方法，应用它能解决许多涉及存在性数学问题。特别是Ramsey理论产生了重要而深远的影响。二鸽巢原理定理一如果n+1个物体被放进n个盒子，则必有一个盒子包含两个或者更多的物体（山组合数学得到）第一种证明（反证法）如果每个盒子至多只

3、能放进一个物体，那么物体的总数至多是n，而不是题设的n+k（k21）这不可能第二种证明如果这n个盒子中的每一个都至多含有一个物体，那么物体的总数最多是n,既然我们有n+1个物体，于是某个盒子必然含有至少两个物体如果问题的讨论对象有无限多个，抽屉原理还有另一种表述“把无限多个东西任一放进n个空抽屉（n是自然数），那么一定有-•个抽屉中放进了无限多个东西”。定理二如果m个元素分为n个集合中，其中必有一个集合元素个数大于或等于[m/n]（山组合数学得到）证明设把m个元素分为n个集合A「A2,人3人"，用ara2,a3a“表示这n个集合里的元

4、素个数，需要证明至少存在某个a大于或等于[m/n]0反证法假设结论不成立即对每一个a/•都有ai<[m/n],于是有：a,+a2a“V[m/n]+[m/n]HF[m/n]=m/[m/n]Wm/（m/n）=m,1<个[m/n]所以a]+a2Ha

5、则至少有一个鸽巢里有不少于[]+1只鸽n定理五设有P]+P2HHP„—n+1只鸽了，贴上标号分别为1,2,…，n的鸽巢，则存在至少一个标号为i的鸽巢至少有P，只鸽子，i=1,2,…，n证明反证法，若第一•个鸽巢最多只有P

6、—1只鸽子，则第二个鸽巢最多只有P2~1只鸽子，…，第n个鸽巢最多不超过P“一1只鸽子，则鸽子的总数最多不过（P厂1）+（P2~1）+•••+（P“一1）=Pi+P2+…+P„-n定理六若序列aj,a2,a3，…a〃2的"2个元素是不相筹的实数，则从（S）中至少可选出一组山n各元素纽.成的或为单调递减或为单调递增的子

7、数列在证明定理以前，先举一个例子以说明定理的意思，对于序列5,3,16,10,15,14,9,11,6从中可以选出不相同的单调递增子序列，例如{5,16}；{5,10,15}；{3,9,11}；{3,6}；・・・也可以从中选出单调递减子序列{5,3}；{16,10,9,6}；{16,15,14,11}；-证明从序列（S）中的每一个元素a,向后可选出若干个单调递增子序列，其中有一个元素垠多的单调递增子序列，设其元素个数为1厂i=1,2,3,-n2于是得到一序列1I,12，…1“2若上述序列中有一个元素1n+1,则己符合定理要求，若不然，

8、设不存在元素个数超过n的单调子序列，即0W1jWn,i=1,2,•••,n2这相当于把n2个球放到口个盒子里，山于m=n22rm—r+1—1nL」=LJ=nnn根据鸽巢原理，存在n+1个1人，1他，…，1觴和1,0V1Wn，使得1伤=1灯=・・•1k”=1，不失一般性，不妨令k1Vk2<••••>*觴（A）因为如若不然,设k了Vk厂有ak_

9、增序列，这和1是a,的最长递增序列的假设矛盾但序列（A）本身是一个弔调递减子序列，这就证明了若不存在n个元索的单调递增子序列，便存在一个有n个元素的单调递减子序列（A）,同样的办法可证，若（S）不存在元素个数为n的单调递