抽屉原理的应用及其推广毕业论文.doc

1、数学与计算机科学学院毕业论文1抽屉原理的应用及其推广数学与计算机科学学院 数学与应用数学 指导老师： 王美能摘要：抽屉原理也叫鸽巢原理，是研究如何将元素分类的一个原理，也是组合数学里最简单、最基本的原理。本文简述了抽屉原理普遍使用的简单形式，重点介绍了抽屉原理在我们数学竞赛，通过由浅到深，由简单到复杂，循序渐进的了解抽屉原理。同时，通过对抽屉原理的学习，我们可以发现在我们日常生活中很多地方都有抽屉原理的应用。通过本文的介绍，相信大家对抽屉原理会有一个更为全面的认识。关键词：抽屉原理、狄利克雷原理、数学竞赛、拉姆塞定理Abstract：This paper describes the simpl

2、e form of the widespread use of drawer principle,focuses on the drawer principle in mathematics our primary school mathematics,advanced mathematics,form shallow to deep,form simple to complex,step by step to understand the principle of drawer.At the same time,the drawer principle of learning,we can

3、find applications in our daily life,there are a lot of places of drawer principle,such as computer divination,schedule,resource allocation and so on. Keywords: Drawer principle,de Lickley principle,Mathematics competition,Ramsrys theorem21 引言抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P.G.T.

