鸽巢原理及其应用+6

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

1、学号：20115034032学年论文（本科）学院数学与信息科学学院专业信息与计算科学年级2011级姓名陈婷婷论文题目鸽巢原理及其应用指导教师沈明辉职称教授成绩2014年3月16日学年论文成绩评定表评语成绩：指导教师(签名):201年月日学院意见：____________________学院院长(签名):201年月日目录摘要1关键字1Abstract..1Keywords1前言21.鸽巢原理21.1鸽巢原理的简单形式21.2鸽巢原理的一般形式31.3鸽巢原理的加强形式32.鸽巢原理的相关推论43.鸽巢原理的应用63.1鸽巢原理应用于数的整除关系63.2鸽巢原理应用于实际生活7

2、参考文献9鸽巢原理及其应用姓名：陈婷婷学号：20115034032数学与信息科学学院信息与计算科学专业指导老师：沈明辉职称：教授摘要：鸽巢原理是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用.本文简单介绍了鸽巢原理的几种形式，便于了解鸽巢原理到底是什么东西.本文主要研究鸽巢原理和其原理的应用.应用主要从数学领域的应用和现实生活中的应用两大方面进行研究，数学领域方面主要应用于整除关系的证明等几方面的解题.关键字：鸽巢原理;组合数学;鸽巢原理的应用Pigeonholeprincipleandtheapplicationo

3、fthepigeonholeAbstract:Pigeonholeprincipleisamathematicalcombinationofproblemoftheexistenceofoneofthebasicprinciplesofnonconventionalproblemsolvingmethod,isalsooneoftheimportanttypesinnumbertheoryandcombinationhasawiderangeofapplications.ThispaperbrieflyintroducestheprincipleofPigeonholein

4、severalforms,easytounderstandwhatthePigeonholeprincipleis.ThispapermainlystudiestheprincipleofPigeonholeprincipleandtheapplicationoftheprinciple.Applicationmainlyfromthemathematicalfieldofapplicationandtherealityoflifeintheapplicationofthetwomajoraspectsofresearch,mathematicalfieldsmainlyu

5、sedinnumbertheory,algebra,geometryandsoonseveralaspectsoftheproblemsolving,inreallife,mostusedcomputerfortune-telling,predictsomeexistenceresultsetc..Keywords:Pigeonholeprinciple；Mathematicalcombination；Theapplicationoftheprinciple9前言：在组合数学中，证明某种排列或模式存在的一个应用最广泛的工具是鸽巢原理.这一原理也称狄利克雷抽屉原理或鞋盒原理.

6、它和容斥原理一样，是组合分析中的一个重要的原则.它可以用来解决组合分析中许多“存在性”问题，并且常常得到一些令人惊异的结果.下面我们主要研究鸽巢原理的基本形式及其扩展形式和应用.1.鸽巢原理1.1鸽巢原理的简单形式定理一如果把n+1个物体放入n个盒子中去，则至少有一个盒子放有两个或更多的物体.证明（反证法）假设n个盒子中的每个盒子里至多放入了一个物体，则放入n个盒子中的物体总数至多为n个，这与题设“共有n+1个物体”相矛盾，所以知道假设是错误的，从而证明了至少有一个盒子中放有两个或更多的物体.定理一仅能被用于证明一个排列或某种现象的存在性，不能对任何构造排列或寻找现象的例证

7、给出任何指示.例一在一次舞会上，来了来了来了n位舞伴，彼此认识的握手问候，证明：在无论什么情况下，这n位舞伴中至少有两个人握手的次数一样多.证有已知条件可知，这n位舞伴中，每个人握手的次数最少有0次，最多有n-1次，比如，如果有一位舞伴握手的次数是0次，那么其他舞伴握手的次数最多不能多于n-2次，即握手次数为0,1,2，...,n-2;如果有一位舞伴握手的次数是n-1次，那么其他舞伴握手次数最少不能少于1次，即握手次数为1,2，...,n-1.总之，这n位舞伴按照其握手次数归入相应的“抽屉”，则根据抽屉原理可知，至