大学数学论文new

1、抽屉原理及其应用学生姓名：闫梦茹 学号：20090401017 数学与计算机科学系 数学与应用数学专业指导教师：沈守强 职称：讲师摘 要：抽屉原理是数学中一个十分重要的原理，其应用非常广泛. 本文首先给出了抽屉原理的一些形式，然后讨论了它在数学中和生活中的一些具体应用.关键词：抽屉原理；数学；应用Abstract：Drawer principle is an important principle in mathematics, its application is very extensive. This paper gives some form of drawer principle,

2、and then discusses it in mathematics and the life of some specific application.Key Words: Drawer principle; Mathematics; Application引言 抽屉原理又称鸽巢原理、鞋盒原理、重叠原理，它最先是由德国数学家狄利克雷明确地提出来的，因此也称为狄利克雷原理.比如说，桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果.这一现象就是我们所说的“抽屉原理”.抽屉原理的内容简洁明了，易于接受，它在解决数学问题中有非常重要的作用，许

3、多生活中的问题也可以用它来解决.为此，本文首先给出了抽屉原理的一些形式，然后讨论了它在近世代数、离散数学、数论、高等代数及几何中的具体应用，最后还利用抽屉原理解决了生活中的取同色衣服、电脑算命及握手问题.1. 抽屉原理1.1 抽屉原理的形式原理1 如果把个元素分到个集合中，那么不管怎么分，则必有一个集合中至少含有两个元素. 证明 用反证法. 如果个集合中每个集合至多放一个元素，则放入个集合中的元素总数至多为个.这与假设有个元素矛盾，从而定理得证. 原理2 把无穷多个元素按任意确定方式分成个集合，则至少有一个集合中仍含有无穷个元素. 原理3(鸽巢原理） 设为正整数，如果将个物体放入个盒子内，那么

4、，或者第一个盒子至少含有个物体，或者第二个盒子至少含有个物体,，或者第个盒子至少含有个物体.证明 设将个物体分放到个盒子中，若对于每个第个盒子里含有少于个物体，则所有盒子中的物体总数不超过该数比所分发的物体总数少.因此，我们断言，对于某一个，第个盒子至少包含个物体.在初等数学中，如果上述都等于同一个整数时，该原理叙述如下：推论1 如果个物体放入个盒子中，那么，至少有一个盒子含有个或更多的物体.推论2 如果个非负整数的平均数大于,那么，至少有一个整数大于或等于.推论3 如果个非负整数的平均数小于，那么，至少有一个整数小于或等于.推论4 如果个非负整数的平均数至少等于,那么，这个整数至少有一个满足

5、. 推广 如果把多于个元素分成个集合，则至少有一个集合中含有不少于个元素.证明 用反证法. 如果每个集合至多放个元素，那么个集合至多放个元素，这与题设不符，从而定理得证.原理4（抽屉原理的映射形式） 设和是两个有限集，如果，那么对从到的任何满映射，至少存在，使.1.2 抽屉原理的解题步骤 第一步：分析题意. 分清什么是“东西”，什么是“抽屉”，也就是什么作“东西”，什么可作“抽屉”. 第二步：制造抽屉.这是最关键的一步，这一步就是如何设计抽屉.根据题目条件和结论，结合有关的数学知识，抓住最基本的数量关系，设计和确定解决问题所需要的抽屉及其个数，为使用抽屉铺平道路.通常有以下三种构造抽屉的方法：

6、 ()整除性问题：常以剩余类为抽屉；()集合问题：常以元素的性质划分集合构造抽屉；()其他问题：常将状态不同的元素分类构造抽屉. 第三步：运用抽屉原理.观察题设条件，结合第二步，恰当应用各个原则或综合运用几个原则，以求解决问题.2. 抽屉原理在数学中的应用 一般地说，用抽屉原理来解决数学问题的时候，有如下特征：新给的元素具有任意性，如八只鸽子放入七个笼子，可以随意地一个笼子放几只，也可以让笼子空着.问题的结论是存在性命题，题中常含有“至少有”、“一定有”、“不少于”、“存在”、“必然有”等词语，其结论只要存在，不必确定.下面来讨论抽屉原理在数学中的具体应用.2.1 在近世代数中的应用例1 证明

7、只含有限个理想的非零整环必是域.证明 根据魏德邦定理，只需证明是除环即可. 也即证对中任意元素，方程或在中有解. 事实上，在中任取元素，考虑，易知，都是的理想.但由于整环只有有限个理想，根据抽屉原理，必存在正整数与满足，从而存在,使或.即方程在中有解,根据定理，是除环.由魏德邦定理，原命题得证.例2 从阶群中任取个元素，证明存在使（单位元）.证明 因为. 用所取元素的积及作序列： （1）则它的项都是的元素. 根据抽屉原理，序列（1）中必有两项相等. 如果，此时，符合要求，否则有.于是有.取，有,使.2.2 在离散数学中的应用 例3 ,是的子集，且,可以找到的两个非空真子集和，使得的元素之和与的

8、元素之和相等.解 由于，所以的非空子集的数目为，另一方面，的元素之和有,.这说明中个元素的和不超过，也就是个元素之和不同的数充其量也就是个.现在有只鸽子,个鸽巢，故存在一个鸽巢中两个鸽子相同.设这个子集为和,使得若和无共同元素，即，则若,则便是所求. 例4 设是个正整数的集合，且，证明存在非空的子集, 使得的元素之和被除尽.证明 设，令 若存在，则.否则，为小于的正整数，根据鸽巢原理,个鸽巢，只鸽子，必存在和相等，不妨设,则，故 ，即.2.3 在数论中的应用 中国余式定理 令和为两个互素的正整数，并令和为整数，且以及，则存在一个正整数，使得除以的余数为，并且除以的余数为，即可以写成的同时又可以

9、写成的形式，这里和是整数.证明 为了证明这个结论,考虑个整数这些整数中的每一个除以都余.设其中两个除以有相同的余数，令这两个数为和，其中因此，存在两个整数和，使得，这两个方程相减可得. 于是是的一个因子. 由于和没有除之外的公因子，因此是的因子.然而，意味着，也就是说不可能是的因子.该矛盾产生于我们的假设，个整数中的两个除以有相同的余数. 因此，这个数中的每一个数除以都有不同的余数. 根据抽屉原理，个数中的每一个作为余数都要出现，特别地，数也是如此.令为整数，满足，且使数除以余数为.则对于某个适当的，有. 因此且，从而具有所要求的性质.例5 从到的个正整数中任取个，则这个数中至少有一对数，其中

10、一个数是另一个数的倍数. 证明 设所取个数是，对序列中的每一个数去掉一切的因子，直至剩下一个奇数为止.例如，去掉的因子，留下奇数，结果得到由奇数组成的序列 （2）到中只有个奇数，故序列（2）中至少有两个是相同的.设为，对应地有.若，则是的倍数.例6 设是个任意整数，是的任一排列，则至少有一个是偶数. 证明 根据抽屉原理，这个数中至少有两个数同为偶数，或同为奇数，不妨设这两个数为和，且同为奇数，则中至多有一个偶数.故再根据抽屉原理，和中至少有一个是奇数，而且有一个和中某一个相等.奇数与奇数之差为偶数,故中至少有一个为偶数.若两个数同是偶数，结果也是对的，因偶数与偶数之差仍然是偶数.2.4 在高等

11、代数中的应用例7 设为阶方阵，证明存在，使秩=秩=秩=.证明 因为阶方阵的秩只能是这个数之一，令，的个数多于秩的个数，由抽屉原理可知，存在,满足使得秩=秩，但秩秩秩，所以秩=秩，利用此式与秩的性质得秩秩+秩-秩,这里的是任意三个可乘矩阵，用数学归纳法可证秩=秩.其中为非负整数，故命题的结论成立.例8 已知齐次线性方程组 其中.证明存在不全为零的整数适合.证明 令.于是，所给方程组写成. 设集合那么映射是一个满射，显然，因为，所以对每个,它的个分量适合 因此，又，于是根据抽屉原理的映射形式知，必存在中两个不同的元使,于是.令，则就是我们所要求的.是不全为零的整数，且满足.2.5 在几何中的应用例

12、9 在边长为的正方形内部，放置若干个圆，这些圆的周长之和等于.证明：可以作出一条直线，至少与其中四个圆有交点.证明 将所有的已知圆投影到正方形的一条边上.注意，周长为的圆周，其投影长为的线段.因此所有已知圆的投影长度之和等于，由于，所以由抽屉原理知，线段上必有一点，至少被四条投影线段所覆盖.即至少有四条投影线段有公共点.因此，过点且垂直于的直线，至少与四个已知圆有交点.例10 求证：在平面内，任意凸五边形的顶点中，必有三点、，使.分析 因为是凸五边形五个内角大小的平均值，又是的三等分值，所以此题要用两次抽屉原理.证明 因为平面凸五边形的内角和为，所以由抽屉原理知，至少有一个内角不小于.不妨设这

13、个不小于的内角的顶点为，与它不相邻的两个顶点为、，边、把分成三个角，则由抽屉原理知，必有一个角不小于，设这个角为，于是.例11 边长为的正三角形内任选五个点，必有两点的距离不超过.证明 用正三角形的三条中位线可将其分割为个边长为的小正三角形，以这个小正三角形为鸽笼，将要选的个点视为只鸽子，由鸽笼原理可知，必有个点（鸽子)落在某一个小正三角形内.因为小正三角形内任两点之间的距离小于等于边长，即知此两点的距离小于等于.3. 抽屉原理在生活中的应用抽屉原理在日常生活中的应用也非常的广泛，比如说：个人中必然至少存在两人有相同的生日；抽屉里有双手套散开放着，从中任取只，其中至少有一对是成双的.这些都可以

