抽屉原理及其应用----陈梦霞.doc

抽屉原理及其应用 陈梦霞 作者： 日期：2 个人收集整理 勿做商业用途 学号： 10124090304 学年论文题 目 ：抽屉原则及其运用Title ：Dicichlet drawer principie and the application of it学院 理学院 专业 数学与应用数学(师范)班级 数学103班 学生 陈梦霞 指导教师（职称） 戴丽娜（讲师） 完成时间 2012 年 4 月 1日至 2012 年 4 月 8日指导教师评语：评分： 签名： 1摘要本文简述了抽屉原理普遍使用的简单形式、各种推广形式，着重阐述其在数论和离散数学、高等代数及抽象代数中的应用，及在生活中的应用，可以巧妙地解决一些复杂问题,并根据抽屉原理的不足之处引入抽屉原理的推广定理Ramsey定理.关键词 :抽屉原理 数论 离散数学 高等及抽象代数 Ramsey定理引言 抽屉原理又称鸽巢原理、鞋箱原理或重叠原理，是一个十分简单又十分重要的原理.它是由德国著名数学家狄利克雷(P。G。T.Dirichlet 1805-1855）首先发现的,因此也叫作狄利克雷原理.抽屉原理简单易懂,主要用于证明某些存在性或必然性的问题，不仅在数论、组合论以及集合论等领域中有着广泛应用，在高等数学的其它几门学科领域中也是解决问题的有效方法。本文总结了如何运用抽屉原理解决数论、离散数学、高等代数及抽象代数中的问题，对抽屉原理在高等数学中的应用进行了梳理，将抽屉原理的解题思路拓展到高等数学的其他领域，有助于更好地理解抽屉原理，并举例阐述了抽屉原理在现实生活中的应用，以及根据抽屉原理的不足引出的Ramsey定理。31.抽屉原理的形式什么是抽屉原理？先举个简单的例子说明，就是将3个球放入2个篮子里，无论怎么放，必有一个篮子中至少要放入2个球，这就是抽屉原理。或者假定一群鸽子飞回巢中,如果鸽子的数目比鸽巢多，那么一定至少有一个鸽笼里有两只或两只以上的鸽子，这也是鸽巢原理这一名称的得来。抽屉原理简单直观，很容易理解。而这个看似简单的原理在高等数学中有着很大的用处，对于数论、离散数学、高等代数以及抽象代数中的一些复杂问题，可以利用抽屉原理巧妙的解答出来.下面首先从抽屉原理的形式入手，然后再研究它在高等数学中的应用. 我们最常用的抽屉原理只是抽屉原理的简单形式，就是将n+1个元素或者更多的元素放入n个抽屉中，则至少有一个抽屉里放有两个或两个以上的元素。除了这种比较普遍的形式外,抽屉原理还经许多学者推广出其他的形式。 陈景林、阎满富在他们编著的组合数学与图论一书中将抽屉原理抽象概括成以下三种形式1：原理1. 把多于个的元素按任一确定的方式分成个集合，则一定有一个集合中含有两个或两个以上的元素。原理2. 把个元素任意放到个集合里，则至少有一个集合里至少有个元素，其中原理3。 把无穷个元素按任一确定的方式分成有限个集合,则至少有一个集合中仍含无穷个元素。卢开澄在组合数学（第三版）中将抽屉原理（书中称为鸽巢原理)又进行了推广2。鸽巢原理：设k和n都是任意正整数，若至少有kn+1只鸽子分配在n个鸽巢中,则至少存在一个鸽巢中有至少k+1只鸽子.推论1.有m只鸽子和n个鸽巢，则至少有一个鸽巢中有不少于+1只鸽子.推论2。若将n（m-1)+1个球放入n个盒子里，则至少有一个盒子有m个球。推论3.若是n个正整数,而且r=,则中至少有一个数不小于r。另外，抽屉原理还可以用映射的形式来表示,即：设和是两个有限集，如果，那么对从到的任何满射,至少存在,，使.52。抽屉原理在高等数学中的应用 以上的几种形式就是我们解题时常用到的抽屉原理的表示形式，接下来，在了解了抽屉原理的基本形式以及多位学者所发展的推广形式的基础上,我们通过一些比较典型的实例来说明抽屉原理在高等数学中数论、离散数学、高等代数以及抽象代数这五个方面的应用。2.1 数论问题中的应用 例1.任意5个整数中，有其中3个整数的和为3的倍数。证明 将整数分为形如3k、3k+1及3k+2这3类形式， 则我们可以将这3类整数看作是3个抽屉，将这5个整数看作元素放入这3个抽屉中。 由抽屉原理可知,至少存在2=+1个整数在同一抽屉中,即它们都是形如(3k+m）的整数，m=0,1或2。 如果有3个以上的数在同一个抽屉中，则取其中的任意三个数,它们的和是形如3（3k+m）的整数，即三者的和为3的倍数.如果有2个整数在同一个抽屉中，则由抽屉原理知，在余下的3个数中有2个数在同一个抽屉中，余下的1个数在另一个抽屉中。在3个抽屉中各取一个数，这3个数的形式分别为3k,3k+1，3k+2，则三者的和为3（k+k+k）+3，即为3的倍数。例2。从1,2，3,，98中任取50个不同的数，试证:其中必有两个数,它们之差等于7.证明先把所给的98个数设计成49个抽屉：（1,8），（2,9）(3,10),（4,11),(21,28），(91，98）,每个抽屉中的两个数之差为7。 从1，2，3，,98中任取50个，就是从这49个抽屉中任取50个数,由抽屉原理1知，必有一个抽屉中要取两个数，即这50个数中必有两个数，它们之差等于7。例3.任取6人,试证必有3人,他们互相认识或不认识.证明用A、B、C、D、E、F表示这六个人,首先以A为中心考虑,与另外五个人B、C、D、E、F只有两种可能的关系:认识或不认识，则由抽屉原理知,必定与其中某三个人认识或不认识。现在不妨设A认识了B、C、D三人，当B、C、D不认识时，问题得证；当B、C、D三人中有两人认识,如B、C认识时，则A、B、C互相认识，问题也得证。2.2 离散数学中的应用 例4。设有3个7位的二进制数 试证存在整数和，,使得下列之一必然成立 解 由已知条件,在每一个纵列中，含有三个元素，分别都只由两种选择，即0或1，则根据鸽巢原理，中至少一个必然成立。 成立的时候取值的不同可以有=6种情况，而每一横行共有七个元素再根据鸽巢原理,必有两列是相同的. 即之一必然成立。例5。三维空间中9个坐标为整数的点，试证在两两相连的线段内，至少存在一个坐标为整数的内点.解 三维空间中,任意两坐标为整数的点，若这两点相连的线段内不存在坐标为整数的内点,则对于x,y,z这三个坐标轴，这两点至少在一个坐标上的差值正好是1. 那么，在这9个坐标为整数的点中，任意取出一点，与这个点的三个坐标中，存在的差值正好是1的共有7类，即与x轴差值正好是1，与y轴差值正好是1，与z轴差值正好是1，与x，y轴差值都是1，与x,z轴差值都是1，与y,z轴差值都是1，与x,y，z轴差值都是1。 对于剩下的8个点，若存在一点a不满足这7种情况,那么a点与这个点相连的线段内必有一个坐标为整数的内点. 若剩下的8个点都属于这7种情况之一，那么，运用鸽巢原理,则至少存在两个点属于这7种情况中的同一个情况，那么，这两点中必存在一个坐标为整数的内点。例6。在平面直角坐标系中，求至少在多少个整点(坐标都是整数的点）中有4个整点,它们两两的中点也是整点.7分析 由中点坐标公式知，中点为整点的条件是两个端点的对应坐标的奇偶性相同,因此，需要把整点的坐标按奇偶性分类. 解 整点的坐标按整数的奇偶性分成如下四类：（奇，偶）,(奇,奇），（偶，奇），（偶,偶）。 由抽屉原则2知，在X个整数中至少一类中有4个整点，所以，即，所以12，即13.所以x的最小值是13，即至少在13个整数点中,有4个整点,它们两两的中点也是整点.2.3 高等代数中的应用例7. 设为阶方阵，证明存在1,使秩(）=秩()=秩证明 因为阶方阵的秩只能是这+1个数之一.，的个数多于秩的个数，由抽屉原理可知,存在,满足1R(p,q）时，用红蓝两色涂的边，则或存在一个蓝色的,或存在一个红色的.Ramsey定理(狭义）的内容任意六个人中要么至少三个人认识，要么至少三个不认识。 Ramsey定理可以视为抽屉原理的推广，1947年,匈牙利数学家把这一原理引进到中学生数学竞赛中,当年匈牙利全国数学竞赛有一道这样的试题：“证明:任何六个人中,一定可以找到三个互相认识的人，或者三个互不认识的人.” 在1958年6-7月号美国数学月刊同样也登载着这样一个有趣的问题“任何六个人的聚会，总会有3人互相认识或3人互相不认识.”这就是著名的Ramsey问题.这个问题乍看起来,似乎令人匪夷所思。但如果懂得抽屉原理，要证明这个问题是十分简单的: 我们用A、B、C、D、E、F代表六个人，从中随便找一个,例如A吧，把其余五个人放到“与A认识和“与A不认识”两个“抽屉”里去，根据抽屉原理，至 少有一个抽屉里有三个人。不妨假定在“与A认识的抽屉里有三个人，他们是B、C、D.如果B、C、D三人互不认识，那么我们就找到了三个互不认识的人; 如果B、C、D三人中有两个互相认识,例如B与C认识，那么，A、B、C就是三个互相认识的人.不管哪种情况，本题的结论都是成立的。或者我们可以用染色的方法。以6个顶点分别代表6个人，如果两人相识，则在相应的两点间连一条红边,否则在相应的两点间连一蓝边.命题1。对6个顶点的完全图任意进行红、蓝两边着色,都存在一个红色三角形或蓝色三角形.证明如下首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设如果两个人认识,则设这两个人组成的线段为红色;如果两个人不认识，则设这两个人组成的线段为蓝色.由抽屉原则可知这五条线段中至少有三条是同色的.不妨设AB、AC、AD为红色。若BC或CD为红色，则结论显然成立。若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识。上述的Ramsey问题等价于下面的命题1。命题1.对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色三角形或蓝色三角形。命题1运用抽屉原理可以很容易很简便地对其进行证明。现将命题1推广成下面的命题2。命题2.对六个顶点的完全图任意进行红、蓝两边着色，都至少有两个同色三角形.由于命题2是要证明至少存在两个同色三角形的问题，而抽屉原理一般只局限在证明至少存在一个或必然存在一个的问题，所以对于上述命题抽屉原理就显得无能为力,这时需要运用Ramsey定理来解决问题。 例13。证明 设是的六个顶点，由上面的命题1可知，对任意进行红、蓝两边着色都有一个同色三角形，不妨设是红色三角形.以下分各种情况来讨论(1)若均为蓝边，如图1所示，则若之间有一蓝边，不妨设为，则三角形为蓝色三角形；否则,为红色三角形。 图1 图2（2）若中有一条红边，不妨设为红边，此时若边中有一条红边，不妨设是红边，则是一红色三角形，见图2.以下就均为蓝边的情况对与相关联的边的颜色进行讨论. ()若中有一蓝边，不妨设为蓝边，如图3，此时，若均为红边，则是红色三角形;否则，或是蓝色三角形。 （)若均为红边,见图4，此时，若之间有一条红边，不妨设为红边，则为红色三角形；否则,为蓝色三角形。 图3 图4 由以上对各种情况的讨论知，对的任意红、蓝两边着色均有两个同色三角形。从以上例子可知，抽屉原理在应用上确有不足之处,之上只是个特例，至于在别的领域中的不足之处还需我们进一步的探索. 抽屉原理的应用领域十分广泛，涉及到高等数学的多个学科，并且在生活中也有广泛的应用,可以巧妙的用于解决一些复杂问题，本文主要梳理总结了它在数论、离散、高等代数及抽象代数中的应用，其不足之处也由Ramsey定理进行了补充，使其能够更好的应用与问题解决当中.13参考文献1陈景林,阎满富。组合数学与图论。北京中国铁道出版社出版,2000。042卢开澄.组合数学（第3版）。北京清华大学出版社，2002。073濮安山.“高等代数中抽屉原理的应用”.哈师大自然科学学报，2001。064王向东，周士藩等。高等代数常用方法M。1989。11。5杨子胥。近世代数。北京。高等教育出版社。2003。126严士健。抽屉原则及其它的一些应用J.数学通报，19597曹汝成。组合数学M。华东理工大学出版社,2000