抽屉原理论文

摘要抽屉原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用。本文简单介绍了抽屉原理的几种形式，便于了解抽屉原理到底是什么东西。本文主要研究抽屉原理的抽屉构造和原理的应用。构造主要研究抽屉原理经常使用的几种构造方式：分割图形构造法，整数性质构造法（同余类构造法、划分数组构造法），间接转换构造法（染色体构造法）。应用主要从数学领域的应用和现实生活中的应用两大方面进行研究，数学领域方面主要应用于数论，代数，几何等几方面的解题，现实生活中大多数用于电脑算命，预测某些存在性的结果等等。关键词：抽屉原理；“抽屉”的构造；抽屉原理的应用AbstractDrawerprincipleisamathematicalcombinationofproblemoftheexistenceofoneofthebasicprinciplesofnonconventionalproblemsolvingmethod,isalsooneoftheimportanttypesinnumbertheoryandcombinatorics,hasawiderangeofapplications.Thispaperbrieflyintroducestheprincipleofdrawerinseveralforms,easytounderstandthedrawerprincipleiswhat.Thispapermainlystudiestheprincipleofdrawerdrawerstructureandtheapplicationoftheprinciple.Tectonicresearchdrawerprincipleoftenuseseveralconstructionmethods:segmentationgraphconstructionmethod,constructionmethodofintegerproperties(congruenceclassconstructionmethod,constructionmethodofdividingthearray),indirectconversionmethodofconstruction(chromosomeconstructionmethod).Applicationmainlyfromthemathematicalfieldofapplicationandtherealityoflifeintheapplicationofthetwomajoraspectsofresearch,mathematicalfieldsmainlyusedinnumbertheory,algebra,geometryandsoonseveralaspectsoftheproblemsolving,inreallife,mostusedcomputerfortune-telling,predictsomeexistenceresultsetc..Keywords：DrawerPrinciple；drawertectonicdrawer；principleapplication目录1引言...............................................................12抽屉原理...............................................................12.1抽屉原理概述..........................................................12.1.1抽屉原理的几种常见形式..............................................12.1.2抽屉原理的其他特殊形式..............................................32.2抽屉原理的构造及其常用的几种构造方式..................................32.2.1利用分割图形的方法构造抽屉..........................................42.2.2利用整数性质来构造抽屉..............................................42.2.3利用间接转换的方法来构造抽屉........................................42.2.4利用对称性构造抽屉..................................................53抽屉原理的应用.........................................................73.1抽屉原理在数学领域的应用..............................................73.1.1应用于数论问题......................................................73.1.2应用于几何问题......................................................83.1.3应用于代数问题......................................................83.1.4应用于组合问题......................................错误!未定义书签。3.1.5应用于数学奥赛......................................错误!未定义书签。3.2抽屉原理在生活中的应用................................................94总结..............................................................10谢辞.................................................................11参考文献...............................................错误!未定义书签。1抽屉原理及其应用1引言抽屉原理是离散数学中的一个重要原理，在数论和组合论中有着广泛的应用，是处理存在性问题的一个重要方法。抽屉原理又叫个鸽笼原理，它由德国数学家狄利克雷（Dirichlet，1805-1859）首先发现，因此又叫作狄利克雷原理。抽屉原理是组合数学中一个最基本的原理，在组合数学的发展中起到了至关重要的作用。狄利克雷在研究数论的问题时最早很巧妙的运用抽屉原理去解决问题。后来德国数学家闵可夫斯基（Minkowski，1864-1909）也运用这一原理得到一些结果。到了20世纪初期杜尔（AThue，1863-1922）在不知道狄利克雷和闵夫斯基的工作情况下，很机巧的利用鸽笼原理来解决不定方程的有理数解的问题，有12篇论文用到这个原理。后来西根（C.L.Siegel，1896-？）利用杜尔的结果发现了现在称为西根引理的东西，这个引理是研究超越数时最基本的必要工具。在数学的学习研究中，我们可以把抽屉原理看作是一种重要的非常规的解题方法，应用它能解决许多涉及存在性的数学问题。2抽屉原理2.1抽屉原理概述抽屉原理有时也被称为“鸽巢原理”，“邮箱原理”，“重叠原则”，“狄利克雷原理”等等，它是组合数学中一个重要的原理。2.1.1抽屉原理的几种常见形式(1)把5个苹果放到4个抽屉中，必然有一个抽屉中至少有2个苹果，这是抽屉原理的通俗解释。若有10个苹果，而只有9个抽屉，则必然有一个抽屉中至少有2个苹果，依次类推，我们可得到抽屉原理的另一种较规范的形式，即：若把1n+个苹果放到n个抽屉中，必然有一个抽屉中至少有2个苹果。我们用简单的数学语言可以把上述原理描述为：将1n+个物品放入n个盒子中，则至少有一个盒子中装的物品数不少于2个，即必存在一个盒子中装有至少两个或更多的2物品。（2）若将n个盒子看作是有限集合A的n个子集，1n+看作是集合A的元素个数，则我们可以把上述原理描述为以下形式：设A是有限集，niAAnAi,...,2,1,1且1niiA==A，则必有正整数nkk1，使得2kA。（3）由以上的原理我们又可以把抽屉原理描述为下面这个形式：若把1kn+个苹果放入n个盒子里，则必有一个盒子中至少有1k+个苹果。即：○1若将11rn个物品放入n个盒子中，则至少有一个盒子中至少有r个物品。○2设nmmm,...,,21是n个整数，而且1...21rnmmmn，则nmmm,...,,21中至少有一个数不小于r。即：设A是有限集，niAArnAi,...,2,1,11且1niiA==A，则必有正整数nkk1，使得rAk。（4）假如，有m个苹果，把它们放入n个抽屉里面，则必有一个抽屉里至少有11nm个苹果。证明：反证法，如果一个抽屉里面至多放nm1个苹果，则n个抽屉里面的苹果数不超过11mnmn与已知的m个苹果矛盾。即必有一个抽屉里面至少有11nm个苹果。若把m看作是有限集合A的元素个数，n看作是集合A的n个子集，则我们又可以把上述原理表示为：设A是2mm元集，niAAi,...,2,1且=1=niiAA，则必有正整数nkk1，使得11nmAk3（5）假设有1...21nqqqn个苹果，有标号为n,...,3,2,1的抽屉，则存在至少一个标号为j的抽屉里面至少有jp个苹果，nj,...,3,2,1证明：反证法，假如第一个抽屉里面最多只有11p个苹果，第二个抽屉里面最多只有12p个苹果，…，第n个抽屉最多只有1np个苹果，则n个抽屉里面的苹果总数不超过nqqqqqqnn...1...112121与原假设1...21nqqqn个苹果矛盾。即上述原理成立。即：设A是有限集nqqq,...,,21都是正整数。如果niAAnqqqAin,...,2,1,1...21且1niiA==A，则必有正整数nkk1，使得kkqA.2.1.2抽屉原理的其他特殊形式1、抽屉原理还有一种特殊的表现形式，那就是逆向抽屉原理：把121nnk个苹果任意放入kn个抽屉里面，则至少有1k个抽屉里面的苹果数一样多。即：把121nnk个元素任意分成kn类，则至少有1k类元素的个数一样多。证明：反证法，假设如果至多有k类的元素一样多，那么元素个数最少的放法是k类放0个元素，k类放1个元素，k类放2个元素，…，k类放1n-个元素，这样最少需要121211...210nknnknnk与已知出现矛盾。抽屉原理的形式比较多变，在具体的应用中也会有不同的变化，但本质上都是一样的。上述抽屉原理的证明均采用反证法，这种证明方法对于证明元素个数多于抽屉个数的问题时具有普遍意义。2.2“抽屉”的构造通过了解抽屉原理的形式，我们可以利用它的特殊形式来解决不同的问题。首先，必须明确题目中应该以什么为抽屉，什么为物品；其次，构造合适的抽屉，需要注意的4是抽屉的数量一定要少于物品的数量。最后，运用抽屉原理解决问题。其中，最重要最有难度的就是如何构造抽屉，构造抽屉是运用抽屉原理解题的关键，下面介绍几种常用的构造抽屉的方法。2.2.1利用映射的概念构造抽屉2.2.2利用奇偶分类构造抽屉2.2.3利用分割概念构造抽屉1、利用剖分图形来构造抽屉本方法主要用于解决点在几何图形中的位置分布和性质问题,