14、用抽屉原理来解释.下面进一步讨论抽屉原理在生活中的有趣应用.3.1 取同色衣服 如果你的衣柜里有件衣服，其中件是蓝的，件是灰的，件是红的.试问应从中随意取多少件能保证有件是同色的.又应再抽取多少件保证为件是同颜色的？根据鸽巢原理，个鸽巢，只鸽子，则至少有一个鸽巢有只鸽子. （1）现在有个鸽巢，即,所以，,.即随意抽取件可保证有件是同颜色的. （2）似乎若依据（1），,则应抽取件能保证有件同色.其实不然，问题的模型与鸽巢原理不尽相同.我们考虑一种最坏的情况：第次取件正好有件都是蓝的即件蓝色，取走后，问题变成由灰的和红的构成同颜色的情况.这时，,.故应取件. （3） ,故需要取出件. （4） ,应

15、取件. （5） 考虑到蓝的和灰的已分别取尽，这时只剩下红的，,故应取件. （6） ,应取件.3.2 电脑算命 “电脑算命”看起来挺玄乎，只要你报出自己出生的年、月、日和性别，一按按键，屏幕上就会出现所谓性格、命运的句子，据说这就是你的“命”.这是科学的吗？如果以年算，按出生的年、月、日、性别的不同组合数应为，我们把它作为抽屉数.我国现在有亿人口，把它作为物体.由于，根据抽屉原理，存在个以上的人，尽管他们的出身、环境、经历、天赋、机遇各不相同，但他们却有完全相同的“命”，这是非常荒谬的！所谓“电脑算命”不过是把人为编好的算命语句像中药柜那样事先分别一一存放在各自的柜子里，谁要算命，即根据出生的年