4、Dirichlet 1805-1855)首先发现的，因此也叫作狄利克雷原理。抽屉原理简单易懂，主要用于证明某些存在性或至少类的问题，在生活中抽屉原理的应用非常广泛，解决了生活中一些模糊不清的问题，方便了人们的生活。本文归纳了抽屉原理在小学数学竞赛、中学数学竞赛中的一些简单应用，由浅入深将抽屉原理推广到更高的领域，并举例阐述了抽屉原理在现实生活中的应用。2 抽屉原理的定义第一抽屉原理原理 1：把多于 n个的物体放在 n个抽屉里，则至少有一个抽屉里的东西不少于两件。证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是 n，而不是题设的 ，故不可能。)(kn原理 2：把多于 （m

5、乘于 n）个的物体放到 n个抽屉里，则至少有一个抽屉里有不少于的物体。1m证明（反证法）：若每个抽屉至多放进 m个物体，那么 n个抽屉至多放进 个物体，与题设mn不符，故不可能。原理 3：把无穷多件物体放入 n个抽屉，则至少有一个抽屉里有无穷个物体。第二抽屉原理把 个物体放入 n个抽屉中，其中必有一个抽屉中至多有 个物体（例如，将）（ 1n ）（ 1个物体放入 5个抽屉中，则必定有一个抽屉中的物体数少于等于 ） 。4-5 2-3证明（反证法）：若每个抽屉都有不少于 m个物体，则总共至少有 个物体，与题设矛盾，mn故不可能。3 抽屉原理在数学竞赛以及实际生活中的应用数学竞赛是以开发智力为根本目的

6、、以问题解决为基本形式、以竞赛数学为主要内容。最本质的是对中学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、开发智力的素质教育、生动活泼的业余教育、现代数学的普及教育。数学竞赛与体育竞赛相类似，它是青少年的一种智力竞赛，所以苏联人首创了“数学奥林匹克“这个名词。在类似的以基础科学为竞赛内容的智力竞赛中，数学竞赛历史最悠久，参赛国最多，影响也最大。数学竞赛活动也是由浅入深逐步发展的。几乎每个国家的数学竞赛活动都是先由一些著名数学家出面提倡组织，试题的命题在背景的深刻度和构题的艺术性上也有较高的要求，较为突出的有四条：内容的科学性、结构的新颖性、功能的选拔性、解法的灵活性。数学竞

7、赛命题的基本途径主要有：高等初等化，历史名题的再生，成题改编，模型法。抽屉原理由于它自身的特点，简单并且思维方法在解题过程中可以演变出很多奇妙的变化和颇具匠心的运用，所以抽屉原理经常是命题人出题方向及思路。3.1 抽屉原理在小学数学竞赛中的应用其实在抽屉原理在小学数学中已经有雏形了，在人教版六年级下册中的“数学广角”中，就已经出现了一些抽屉原理的简单应用。当时就有很多教师反应教学存在一定的困难性，不仅如此，学生也普遍觉得难以理解，学习起来也很困难！在数学问题中，经常碰到有关“存在性”的问题。如某地区医院一月共接生 32名婴儿，那么一定存在两名婴儿，他们是在同一天出生的。在解决这类问题中，只需要

8、确定某个人（或某件物） ，也不需要严格说明通过什么方式把这个存在的人（或物）找出来。这就是我们小学初次接触的比较简单的“抽屉原理” ，即把多于 n个的物体放在 n个抽屉数学与计算机科学学院毕业论文3里，则至少有一个抽屉里的东西不少于两件。在教学过程中，教学者普遍认为在这类问题上很难向学生讲清其中的来龙去脉，所以在理解算法的基础上，采用“总有 至少 ”的语言叙述出来，以加固理解，采用这种教学方法，学生相对来说容易理解一些。下面我们将问题建立两类模型来解决：模型一 求至少的问题这类问题的特点是：已知“抽屉”的个数，求某个“抽屉”里至少能装多少的问题。例 1 在任意的 49个人中，至少有几个人的属相

9、相同？解：因为共有 12个生肖，将 12个生肖看成 12个“抽屉” ，问题就转换成寻求一个“抽屉”里至少能“装”多少人。我们可以先算出平均每个“抽屉” “装”多少个人： ，多4912 出来的 1个人总会随机的进入到某个“抽屉”中，所以总有一个抽屉里有四个人，也就是总有一种生肖属相里至少有 4个人。即：至少有 4个人的属相相同。例 2 平面上有六个点 A、B、C、D、E、F，其中不存在三个点在同一条直线上的情况，每两点之间都用红线或蓝线连接。试说明：不管如何连接，至少存在有一个三角形是三条边的颜色都相同。解：从六个点当中任取一点，设为 A，在用它连接其余五点的五条线段中，至少有 3条同色（把红、

10、蓝两色作为两个“抽屉” ， ） 。假设其中的 AB、AC、AD 为红色线521,3 段（如下图所示） 。这时，在三条线段 BC、BD、CD 中，若有一条为红色，则得到一个三边为红色的三角形；（如下图所示） AB CD若没有一条为红色，则 BC、BD、CD 都是蓝色，也得到一个三边都是的三角形BCD。 （如下图所示）ABCD4ABCD所以不管怎样连接，至少有一个三边同色的三角形。对于求至少性的这类问题，我们首先确定有多少个抽屉，然后可以把物体平均分给这几个抽屉，剩余的物体再平均分一次，最后就可以确定一个抽屉至少有几个物体。解这类问题的原理是把多于（m 乘于 n）个的物体放到 n个抽屉里，则至少有

11、一个抽屉里有不少于 的物体。1m模型二 作“最坏”的打算理论依据：把多于 n个的物体放在 n个抽屉里，则至少有一个抽屉里的东西不少于两件。即：一定有一个“抽屉”里至少有两个元素。例 3 有红、黄、绿三种颜色的手套各 6双，装在一个黑色的布袋里，从袋子里任意取出手套来，为确保至少有 2双手套不同颜色，则至少要取出的手套只数是？分析：“为确保至少有” ，考虑最坏的情况，首先取出了一种颜色的全部 6双手套和其他两种颜色的手套各一只，再任意取出一只，必然得到 2双不同颜色的手套。因此至少要取出只。2615例 4 有 120名职工投票从甲、乙、丙三人中选举一人为劳模，每人只能投一次，且只能选一个人，得票

12、最多的人当选。统计票数的过程发现，在前 81张票中，甲得 21票，乙得 25票，丙得35票。在余下的选票中，丙至少再得几张选票就一定能当选？分析：此题是问丙至少再得几张选票就一定能当选，由题干中可以看出共有三位候选人，甲得21票， 乙得 25票，丙得 35票，要使至少再得到几张选票丙一定能当选，那么还是首先应该考虑到，丙竞选中遇到的最不利的情况，丙遇到的最不利的情况其实就是来看，谁对丙当选的竞争最大，从开始的选票中，可以看到甲的选票比较少，对丙当选的威胁较小，可以排除；而乙得到的选票与丙是最接近的，对丙的当选最有威胁。120 名职工投票，已有的 81张票中，得票最少的是甲21张，只考虑乙丙即可

13、。 ，若丙最后当选，至少得 50张票，所以丙至少再得1209 503515 张票。综上所述，抽屉原理在小学数学中主要是上述两方面的应用，实质上就是抽屉原理的两种常用形式。在教学中，可以归类进行学习，建立两种模型，学生熟练掌握，进而能简单应用。为孩子后续学习和理解打下坚实的基础。3.2 抽屉原理在中学数学竞赛中的应用在小学数学中我们已经学习了“抽屉原理”的雏形，在初中数学中我们主要学习的是抽屉原理的基本形式和如何使用抽屉原理，并通过实例了解抽屉原理中的一些构造方法，以及抽屉原理在中学数学竞赛题中的应用。抽屉原理的基本形式：（1）把 个元素分为 n个集合，那么必有一个集合中含有两个或两个以上的元素

14、。n（2）把 个元素分成 n个集合，那么必有一组中含有 个或 个以上元素。m1m（3）把 n个元素分成 k个集合，那么必有一个集合中元素的个数 ，也必有一个集合中nk数学与计算机科学学院毕业论文5元素的个数 。nk（4）把 个元素分为 n个集合，那么必有一个 i ，在第 i个121nq (1)n集合中元素的个数 。i（5）把无穷多个元素分成为有限个集合，那么必有一个集合含有无穷多个元素。抽屉原理的基本构造：利用抽屉原理解题的过程中首先要注意指明什么是元素，什么是抽屉，元素进入抽屉的规则是什么，以及在同一个盒子中，所有元素具有的性质。构造抽屉是用抽屉原理解题的关键。有的题目运用一次抽屉原理就能解

15、决，有的则需要反复多次。下面我们通过一些具体的例题来介绍抽屉原理的应用：例 5 求证：从任意给定的 2010个自然数 ，中可以找到若干数，使得它们的和是1201,a2010的倍数。证明 以 ，即被 2010除的余数分类制造抽屉，将下列数：9 ,0，作为抽屉中的元素。S, 321232132121 aaSaS 201若上述 2010个数中有一个是 2010的倍数，则问题得证；否则，根据抽屉原理，至少存在两个数 （它们的差仍为 中若干数的和） ，nm, ,321201a它们被 2010除的余数相同，则它们的差是 ，即 中若干数的和能被 2010整除，S0a命题得证。此例是抽屉原理中常见的题型“存在

16、至少”性问题，解决此类问题的关键就是抽屉的中元素的选择。例 6 在边长为 1的正方形内任意放入九个点，求证：存在三个点，以这三个点为顶点的三角形的面积不超过 。（1963 年北京竞赛题） 8分析与解答：如图，四等分正方形，得到 A1，A 2，A 3，A 4四个矩形。在正方形内任意放入九个点，则至少有一个矩形 Ai内存6在 个或 3个以上的点，设三点为 A、B、C，具体考察 Ai（如图所示），过 A、B、C 三点914分别作矩形长边的平行线，过 A点的平行线交 BC于 A点，A 点到矩形长边的距离为，则ABC 的面积h(0)ABCAB111S+S2428hh说明：把正方形分成四个区域，可以得出“

17、至少有一个区域内有 3个点”的结论，这就为确定三角形面积的取值范围打下了基础。本题构造“抽屉”的办法不是唯一的，还可以将正方形等分成边长为 的四个小正方形等。但是如将正方形等分成四个全等的小三角形却是不可行的。所以适当12地构造“抽屉”，正是应用抽屉原则解决问题的关键所在。此例是通过分割图形构造抽屉，在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，在对其中需要用到的抽屉进行讨论，使问题得到解决。例 7 在 中任选出 20个数，其中至少有不同的两组数，其和都等于1,470,31104，试证明之。 （美国普特南）证明 给定的数共有 34个，其相

18、邻两数的差均为 3，我们把这些数分成如下 18个不想交的集合 1,524,07,9,45,并且把他们看做是 18个抽屉。从已知的 34个数中任选 20个数，即使把前两个抽屉中的数 1和 52都取出来，则剩下的 18个数在后面的 16个抽屉中至少有不同的两个抽屉中的数全被取出来，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是 104.此例是根据某两个数之和为 104来构造抽屉。一般的，与整数集有关的存在性问题也可以根据不同的需要利用整数间的倍数关系，同余关系来适当分组而构造抽屉。例 8 设实数 ，则其中必有两个数 ，满足0,1),2,ixin ,klx.1klxn证 把 分成 n个小区间：

