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

数学与计算机科学学院毕业论文

抽屉原理的应用及其推广

数学与计算机科学学院 数学与应用数学

指导老师： 王美能

摘要：抽屉原理也叫鸽巢原理，是研究如何将元素分类的一个原理，也是组合数学里最简单、最基本的原理。本文简述了抽屉原理普遍使用的简单形式，重点介绍了抽屉原理在我们数学竞赛，通过由浅到深，由简单到复杂，循序渐进的了解抽屉原理。同时，通过对抽屉原理的学习，我们可以发现在我们日常生活中很多地方都有抽屉原理的应用。通过本文的介绍，相信大家对抽屉原理会有一个更为全面的认识。

关键词：抽屉原理、狄利克雷原理、数学竞赛、拉姆塞定理

Abstract：This paper describes the simple 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 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,Ramsry’s theorem

1

1 引言

抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P.G.T.Dirichlet 1805-1855)首先发现的，因此也叫作狄利克雷原理。

抽屉原理简单易懂，主要用于证明某些存在性或至少类的问题，在生活中抽屉原理的应用非常广泛，解决了生活中一些模糊不清的问题，方便了人们的生活。

本文归纳了抽屉原理在小学数学竞赛、中学数学竞赛中的一些简单应用，由浅入深将抽屉原理推广到更高的领域，并举例阐述了抽屉原理在现实生活中的应用。

2 抽屉原理的定义

第一抽屉原理

原理1：把多于n个的物体放在n个抽屉里，则至少有一个抽屉里的东西不少于两件。 证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是 n，而不是题设