16、、月、日、性别的不同的组合按不同的编码机械地到电脑上各个“柜子”里取出所谓命运的句子.其实这充其量不过是一种电脑游戏而已.3.3 有趣的握手在一次聚会后，如果你统计一下每个人的握手数（即与他人握手的次数），你会发现握手数为奇数的一定是偶数个人，且必有两个人的握手数相等.假如聚会有个人参加（当然可以假定），其中握手数为的有个人.若，即大家彼此全未握手，结论当然成立.现在假设（注意不会有，只能是），设这个人的握手数分别为，因为他们握手的范围就在这个人之间，故必有.由抽屉原理可知，诸中必有个是相等的，进而，因为每次握手分别对握手的两人各计入一次握手数，故必为偶数.此即说明诸中奇数的个数只能是偶数.至

17、于另个未与任何人握手的人，他们的握手数被认为是偶数.这就得到了全部结论.4. 小结 抽屉原理是一个叙述起来非常简单明了的原理，但它在数学和日常生活中的应用十分广泛.本文首先给出了抽屉原理的一些形式，然后讨论了它在近世代数、离散数学、数论、高等代数及几何中的具体应用，最后还利用它解决了生活中有趣的取同色衣服、电脑算命及握手问题.运用抽屉原理的关键在于如何制造抽屉，而构造抽屉的技巧也有很多，比如利用等分区间、分割图形、对称性等都可以制造抽屉，这里不再一一论述. 参考文献1 田秋成.组合数学.M.北京：电子工业出版社，2006.2 卢开澄，卢华明.组合数学.M.北京：清华大学出版社，2006.3 曹汝成