19、,) 20,),1).它们两两不相交。现有 n+1个点 在 中，则至少有两点设为 和 属于同一1nx kxl数学与计算机科学学院毕业论文7小区间，从而有.1klxn在例 8中，如记 是任意的无理数，则 ，由例 8有,0,2,kx 01kx.（不妨设 kl）()()l如记 都是整数可得 .,aklblab1ban只要 n充分大，我们可用有理数比较精确的逼近一个无理数.抽屉原理还有其他表现形式：把 个元素任意分成 类，则至少有 类的元素个数一样多.(1)2kknk1逆向抽屉原则不难用反证法给予证明.如果至少有 k类的元素一样多，那么元素个数最少的方法是 k类 0个元素，k 类 1个元素，k类 2个

20、元素，k 类 个元素，这样最少需要 012(1)().knnk出现矛盾.以上证明方法对于证明元素个数多于抽屉个数的问题时有普遍意义.平均量重叠原则 把一个量 S任意分成 n份，则其中至少有一份不大于 ，也至少有一份不Sn少于 .Sn不等式重叠原则 若 ,且 ，则 至少有一个成立.,abcdRacbd,abcd面积重叠原则 在平面上有 n个面积分别是 的图形，把这 n个图形按任何方式12,nA一一搬到某一面积为 A的固定图形上去，（1）如果 ,则至少有两个图形有公共点；12n（2）如果 ，则固定图形中至少有一个点未被盖住.总而言之，抽屉原理的应用比较灵活，在竞赛辅导中教给学生一些简单的思想方法有