1)，故不可能。 的n?k(k≥ 原理2：把多于mn（m乘于n）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于m?1的物体。

证明（反证法）：若每个抽屉至多放进m个物体，那么n个抽屉至多放进mn个物体，与题设不符，故不可能。

原理3：把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体。 第二抽屉原理

（m?1）（mn?1） 把个物体放入n个抽屉中，其中必有一个抽屉中至多有个物体（例如，将

3×5-1?14个物体放入5个抽屉中，则必定有一个抽屉中的物体数少于等于3-1?2）。 证明（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。

3 抽屉原理在数学竞赛以及实际生活中的应用

数学竞赛是以开发智力为根本目的、以问题解决为基本形式、以竞赛数学为主要内容。最本质的是对中学生进行“竞赛数学”的教育，这种教育的性质是：较高层次的基础教育、开发智力的素质教育、生动活泼的业余教育、现代数学的普及教育。

数学竞赛与体育竞赛相类似，它是青少年的一种智力竞赛，所以苏联人首创了\数学奥林匹克\这个名词。在类似的以基础科学为竞赛内容的智力竞赛中，数学竞赛历史最悠久，参赛国最多，影

2

数学与计算机科学学院毕业论文

响也最大。

数学竞赛活动也是由浅入深逐步发展的。几乎每个国家的数学竞赛活动都是先由一些著名数学家出面提倡组织，试题的命题在背景的深刻度和构题的艺术性上也有较高的要求，较为突出的有四条：内容的科学性、结构的新颖性、功能的选拔性、解法的灵活性。数学竞赛命题的基本途径主要有：高等初等化，历史名题的再生，成题改编，模型法。抽屉原理由于它自身的特点，简单并且思维方法在解题过程中可以演变出很多奇妙的变化和颇具匠心的运用，所以抽屉原理经常是命题人出题方向及思路。

3.1 抽屉原理在小学数学竞赛中的应用

其实在抽屉原理在小学数学中已经有雏形了，在人教版六年级下册中的“数学广角”中，就已经出现了一些抽屉原理的简单应用。当时就有很多教师反应教学存在一定的困难性，不仅如此，学生也普遍觉得难以理解，学习起来也很困难！在数学问题中，经常碰到有关“存在性”的问题。如某地区医院一月共接生32名婴儿，那么一定存在两名婴儿，他们是在同一天出生的。在解决这类问题中，只需要确定某个人（或某件物），也不需要严格说明通过什么方式把这个存在的人（或物）找出来。这就是我们小学初次接触的比较简单的“抽屉原理”，即把多于n个的物体放在n个抽屉里，则至少有一个抽屉里的东西不少于两件。在教学过程中，教学者普遍认为在这类问题上很难向学生讲清其中的来龙去脉，所以在理解算法的基础上，采用“总有??至少??”的语言叙述出来，以加固理解，采用这种教学方法，学生相对来说容易理解一些。 下面我们将问题建立两类模型来解决：

模型一 求至少的问题

这类问题的特点是：已知“抽屉”的个数，求某个“抽屉”里至少能装多少的问题。

例1 在任意的49个人中，至少有几个人的属相相同？ 解：因为共有12个生肖，将12个生肖看成12个“抽屉”，问题就转换成寻求一个“抽屉”里至少能“装”多少人。我们可以先算出平均每个“抽屉”“装”多少个人：49?12?4??1，多出来的1个人总会随机的进入到某个“抽屉”中，所以总有一个抽屉里有四个人，也就是总有一种生肖属相里至少有4个人。即：至少有4个人的属相相同。

例2 平面上有六个点A、B、C、D、E、F，其中不存在三个点在同一条直线上的情况，每两点之间都用红线或蓝线连接。试说明：不管如何连接，至少存在有一个三角形是三条边的颜色都相同。 解：从六个点当中任取一点，设为A，在用它连接其余五点的五条线段中，至少有3条同色（把红、蓝两色作为两个“抽屉”，5?2?2??1,2?1?3）。假设其中的AB、AC、AD为红色线段（如

下图所示）。

BCAD

这时，在三条线段BC、BD、CD中，若有一条为红色，则得到一个三边为红色的三角形；（如下图所示）

3

BCAD

若没有一条为红色，则BC、BD、CD都是蓝色，也得到一个三边都是的三角形⊿BCD。（如下图所示）

BCA

所以不管怎样连接，至少有一个三边同色的三角形。

对于求至少性的这类问题，我们首先确定有多少个抽屉，然后可以把物体平均分给这几个抽屉，剩余的物体再平均分一次，最后就可以确定一个抽屉至少有几个物体。解这类问题的原理是把多于mn（m乘于n）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于m?1的物体。 模型二 作“最坏”的打算

理论依据：把多于n个的物体放在n个抽屉里，则至少有一个抽屉里的东西不少于两件。即：一定有一个“抽屉”里至少有两个元素。

例3 有红、黄、绿三种颜色的手套各6双，装在一个黑色的布袋里，从袋子里任意取出手套来，为确保至少有2双手套不同颜色，则至少要取出的手套只数是？ 分析：“为确保至少有”，考虑最坏的情况，首先取出了一种颜色的全部6双手套和其他两种颜色的手套各一只，再任意取出一只，必然得到2双不同颜色的手套。因此至少要取出2?6?2?1?15只。

例4 有120名职工投票从甲、乙、丙三人中选举一人为劳模，每人只能投一次，且只能选一个人，得票最多的人当选。统计票数的过程发现，在前81张票中，甲得21票，乙得25票，丙得35票。在余下的选票中，丙至少再得几张选票就一定能当选？

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

综上所述，抽屉原理在小学数学中主要是上述两方面的应用，实质上就是抽屉原理的两种常用形式。在教学中，可以归类进行学习，建立两种模型，学生熟练掌握，进而能简单应用。为孩子后续学习和理解打下坚实的基础。

3.2 抽屉原理在中学数学竞赛中的应用

在小学数学中我们已经学习了“抽屉原理”的雏形，在初中数学中我们主要学习的是抽屉原理

4

D 数学与计算机科学学院毕业论文

的基本形式和如何使用抽屉原理，并通过实例了解抽屉原理中的一些构造方法，以及抽屉原理在中

学数学竞赛题中的应用。 抽屉原理的基本形式：

（1）把n?1个元素分为n个集合，那么必有一个集合中含有两个或两个以上的元素。 （2）把nm?1个元素分成n个集合，那么必有一组中含有m?1个或m?1个以上元素。

（3）把n个元素分成k个集合，那么必有一个集合中元素的个数???，也必有一个集合中元

k素的个数???。

k（4）把q1?q2?合中元素的个数?qi。

（5）把无穷多个元素分成为有限个集合，那么必有一个集合含有无穷多个元素。 抽屉原理的基本构造：

利用抽屉原理解题的过程中首先要注意指明什么是元素，什么是抽屉，元素进入抽屉的规则是什么，以及在同一个盒子中，所有元素具有的性质。构造抽屉是用抽屉原理解题的关键。有的题目运用一次抽屉原理就能解决，有的则需要反复多次。

下面我们通过一些具体的例题来介绍抽屉原理的应用：

例5 求证：从任意给定的2010个自然数a1,a22010的倍数。

?n????n????qn?n?1个元素分为n个集合，那么必有一个i(1?i?n)，在第i个集

a2010，中可以找到若干数，使得它们的和是

，… ，2009，即被2010除的余数分类制造抽屉，将下列数： 证明 以0,1S1?a1,S2?a1?a2,S3?a1?a2?a3,…,S2010?a1?a2?a3?…a2010作为抽屉中的元素。

若上述2010个数中有一个是2010的倍数，则问题得证；

否则，根据抽屉原理，至少存在两个数Sm,Sn（它们的差仍为a1,a2,a3,…,a2010中若干数的和），它们被2010除的余数相同，则它们的差是Sm?Sn，即a1,a2,?,a2010中若干数的和能被2010整除，命题得证。

此例是抽屉原理中常见的题型“存在至少”性问题，解决此类问题的关键就是抽屉的中元素的选择。

例6 在边长为1的正方形内任意放入九个点，求证：存在三个点，以这三个点为顶点的三角形的

面积不超过

5

1。（1963年北京竞赛题） 8

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库抽屉原理的应用及其推广优秀毕业论文在线全文阅读。