第七讲抽屉原则

第七讲抽屉原则知识点拨抽屉原则,又称鸽巢原理,最早由德国数学家狄利克雷提出,并在有关数论问题中得到成功应用.抽屉原则,主要有下面几种表述形式：抽屉原则1：把n＋1个元素分为n个集合,那么必有一个集合含有两个以上的元素.抽屉原则2：把mn＋1个元素分为n个集合,那么必有一个集合中含有m＋1个或m＋1个以上的元素.抽屉原则3：把n个元素分为k个集合,那么必有一个集合中的元素个数≥kn,也必有一个集合中的元素个数≤kn.抽屉原则4：把无穷多个元素分为有限个集合,那么必有一个集合含有无穷多个元素.在运用抽屉原则时,所给定的元素具有任意性,也就是说,对元素的处理是任意的；所论证的问题,也只要求存在即可,不必一定是确定的.运用抽屉原则进行论证的命题,往往含有“至少含有”、“一定有”、“不少于”、“存在”、“必然有”等词语.利用抽屉原则的关键在于构造抽屉,从而把论证的命题的范围缩小,使问题变得简单明确,易于把握.一般说来,总是从问题自身的特点出发,先弄清所需要进行分类的元素特征.并指出规律,从而构造“抽屉”.利用抽屉原则解题的一般步骤是：第一步,根据元素的特征,构造抽屉(是运用抽屉原则解决问题的关键)；第二步,把元素放入所构造的抽屉；第三步,运用抽屉原则,对所论证的问题作出问题.赛题精讲(一)抽屉原则的一般运用例1证明：从1,2,3,…,11,12这12个数中任意取出7个数,其中至少有两个数之差为6.【解析】现将这12个数按下面的方式分成6组(1,7)；(2,8)；(3,9)；(4,10)；(5,11)；(6,12).任取7个数,根据抽屉原则1,至少有两个数来自同一个抽屉,这也就是说,至少有两个数之差是6.例2某校初中二年级共有210名学生,则至少有18名同学是在同一个月里出生的.【解析】由于一年有12个月,则可以将其试作12个抽屉,又因为210＝12×17＋6.因此根据抽屉原则2可知,至少有19名同学是在同一个月里出生的.例3从1,2,3,…,n中任取10个数,使得其中两个数比值大于32,小于23,那么n的最大值是91.【解析】由于任取10个数中有两个数在同一个抽屉里,显然最多构造9个抽屉.这9个抽屉中的每一个抽屉都含有1,2,3,…,n中的一些数,而且这些数必须满足每两个数的比值都在32和23之间,这9个抽屉,是：｛1｝；｛2,3｝；｛4,5,6｝；｛7,8,9,10｝；｛11,12,…,16｝；｛17,18,…,24,25｝；｛26,27,…,38,39｝；｛40,41,…,59,60｝；｛61,62,…,90,91｝.因此,n的最大值是91.例4从1到100这100个自然数中,任意取出51个数,其中一定存在两个数,这两个数中的一个是另一个的整数倍.【解析】由于任何一个自然数都可以表示成一个奇数与2n和乘积的形式,而且这种表示方法是惟一的.因此,我们可以按下面的方法来构造50个抽屉：｛1,1×2,1×22,…,1×23,1×26｝；｛3,3×2,3×22,3×23,3×24,3×25｝；｛5,5×2,5×22,5×23,5×24｝；……；｛49,49×2｝；｛51｝；｛53｝；……；｛99｝.于是从这50个抽屉中任取51个数,根据抽屉原则,其中一定存在至少两个数属于同一个抽屉,即命题得证.(二)同余与抽屉原则当任何一个正整数m被另一个正整数n相除时,总可以写成m＝nq＋r的形式(其中,q称为商,r称为余数.当n整除m时,r＝0；当n不能整除m时,r为小于n的正整数,也就是说,这里的0≤rn.)于是,我们可以根据m被n所除的余数的不同情况来构造抽屉,进而运用抽屉原则来解决一些与之相关的命题.这时,我们根据整数被某一整数n相除所得的余数相同与否进行分类,从而构造抽屉.如果将所有整数被n所除余数相同(习惯上我们称之为同余)的数归为一类,这样便可以构造出n个不同的抽屉,而且任一整数,它必然在这n类数(或n个抽屉)中的某一个之内.同时,如果所讨论的对象超出了n个,那么至秒有两个数被n所除的余数相同；此外,这样的两个数的差也一定能被n整除.下面,我们给出一些运用同余来构造抽屉并解决实际问题的例子.例5对于任意给定的n个自然数,其中一定存在若干个数,它们的和是n的倍数.【解析】我们假设n个自然数是a1,a2,a3,…,an,而且考虑如下形式的和：S1＝a1,S2＝a1＋a2,…,Sn＝a1＋a2＋a3＋…＋an.如果在这n个和S1,S2,…,Sn中,存在一个数是n的倍数,则原命题成立.如果在n个和S1,S2,…,Sn中,没有n的倍数的数,那么它们被n除所得的余数只可能是1,2,…,n－1共n－1种情况.但由于S1,S2,…,Sn共有n个数,从而根据抽屉原则,必然存在两个数它们被n除的余数相同.不妨设在这两个数是Sk与Sj(kj),那么这两个数的差Sk－Sj一定是n的倍数.也就是说,有：Sk－Sj＝(a1＋a2＋a3＋…＋aj＋aj＋aj＋2＋…＋ak)－(a1＋a2＋a3＋…＋aj)＝aj＋1＋aj＋2＋…＋ak,这表明：这时从第j＋1个数起,一直到第k个数.它们的和正好是n的倍数.例6如果三个完全平方数之和能被9整除,那么可以从这三个数中选出两个来,使得这两个完全平立数之差也能被9整除.【解析】下面我们先来讨论任意的完全平方数被9除的余数.根据同余理论,我们知道,任何一个整数总可以表示成：9k,9k±1,9k±2,9k±3及9k±4这九种情况中的一种.现在将这九种情况分别平方,于是可得：(9k)2＝9×9k2＋0；(9k±1)2＝9(9k2±2k)＋1；(9k±2)2＝9(9k2±4)＋4；(9k±3)2＝9(9k2±6k＋1)＋0及(9k±4)2＝9(9k2±8k＋1)＋7.可见,任何一个完全平方数被9除的余数只可能是0,1,4,7这四种情况之一.另一方面,由于所选的三个完全平方数之和能被9整除,因此这三个数的余数之和也一定能被9整除；而从0、1、4、7这四个数中选出三个,其和要能被9整除,只可能是｛0,0,0｝、｛1,1,7｝、｛1,4,4｝或｛4,7,7｝这四种情况中的一种.而在上面这四种可能的余数组合中,每一组都至多有两种余数,因此至少有两个完全平方数被所9除的余数相同,从而这两个余数相同的完全平方数之差就一定能被9整除.(三)图形分割与抽屉原则一些与几何图形有关的数学命题,有时可以先根据图形的特点“适应”地将其分割,然后再利用分割而成的图形来构造“抽屉”,最后在此基础上再利用抽屉原则来解决这些问题.例7如果在长度为1的线段上有n＋1个点,那么其中必有两点,它们之间的距离不超过n1.【解析】这里,我们可以将这条线段n等分,并把等分后的每一份看成一个“抽屉”,那么这里的n＋1个点至少有两个点一定在等分后的“抽屉”中,也就是说,至少有两个点在一个长度为n1的小线段内,当然这两个点之间的距离就一定不会超过n1.命题得证.例8在边长为1的正方形内任给五点,则必有两点,它们之间的距离不大于22.【解析】由抽屉原则,显然我们应将这五点放入四个合适的抽屉中,且每个抽屉中任两个点的距离都不超过22.于是我们可以通过连接正方形两组对边的中点,从而将其分割成长度为21的四个小正方形来构造“抽屉”.这样,任意的五个点中必有两个点一定在同一个小正方形内,如图1所示,而每一个小正方形内两点间的最大距离就是22.因此,在同一个小正方形内的两个点的距离一定不大于22.于是命题得证.这里,特别值得一提的是,并不是任意与几何图形有关的命题在构造抽屉时都一定得将图形等分(见下面的例9).事实上,就本例来讲,如果将原正方形的两条对角线连接起来,也将原正方形四图1等分了,但是对于原命题的证明是没有任何原助的.因为这时如果两点恰好位于正方形的相邻的两个顶点处,这样的两个点也可以在一个抽屉内,但是这两个点的距离却不大于22,显然与原命题的要求不符.例9证明：如果在边长分别为3和4的矩形中有任意6个点,那么一定可以选出两个点,它们之间的距离不大于5.【解析】根据抽屉原则,显然需要将3×4的矩形分割成五个“抽屉”,每个抽屉中任意两个点的最大距离不超过5.而且大家都容易将5与边长为1×2的矩形联系起来,因为这里矩形的对角线长度是5.但是这样却把3×4的矩形分割成了六个“抽屉”,显然这是不符合题目要求的.可见,构造的抽屉是要满足一定“尺寸”的.我们可以在此基础上适当改造“抽屉”的形状,如图2,可以将图中的点A、B、K、J、I这五点,B、C、D、L、K这五点,D、E、F、L这四点,F、G、J、K、L这五点以及G、H、I、J这四点所组成的五边形或四边形为“抽屉”而构造出五个抽屉,而且这五个“抽屉”中的任何两个点之间的最大距离都不超过5.根据抽屉原则,该命题得证.这是“非平均分割”而构造“抽屉”的一个非常有说明力的例子.可见,对于通过分割图形来构造“抽屉”并运用抽屉原则来解决问题时,恰当的构造抽屉是多么重要；同时也说明在构造抽屉时,并不一定是将所给出的图形等分.针对训练A组1.一个口袋内有100个球,其中有红球28个,绿球20个,黄球12个,蓝球20个,白球10个,黑球10个.从袋中任意取球,如果要求一次取出的球中至少有15个球的颜色相同,那么至少要从袋中取出多少个球？2.从1到100这100个自然数中至少要取出多少个数,才能保证一定存在两个数是互质的.3.有100人聚会,其中每一个人都认识这100人中的50人.现请你证明：可以从中选出4人,当这4人坐成一个圆圈时,每个人都与他所认识的人邻坐.EDCBAKIHJLGF图24.一定存在这样的正整数,它的各位数字由0或1构成,并且是201的倍数.5.证明：在任意给定的100个整数中,一定存在两个数,它们的和或差是100的倍数.B组1.证明：在21－1,22－1,23－1,…,2n－1－1这n－1个数中,至少有一个数能被n整除(其中n为大于1的奇数).2.九条直线中的每一条直线都把正方形分成面积比为2：3的两个四边形.证明：这九条直线中至少有三条经过同一点.3.对于平面上给定的25个点,如果其中任何3个点中都有某两个点的距离小于1,那么在这些给定的点中,一定可以找到13个点,这13个点都位于一个半径为1的圆内.4.我们把在直解坐标平面内横坐标都是整数的点称为整点.证明：对于平面内任意给定的五个整点,其中一定存在两个整点,这两个点的连线的中点仍为整点.5.在直角坐标系中,我们考虑上面所定义的整点(x,y),其中1≤x≤16,1≤y≤9,显然共有114个整点.如果将114个点任意地染成红、黄、蓝三色,那么一定存在一个长方形,它的边平形于坐标轴,且它的顶点颜色相同.