21、助于培养学生的构造的解题思想，可以使学生的思维能力得到一定的提升，不仅有助于现阶段的学习，也可以为将来的高等数学学习带来一定的帮助。3.3 总结应用抽屉原理解题的步骤在应用抽屉原理进行解题的过程中，我们把解题步骤分成三步：第一步：分析题意，分清什么是“东西”，什么是“抽屉”，也就是把什么看作“东西”，什么看作“抽屉”。8第二步：制造抽屉。这是关键，这一步就是如何设计抽屉，根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需的抽屉及其个数，为使用抽屉原理铺平道路。第三步：运用抽屉原理，观察题设条件，恰当应用各个原则或综合运用几个原则，以求问题之解决。在今后的学习中

22、，我们可以根据抽屉原理的这三步来解决问题，这样既可以节约我们的解题时间，也可以为我们解决这一类题型指明了一个方向。3.4 抽屉原理在生活中的应用抽屉原理不仅在小学数学、中学数学、高等数学中具有广泛应用，在我们的实际生活中，也能处处发现原理的影子。如电脑算命、赛程安排、资源分配等等，都不难看到抽屉原理的作用。在当今信息化、电子化的社会中，我们经常在网络世界中经常看到“电脑算命” 。所谓“电脑算命”不过是把人为编好的算命语句像中药柜那样事先分别一一存放在各自的柜子里，谁要算命，即根据出生年、月、日、性别的不同的组合按不同的编码机械地到电脑的各个“柜子”里，取出所谓命运的句子。其实这充其量不过是一种

23、电脑游戏而已。我们用数学上的抽屉原理很容易说明它的荒谬。如果以 70年计算，按出生年、月、日、性别的不同组合数应为 ，我们把51023670它作为“抽屉”数。由于 ，根据原理，存在 21526个以上的人，21405216. 亿尽管他们的出身、经历、天资、机遇各不相同，但他们却具有完全相同的“命” ，这真是荒谬绝伦！其实早在中国古代的春秋战国时期就有了运用抽屉原理的例子，那就是晏子春秋中的“二桃杀三士”的典故，将两个桃子赏赐给三名勇士，在这里可以将桃子看作抽屉，三个人作为元素放进抽屉，则根据抽屉原理，一定有一个抽屉要放入两个或两个以上的元素，回到问题情境中就是一定要有两个人吃一个桃子，导致这三名

24、勇士最后自相残杀而亡，这就是著名的“二桃杀三士” 。在实际生活中，运用抽屉原理的事情还有很多很多。比如我们在安排一场比赛时，该如何安排才能做到最公平。假设：你所在的年级有 5个班，每班一支球队在同一块场地上进行单循环赛, 共要进行 10 场比赛. 则各队每两场比赛中间至少隔多少场才最公平呢？下面是随便安排的一个赛程: 记 5支球队为 A, B, C, D, E，在下表左半部分的右上三角的 10个空格中, 随手填上 1,2,，10, 就得到一个赛程, 即第 1场 A对 B, 第 2场 B对 C, 第 10 场C对 E. 表的右半部分是各队每两场比赛间相隔的场次数, 显然这个赛程对 A, E有利,

25、 对 D则不公平.答案是 .21n证明因 ，所以分两种情况讨论. 时当 时当 12,2mn（1）当 为偶数时，这 支球队为 .顺次安排 场比赛需n02m1 ， ， ， ， （ ） 1（ ）要 支球队参赛，由抽屉原理，必然有重复出现的球队，由单循环赛知，重复出现的球队m（ ）中一定存在某球队.其两场比赛中间相隔的场次数最多为 .（2)当 为奇数时，这 支球队为 .顺次安排 场比赛需要2121, （ ）数学与计算机科学学院毕业论文9支球队参赛，由抽屉原理，必然有重复出现的球队，其两场比赛中间相隔的场次数最多2m1（ ）为 .因此，当 n支球队比赛时，若安排的赛程使各队每两场比赛中间至少相隔 场，则

