《《抽屉原理及其应用》-公开DOC·毕业论文》由会员分享,可在线阅读,更多相关《《抽屉原理及其应用》-公开DOC·毕业论文(18页珍藏版)》请在金锄头文库上搜索。
1、平顶山学院本科毕业论文(设计)目录 1抽屉原理111抽屉原理的简单形式112抽屉原理的加强形式22抽屉原理的应用421抽屉的构造4211等分区间制造抽屉4212分割图形构造抽屉5213利用“对称性”构造抽屉6214用整数性质制造抽屉7215利用染色制造抽屉8216根据问题的需要制造抽屉922 抽屉原理在数学解题中的应用10221解决代数问题10222解决数论问题11223解决几何问题12224多次顺向运用抽屉原理12225逆向运用抽屉原理1323抽屉原理在生活中的应用13231月黑穿袜子13232手指纹和头发14233电脑算命143总结15参考文献16致 谢171抽屉原理 有关于抽屉原理的阐释
2、,粗略的说就是如果有许多物体放进不足够多的盒子内,那么至少有一个盒子被两个或多个盒子占据更精确的叙述在下面给出11抽屉原理的简单形式 抽屉原理的最简单的形式如下定理111 如果个物体放进个盒子,那么至少有一个盒子包含两个或更多的物体证明:(用反证法)如果个盒子中每个盒子至多放一个物体,则放入个盒子中的物体总数至多为个这与假设有个物体矛盾从而定理得证注意,无论是抽屉原理还是它的证明,对于找出含有两个或更多物体的盒子都没有任何帮助我们只是简单断言,如果人们检查每一个盒子,那么他们会发现有的盒子,里面放有多于一个的物体抽屉原理只是保证这样的盒子存在因此,无论何时抽屉原理被用来证明一个排列或某种现象的
3、存在性,除了考察所有的可能性外,它都不能对任何构造排列或寻找现象的例证给出任何指示还要注意,抽屉原理的结论不能被推广到只存在个(或更少)物体的情形这是应为我们可以把不同的物体放到个盒子的每一个中去当然,在这些盒子中可以这样分发物体:一个盒子放入两个物体,但对任意分发这是没有保证的抽屉原理只是断言,在个盒子中去论如何分发个物体,总不能避免把两个物体放进同一个盒子中去还存在一些与抽屉原理相关的其它原理,有必要正式叙述如下(1) 如果将个物体放入个盒子并且没有一个盒子是空的,那么每个盒子恰好包含一个物体(2) 如果将个物体放入个盒子并且没有盒子被放入多于一个的物体,那么每个盒子里有一个物体现在把所阐
4、明的这三个原理更抽象的表述为:令和是两个有限集,并令是一个从到得函数(1)如果的元素多于的元素,那么就不是一对一的(2)如果和含有相同个数的元素,并且是映上的,那么就是一对一的(3)如果和含有相同个数的元素,并且是一对一的,那么就是映上的12抽屉原理的加强形式 下列定理包含定理111作为它的特殊情形定理121 设为正整数如果将个物体放入个盒子内,那么,或者第一个盒子至少含有个物体,或者第二个盒子至少含有个物体,或者第个盒子至少含有个物体证明:设将个物体分放到个盒子中如果对于每个,第个盒子含有少于个物体,那么所有盒子中的物体总数不超过该数比所分发的物体总数少1,因此我们断言,对于某一个,第个盒子
5、至少包含个物体 注意,能够将个物体用下面的方法分到个盒子中,对所有的第个盒子都不能含有个或更多的物体,我们可以通过将个物体放入第一个盒子,将个物体放入第二个盒子等来实现,抽屉原理的简单形式是由其强化形式的通过使得到的,由此有在初等数学中抽屉原理的加强形式最常用于都等于同一个整数的特殊情况在这种情况下,该定理叙述如下:推论121 如果个物体放入个盒子中,那么至少有一个盒子含有个或更多的物体等价的,推论122如果个非负整数的平均数大于:那么至少有一个整数大于或等于这两种表述之间的联系可以通过取个物体并放入个盒子中得到对于,令是第个盒子中的物体个数于是这个数的平均数为由于这个平均数大于,故而有一个整
6、数至少是换句话说,这些盒子中有一个盒子至少含有个物体 推论123 如果个非负整数的平均数小于:那么至少有一个整数小于推论124 如果个非负整数的平均数至少等于,那么这个整数至少有一个满足推论125 个物体放入个盒子中,则至少有一个盒子中有不少于个物体注:符号表示不超过实数的最大整数证明:(反证法)若不然,则每一个集合中最多有个物体,这时, 个盒子中就最多有个物体因为,所以,这与已知条件个物体放入个盒子中矛盾,故上述推论成立抽屉原理的形式比较多变,在具体的应用中也会有不同的变化,但本质上都是一样的 上述定理及推论的证明均采用反证法,这种证明方法对于证明元素个数多于抽屉个数的问题时有其普遍意义,
7、平均重叠原则:把一个量任意分成份,则其中至少有一份不大于,也至少有一份不少于不等式重叠原则:若,且,则,至少有一个成立 面积重叠原则:在平面上有个面积分别是,的图形,把这个图形按任何方式一一搬到某一个面积为的固定图形上去, (1)如果,则至少有两个有公共点; (2)如果,则固定图形中至少有一个点未被盖住2抽屉原理的应用应用抽屉原理的基本思想是根据不同问题自身特点,洞察问题本质,先弄清对哪些元素进行分类,再找出分类的规律,即所谓的构造抽屉,构造抽屉是应用抽屉原理的关键在介绍抽屉原理的应用之前,本文先用几个具体的例子来介绍几种常用的构造抽屉的方法21抽屉的构造211等分区间制造抽屉当问题的结论与区
8、间有关时,可等分某个区间,设计出若干个抽屉例1 求证:对于任给的正无理数及任意大的自然数,存在一个有理数,使得证明:把区间(0,1)进行等分,得个小区间由抽屉原理知,这些区间内的个数中,必有两个数落在某一个区间,从而这两个数的差的绝对值小于设,则由是正无理数得所以这个数中,必有2个数,不妨设为和,它们的差的绝对值小于,即设,则,即上述例子涉及区间问题,把区间(0,1)进行等分,得个小区间,自然就得到了个抽屉,而个数可以作为个物体,此处可以利用抽屉原理解决问题212分割图形构造抽屉在一个几何图形内有若干已知点,我们可以根据问题的要求把图形进行适当的分割,用这些分割成的图形作为抽屉,再对已知点进行
9、分类,集中对某一个或几个抽屉进行进行讨论,使问题得到解决例2 在边长为2米的正方形内,任意放入13个点求证:必有4个点,以它们为顶点的四边形的面积不超过1平方米 (1) (2)证明:把边长为2米的正方形分割成面积为1平方米的4个小正方形,如图1因为13=34+1,所以由抽屉原理知,至少有4个点落在同一个面积为1平方米的小正方形内(或边上),以这4个点为顶点的四边形的面积总小于或等于小正方形的面积,即以这4个点为顶点的四边形的面积不超过1平方米注:此例是通过分割图形构造抽屉 将正方形等分成4个矩形来制造抽屉也可以解决本题,如图2213利用“对称性”构造抽屉“对称性”是数学中常用的处理问题的一种方
10、法同样,在构造抽屉的过程中也可以利用“对称性”来解决问题,这种方法不易观察,需要不断的训练例3 九条直线中的每一条直线都把正方形分成面积比为2:3的两个四边形证明:这九条直线中至少有三条经过同一点 证明:如图,设是一条这样的这样的直线我们再画出这两个梯形的中位线,因这两个梯形有相等的高,所以他们的面积比应等于对应的中位线长的比,即等于(或者)因为点有确定的位置,它在正方形一对对边中点的连线上,并且,由几何上的对称性,这种点共有4个,即图中的已知的九条适合条件的分割直线中的每一条必须过这4点中的一点把当成4个抽屉,9条直线当成9个物体,即可看出必有3条分割直线经过同一个点正方形是个比较规则的图形
11、,在正方形中有很多对称关系,对解题减小了一点难度。214用整数性质制造抽屉当问题与整数性质有关时,我们可以用整数的性质,把题目中的数设计成一些抽屉,然后用抽屉原理去解(1)划分数组制造抽屉仔细观察题目中的数,如果题中数据具有一定的规律,可以划分数组构造抽屉例4 从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个数,由抽屉原理知,必有一个抽屉中要取出两个
12、数,即这50个数中必有两个数,它们之差为7本题的关键就是对这98个数进行合理分类,构造抽屉分类的原则是每个抽屉中的两个数只差是7,且抽屉的个数少于任取的数的个数(2)按同余类制造抽屉把所有整数按照除以某个自然数的余数分为类,叫做的剩余类或同余类,用0,1,2,m-1表示每一个类含有无穷多个数在研究与整除有关的问题时,常按同余类制造抽屉例5任意10个自然数中,总有两个数的差是9的倍数证明:要使两个自然数的差被9整除,必须使两个自然数被9除的余数相同于是我们考虑把自然数按除以9所得的余数0、1、2、3、8进行分类,也就是9个抽屉根据抽屉原理,任意10个自然数中,必有两个数除以9所得的余数相同因此这
13、两个数的差一定是9的倍数本题的特点比较明显,很容易想到利用同余类制造抽屉215利用染色制造抽屉我们可以把将物体放入盒子改为用中颜色中的每一种颜色对每一个物体染色此时抽屉原理断言,如果个物体用种颜色涂色,那么必然有两个物体被染成相同颜色抽屉原理的加强形式用染色的术语表述就是:如果个物体中的每一个物体被指定用种颜色中的一种染色,那么存在一个这样的,使得第种颜色的物体至少有个例6证明:任意6个人中一定有3个人互相认识或互相不认识 证明:我们用点依次表示这6个人两者互相认识的,他们之间用红色线段相连;两者互相不认识的用蓝色线段相连那么把从出发的5条线段,放入红,蓝两个抽屉中,根据抽屉原理知,一定至少有
14、3条线段同色不妨设线段,都为红色考虑线段,分以下两种情况:(1)若,都是蓝色,则三角形的三边同为蓝色,如图(3),这就是说三者互不认识(2)若,中至少有一条为红色,不妨设为,如图(4),则三角形的三边同为红色,即三者互相不认识 (3) (4)实线表示红色,虚线表示蓝色总之,任意6个人中一定有3个人互相认识或互相不认识本题属于利用染色制造抽屉,染色问题的实质是分类,只不过题目以涂色形式出现,显得直观而已216根据问题的需要制造抽屉 例7 能否在44的方格表的每个小方格中分别填上1、2、3这3个数之一,而使大正方形方格的每行、每列及对角线上的4个数字的和互不相同?请说明理由 证明:若每格都填数字“1”,则4个数字之和最小,其值为4;若每格都填数字“3”,则4个数字之和最大,其值为12因为从4到12之间共有个互不相同的值作为9个抽屉,而4行、4列及2条对角线上的各个数字之和共有个整数值,这样元素的个数比抽屉的个数多1,根据抽屉原理知,一定至少有两个数值属于同一个抽屉,即不可能使大正方形的每行、每列及对角线上的