组合数学论文抽屉原理及其应用

北京航空航天大学软件学院组合数学论文论文题目：抽屉原理及其应用姓名：学号：专业：集成电路与物联网工程BeihangCollegeofSoftware北航软件学院1目录摘要.......................................................................................................................................2Abstract...................................................................................................................................31.引言.......................................................................................................................................42.抽屉原理的形式...................................................................................................................43.抽屉原理的构造...................................................................................................................53.1分割图形构造抽屉....................................................................................................53.2利用划分数组来构造抽屉........................................................................................63.3利用划分集合来构造抽屉........................................................................................63.4利用等分区间构造抽屉............................................................................................73.5利用奇偶性分类构造抽屉........................................................................................83.6利用状态制构造抽屉................................................................................................84.抽屉原理的应用...................................................................................................................94.1抽屉原理在数学中的应用........................................................................................94.1.1解决代数问题........................................................................................................94.1.2解决数论问题......................................................................................................104.1.3解决几何问题......................................................................................................114.2抽屉原理在生活中的应用......................................................................................114.2.1手指纹和头发......................................................................................................114.2.2电脑算命..............................................................................................................124.2.3招生录取..............................................................................................................125.总结.....................................................................................................................................13参考文献.................................................................................................................................13BeihangCollegeofSoftware北航软件学院2摘要抽屉原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用。本文简单介绍了抽屉原理的几种形式，本文主要研究抽屉原理的抽屉构造和原理的应用。构造主要研究抽屉原理经常使用的几种构造方式：分割图形构造法，整数性质构造法（同余类构造法、划分数组构造法），间接转换构造法（染色体构造法）。应用主要从数学领域的应用和现实生活中的应用两大方面进行研究，数学领域方面主要应用于代数、数论、几何等几方面的解题，现实生活中大多数用于电脑算命，预测某些存在性的结果等等。关键词：抽屉原理；“抽屉”的构造；抽屉原理的应用BeihangCollegeofSoftware北航软件学院3AbstractDrawerprincipleisamathematicalcombinationofproblemoftheexistenceofoneofthebasicprinciplesofnonconventionalproblemsolvingmethod,isalsooneoftheimportanttypesinnumbertheoryandcombinatorics,hasawiderangeofapplications.Thispaperbrieflyintroducestheprincipleofdrawerinseveralforms,Thispapermainlystudiestheprincipleofdrawerdrawerstructureandtheapplicationoftheprinciple.Tectonicresearchdrawerprincipleoftenuseseveralconstructionmethods:segmentationgraphconstructionmethod,constructionmethodofintegerproperties(congruenceclassconstructionmethod,constructionmethodofdividingthearray),indirectconversionmethodofconstruction(chromosomeconstructionmethod).Applicationmainlyfromthemathematicalfieldofapplicationandtherealityoflifeintheapplicationofthetwomajoraspectsofresearch,mathematicalfieldsmainlyusedinnumbertheory,algebra,geometryandsoonseveralaspectsoftheproblemsolving,inreallife,mostusedcomputerfortune-telling,predictsomeexistenceresultsetc.Keywords：DrawerPrinciple；drawertectonicdrawer；principleapplicationBeihangCollegeofSoftware北航软件学院41.引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，抽屉原理是离散数学中的一个重要原理，它是由德国著名数学家狄利克雷(P.G.T.Dirichlet1805-1855)首先发现的，因此也叫作狄利克雷原理。抽屉原理简单易懂，主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法。本文将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用。2.抽屉原理的形式什么是抽屉原理？先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理.或者假定一群鸽子飞回巢中，如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来。抽屉原理简单直观，很容易理解。而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来。下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用。我们最常用的抽屉原理只是抽屉原理的简单形式，就是将n+1个元素或者更多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素。除了这种比较普遍的形式外，抽屉原理还经许多学者推广出其他的形式。陈景林、阎满富在他们编著的《组合数学与图论》一书中将抽屉原理抽象概括成以下三种形式[1]:原理1.把多于n个的元素按任一确定的方式分成n个集合，则一定有一个集合中含有两个或两个以上的元素。原理2.把m个元素任意放到n)(nm个集合里，则至少有一个集合里至少有k个元素，其中1mnmnkmnmn　　　,　　当能整除时,　　　,　　当不能整除时.　　BeihangCollegeofSoftware北航软件学院5原理3.把无穷个元素按任一确定的方式分成有限个集合，则至少有一个集合中仍含无穷个元素。卢开澄在《组合数学》（第三版）中将抽屉原理（书中称为鸽巢原理）又进行了推广[2]。鸽巢原理：设k和n都是任意正整数，若至少有kn+1只鸽子