抽屉原理的应用及其推广优秀毕业论文

数学与计算机科学学院毕业论文1抽屉原理的应用及其推广数学与计算机科学学院数学与应用数学指导老师：王美能摘要：抽屉原理也叫鸽巢原理，是研究如何将元素分类的一个原理，也是组合数学里最简单、最基本的原理。本文简述了抽屉原理普遍使用的简单形式，重点介绍了抽屉原理在我们数学竞赛，通过由浅到深，由简单到复杂，循序渐进的了解抽屉原理。同时，通过对抽屉原理的学习，我们可以发现在我们日常生活中很多地方都有抽屉原理的应用。通过本文的介绍，相信大家对抽屉原理会有一个更为全面的认识。关键词：抽屉原理、狄利克雷原理、数学竞赛、拉姆塞定理Abstract：Thispaperdescribesthesimpleformofthewidespreaduseofdrawerprinciple,focusesonthedrawerprincipleinmathematicsourprimaryschoolmathematics,advancedmathematics,formshallowtodeep,formsimpletocomplex,stepbysteptounderstandtheprincipleofdrawer.Atthesametime,thedrawerprincipleoflearning,wecanfindapplicationsinourdailylife,therearealotofplacesofdrawerprinciple,suchascomputerdivination,schedule,resourceallocationandsoon.Keywords:Drawerprinciple,deLickleyprinciple,Mathematicscompetition,Ramsry’stheorem21引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P.G.T.Dirichlet1805-1855)首先发现的，因此也叫作狄利克雷原理。抽屉原理简单易懂，主要用于证明某些存在性或至少类的问题，在生活中抽屉原理的应用非常广泛，解决了生活中一些模糊不清的问题，方便了人们的生活。本文归纳了抽屉原理在小学数学竞赛、中学数学竞赛中的一些简单应用，由浅入深将抽屉原理推广到更高的领域，并举例阐述了抽屉原理在现实生活中的应用。2抽屉原理的定义第一抽屉原理原理1：把多于n个的物体放在n个抽屉里，则至少有一个抽屉里的东西不少于两件。证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的)1≥(kkn，故不可能。原理2：把多于mn（m乘于n）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于1m的物体。证明（反证法）：若每个抽屉至多放进m个物体，那么n个抽屉至多放进mn个物体，与题设不符，故不可能。原理3：把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体。第二抽屉原理把）（1mn个物体放入n个抽屉中，其中必有一个抽屉中至多有）（1m个物体（例如，将141-5×3个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于21-3）。证明（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。3抽屉原理在数学竞赛以及实际生活中的应用数学竞赛是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容。最本质的是对中学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、开发智力的素质教育、生动活泼的业余教育、现代数学的普及教育。数学竞赛与体育竞赛相类似，它是青少年的一种智力竞赛，所以苏联人首创了数学奥林匹克这个名词。在类似的以基础科学为竞赛内容的智力竞赛中，数学竞赛历史最悠久，参赛国最多，影响也最大。数学竞赛活动也是由浅入深逐步发展的。几乎每个国家的数学竞赛活动都是先由一些著名数学家出面提倡组织，试题的命题在背景的深刻度和构题的艺术性上也有较高的要求，较为突出的有四条：内容的科学性、结构的新颖性、功能的选拔性、解法的灵活性。数学竞赛命题的基本途径主要有：高等初等化，历史名题的再生，成题改编，模型法。抽屉原理由于它自身的特点，简单并且思维方法在解题过程中可以演变出很多奇妙的变化和颇具匠心的运用，所以抽屉原理经常是命题人出题方向及思路。3.1抽屉原理在小学数学竞赛中的应用其实在抽屉原理在小学数学中已经有雏形了，在人教版六年级下册中的“数学广角”中，就已经出现了一些抽屉原理的简单应用。当时就有很多教师反应教学存在一定的困难性，不仅如此，学生也普遍觉得难以理解，学习起来也很困难！在数学问题中，经常碰到有关“存在性”的问题。如某地区医院一月共接生32名婴儿，那么一定存在两名婴儿，他们是在同一天出生的。在解决这类问题中，只需要确定某个人（或某件物），也不需要严格说明通过什么方式把这个存在的人（或物）找出来。这就是我们小学初次接触的比较简单的“抽屉原理”，即把多于n个的物体放在n个抽屉里，则至少有一个抽屉里的东西不少于两件。在教学过程中，教学者普遍认为在这类问题上很难向学生数学与计算机科学学院毕业论文3讲清其中的来龙去脉，所以在理解算法的基础上，采用“总有……至少……”的语言叙述出来，以加固理解，采用这种教学方法，学生相对来说容易理解一些。下面我们将问题建立两类模型来解决：模型一求至少的问题这类问题的特点是：已知“抽屉”的个数，求某个“抽屉”里至少能装多少的问题。例1在任意的49个人中，至少有几个人的属相相同？解：因为共有12个生肖，将12个生肖看成12个“抽屉”，问题就转换成寻求一个“抽屉”里至少能“装”多少人。我们可以先算出平均每个“抽屉”“装”多少个人：491241，多出来的1个人总会随机的进入到某个“抽屉”中，所以总有一个抽屉里有四个人，也就是总有一种生肖属相里至少有4个人。即：至少有4个人的属相相同。例2平面上有六个点A、B、C、D、E、F，其中不存在三个点在同一条直线上的情况，每两点之间都用红线或蓝线连接。试说明：不管如何连接，至少存在有一个三角形是三条边的颜色都相同。解：从六个点当中任取一点，设为A，在用它连接其余五点的五条线段中，至少有3条同色（把红、蓝两色作为两个“抽屉”，5221,213）。假设其中的AB、AC、AD为红色线段（如下图所示）。这时，在三条线段BC、BD、CD中，若有一条为红色，则得到一个三边为红色的三角形；（如下图所示）ABCD若没有一条为红色，则BC、BD、CD都是蓝色，也得到一个三边都是的三角形⊿BCD。（如下图所示）ABCD所以不管怎样连接，至少有一个三边同色的三角形。ABCD4对于求至少性的这类问题，我们首先确定有多少个抽屉，然后可以把物体平均分给这几个抽屉，剩余的物体再平均分一次，最后就可以确定一个抽屉至少有几个物体。解这类问题的原理是把多于mn（m乘于n）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于1m的物体。模型二作“最坏”的打算理论依据：把多于n个的物体放在n个抽屉里，则至少有一个抽屉里的东西不少于两件。即：一定有一个“抽屉”里至少有两个元素。例3有红、黄、绿三种颜色的手套各6双，装在一个黑色的布袋里，从袋子里任意取出手套来，为确保至少有2双手套不同颜色，则至少要取出的手套只数是？分析：“为确保至少有”，考虑最坏的情况，首先取出了一种颜色的全部6双手套和其他两种颜色的手套各一只，再任意取出一只，必然得到2双不同颜色的手套。因此至少要取出262115只。例4有120名职工投票从甲、乙、丙三人中选举一人为劳模，每人只能投一次，且只能选一个人，得票最多的人当选。统计票数的过程发现，在前81张票中，甲得21票，乙得25票，丙得35票。在余下的选票中，丙至少再得几张选票就一定能当选？分析：此题是问丙至少再得几张选票就一定能当选，由题干中可以看出共有三位候选人，甲得21票，乙得25票，丙得35票，要使至少再得到几张选票丙一定能当选，那么还是首先应该考虑到，丙竞选中遇到的最不利的情况，丙遇到的最不利的情况其实就是来看，谁对丙当选的竞争最大，从开始的选票中，可以看到甲的选票比较少，对丙当选的威胁较小，可以排除；而乙得到的选票与丙是最接近的，对丙的当选最有威胁。120名职工投票，已有的81张票中，得票最少的是甲21张，只考虑乙丙即可。1202199－＝，若丙最后当选，至少得50张票，所以丙至少再得50－35＝15张票。综上所述，抽屉原理在小学数学中主要是上述两方面的应用，实质上就是抽屉原理的两种常用形式。在教学中，可以归类进行学习，建立两种模型，学生熟练掌握，进而能简单应用。为孩子后续学习和理解打下坚实的基础。3.2抽屉原理在中学数学竞赛中的应用在小学数学中我们已经学习了“抽屉原理”的雏形，在初中数学中我们主要学习的是抽屉原理的基本形式和如何使用抽屉原理，并通过实例了解抽屉原理中的一些构造方法，以及抽屉原理在中学数学竞赛题中的应用。抽屉原理的基本形式：（1）把1n个元素分为n个集合，那么必有一个集合中含有两个或两个以上的元素。（2）把1nm个元素分成n个集合，那么必有一组中含有1m个或1m个以上元素。（3）把n个元素分成k个集合，那么必有一个集合中元素的个数nk，也必有一个集合中元素的个数nk。（4）把121nqqqn个元素分为n个集合，那么必有一个i(1)in，在第i个集合中元素的个数iq。（5）把无穷多个元素分成为有限个集合，那么必有一个集合含有无穷多个元素。抽屉原理的基本构造：数学与计算机科学学院毕业论文5利用抽屉原理解题的过程中首先要注意指明什么是元素，什么是抽屉，元素进入抽屉的规则是什么，以及在同一个盒子中，所有元素具有的性质。构造抽屉是用抽屉原理解题的关键。有的题目运用一次抽屉原理就能解决，有的则需要反复多次。下面我们通过一些具体的例题来介绍抽屉原理的应用：例5求证：从任意给定的2010个自然数122010,aaa，中可以找到若干数，使得它们的和是2010的倍数。证明以2009…1,0，，，即被2010除的余数分类制造抽屉，将下列数：…S,…,,,3212010321321211aaaaaaSaaSaS2010a作为抽屉中的元素。若上述2010个数中有一个是2010的倍数，则问题得证；否则，根据抽屉原理，至少存在两个数nmSS,（它们的差仍为,…,,,321aaa2010a中若干数的和），它们被2010除的余数相同，则它们的差是nmSS，即201021,,,aaa中若干数的和能被2010整除，命题得证。此例是抽屉原理中常见的题型“存在至少”性问题，解决此类问题的关键就是抽屉的中元素的选择。例6在边长为1的正方形内任意放入九个点，求证：存在三个点，以这三个点为顶点的三角形的面积不超过18。（1963年北京竞赛题）分析与解答：如图，四等分正方形，得到A1，A2，A3，A4四个矩形。在正方形内任意放入九个点，则至少有一个矩形Ai内存在9134个或3个以上的点，设三点为A、B、C，具体考察Ai（如图所示），过A、B、C三点分别作矩形长边的平行线，过A点的平行线交BC于A'点，A点到矩形长边的距离为1h(0h)4，则△ABC的面积ABCAACAAB111111SS+S11224248hh说明：把正方形分成四个区域，可以得出“至少有一个区域内有3个点”的结论，这就为确定三角形面积的取值范围打下了基础。本题构造“抽屉”的办法不是唯一的，还可以将正方形等分成6边长为12的四个小正方形等。但是如将正方形等分成四个全等的小三角形却是不可行的。所以适当地构造“抽屉”，正是应用抽屉原则解决问题的关键所在。此例是通过分割图形构造抽屉，在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，在对其中需要用到的抽屉进行讨论，使问题得到解决。例7在1,4,7,1