26、该21n赛程称为完美赛程.抽屉原理的应用非常广泛，除了以上介绍的几个例子之外，在计算机，警方处理指纹或者是头发上也有一定的应用，由于涉及到一些专业问题，在此就不再详细介绍。4 抽屉原理的推广抽屉原理的内容简明朴素，易于接受，它在数学问题中有许多重要的作用。许多有关存在性的证明题都可以用抽屉原理来解决。1958年 6/7月号的美国数学月刊上有一道关于抽屉原理推广的应用题：“证明在任意 6个人的集会上，或者 3个人以前彼此认识，或者有三个人以前彼此不相识。 ”这个问题可以用如下方法简单明了地证出：这个问题看起来，似乎令人匪夷所思。但如果你懂得抽屉原理，要证明这个问题是十分简单的。我们用 A、B、C

27、、D、E、F 代表六个人，从中随便着一个，例如 A吧，把其余五个人放到“与 A认识”和“与 A不认识”两个“抽屉”里去，根据抽屉原理，至少有一个抽屉原理里有三个人。不妨假定在“与 A认识”的抽屉里有三个人，他们是 B、C、D。如果 B、C、D 三个互不认识，那么我们就找到了三个互不认识的人；如果 B、C、D 三人中有两个互相认识，例如 B与 C认识，那么A、B、C 就是三个互相认识的人。不管哪种情况，本题的结论都是成立的。由于这个试题的形式新颖，解法巧妙，很快在全世界广泛流传，使不少人知道了这一原理。 六个人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例，这个简单的问题的证明思想可用来

28、得出另外一些深入的结论。这些结论构成了组合数学中的重要内容拉姆塞定理。从六人集会问题的证明中，我们又一次看到了抽屉原理的应用。5 总结抽屉原理在我们小学、初中、高中课本上虽然没有明确的学习与定义，但是他的价值是非常高的。它虽然只是一个小原理，但是在数学竞赛中确是必不可少的，它的数学思想和技巧是我们值得深刻了解和探索的。在我们学习抽屉原理的过程中，我们会觉得他只有几个原则，只要记住就会解题。但是我们忽略他所蕴含的数学思想，只有掌握了这种思想和把握了这种解题技巧，那么我们的数学素养就会有所提高。所以学好抽屉原理对我们有很大的帮助，从上面可以看出抽屉原理的应用非常广泛，他可以解决许多抽象的问题，可以

29、方便我们的学习与生活。 6 谢辞本论文是在王美能老师的指导下完成的，在论文的写作过程中王老师表现出对学生极大地信任，多次不断的鼓励我，如此一定会在论文写作过程中受益匪浅。在论文指导过程中，王老师始终营造一种平等交流的学术氛围，在他的关心和支持下，我终于能顺利完成毕业论文设计，在此请允许我10向王老师表示衷心的感谢。当然还有许多其他的老师、同学，在我的的成长过程中提供了许多宝贵的意见和建议，使我总能在迷茫的时候找到一种“柳暗花明又一村”的感觉，在此，我对他们表示感谢。除此之外，我还要感谢和我一起奋斗的室友、同学。毕业之际，感谢有你们一路的陪伴，为论文，为毕业，为工作，感谢你们每一位对我的帮助，感

30、谢你们给我带来的快乐与感动。最后也让我在这特殊的时刻，感谢我的父母，没有他们辛勤的付出也就没有我的今天，在这一刻，让我将最崇高的敬意献给你们！本文参考了大量的文献资料，在此，请允许我向各学术界的前辈们致敬！他们严谨的治学态度值得刚毕业的我学习。论文写作是写作的过程，更是一次知识的大运用、大综合，感谢毕业论文写作给我带来的启迪。参考文献1陈景林,阎满富.组合数学与图论M.北京：中国铁道出版社,2000.042朱欢.抽屉原理在中学数学竞赛解题中的应用J.高等函授报，2010.123邓毅.浅谈抽屉原理在小学数学中的应用J.新课程小学.2013.54严士健.抽屉原则及其它的一些应用J.数学通报,1999.065陈传理，张同君.竞赛数学教程M.北京:高等教育出版社，2004.106呂松涛.抽屉原理在数学解题中的应用J.商丘职业技术学院学报，2012.27宁靓.初中奥林匹克数学解题与命题的思想方法和技巧J.广州大学学位论文,2006