抽屉原则_竞赛联赛知识_高中频道-查字典高考网
 
请输入您要查询的关键词

抽屉原则

发布时间: 2009-08-31   来源:查字典高考网

大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉里,更一般地说,只要被放置的苹果数比抽屉数目大,就一定会有两只或更多只的苹果放进同一个抽屉,可不要小看这一简单事实,它包含着一个重要而又十分基本的原则抽屉原则.

1. 抽屉原则有几种最常见的形式

原则1 如果把n+k(k1)个物体放进n只抽屉里,则至少有一只抽屉要放进两个或更多个物体:

原则本身十分浅显,为了加深对它的认识,我们还是运用反证法给予证明;如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k1),这不可能.

原则虽简单.巧妙地运用原则却可十分便利地解决一些看上去相当复杂、甚至感到无从下手的总是,比如说,我们可以断言在我国至少有两个人出生的时间相差不超过4秒钟,这是个惊人的结论,该是经过很多人的艰苦劳动,统计所得的吧!不,只须我们稍动手算一下:

不妨假设人的寿命不超过4万天(约110岁,超过这个年龄数的人为数甚少),则

10亿人口安排在8亿6千4百万个抽屉里,根据原则1,即知结论成立.

下面我们再举一个例子:

例1 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.

解 从三种玩具中挑选两件,搭配方式只能是下面六种:

(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)

把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原则1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.

原则2 如果把mn+k(k1)个物体放进n个抽屉,则至少有一个抽屉至多放进m+1个物体.证明同原则相仿.若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.

原则1可看作原则2的物例(m=1)

例2正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.

证明把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=22+2,根据原则二,至少有三个面涂上相同的颜色.

例3 把1到10的自然数摆成一个圆圈,证明一定存在在个相邻的数,它们的和数大于17.

证明 如图12-1,设a1,a2,a3,,a9,a10分别代表不超过10的十个自然数,它们围成一个圈,三个相邻的数的组成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5),,(a9,a10,a1),(a10,a1,a2)共十组.现把它们看作十个抽屉,每个抽屉的物体数是a1+a2+a3,a2+a3+a4,a3+a4+a5,a9+a10+a1,a10+a1+a2,由于

(a1+a2+a3)+(a2+a3+a4)++(a9+a10+a1)+(a10+a1+a2)

=3(a1+a2++a9+a10)

=3(1+2++9+10)

根据原则2,至少有一个括号内的三数和不少于17,即至少有三个相邻的数的和不小于17.

原则1、原则2可归结到期更一般形式:

原则3把m1+m2++mn+k(k1)个物体放入n个抽屉里,那么或在第一个抽屉里至少放入m1+1个物体,或在第二个抽屉里至少放入m2+1个物体,,或在第n个抽屉里至少放入mn+1个物体.

证明假定第一个抽屉放入物体的数不超过m1个,第二个抽屉放入物体的数不超过m2个,,第n个抽屉放入物体的个数不超过mn,那么放入所有抽屉的物体总数不超过m1+m2++mn个,与题设矛盾.

例4 有红袜2双,白袜3双,黑袜4双,黄袜5双,蓝袜6双(每双袜子包装在一起)若取出9双,证明其中必有黑袜或黄袜2双.

证明 除可能取出红袜、白袜3双外.还至少从其它三种颜色的袜子里取出4双,根据原理3,必在黑袜或黄袜、蓝袜里取2双.

上面数例论证的似乎都是存在、总有、至少有的问题,不错,这正是抽屉原则的主要作用.需要说明的是,运用抽屉原则只是肯定了存在、总有、至少有,却不能确切地指出哪个抽屉里存在多少.

2. 制造抽屉是运用原则的一大关键

首先要指出的是,对于同一问题,常可依据情况,从不同角度设计抽屉,从而导致不同的制造抽屉的方式.

例5 在边长为1的正方形内,任意给定13个点,试证:其中必有4个点,以此4点为顶点的四边开面积不超过(假定四点在一直线上构成面积为零的四边形).

证明如图12-2把正方形分成四个相同的小正方形.

因13=34+1,根据原则2,总有4点落在同一个小正方形内(或边界上),以此4点为顶点的四边形的面积不超过小正方形的面积,也就不超过整个正方形面积的.

事实上,由于解决问题的核心在于将正方形分割成四个面积相等的部分,所以还可以把正方形按图12-3(此处无图)所示的形式分割.

合理地制造抽屉必须建立在充分考虑问题自身特点的基础上.

例6 在一条笔直的马路旁种树,从起点起,每隔一米种一棵树,如果把三块爱护树木的小牌分别挂在三棵树上,那么不管怎样挂,至少有两棵挂牌的树之间的距离是偶数(以米为单位),这是为什么?

解如图12-4(设挂牌的三棵树依次为A、B、C.AB=a,BC=b,若a、b中有一为偶数,命题得证.否则a、b均为奇数,则AC=a+b为偶数,命题得证.

下面我们换一个角度考虑:给每棵树上编上号,于是两棵树之间的距离就是号码差,由于树的号码只能为奇数和偶数两类,那么挂牌的三棵树号码至少有两个同为奇数或偶数,它们的差必为偶数,问题得证.

后一证明十分巧妙,通过编号码,将两树间距离转化为号码差.这种转化的思想方法是一种非常重要的数学方法

例7 从自然数1,2,3,99,100这100个数中随意取出51个数来,求证:其中一定有两个数,,它们中的一个是另一个的倍数.

分析设法制造抽屉:(1)不超过50个;(2)每个抽屉的里的数(除仅有的一个外),其中一个数是另一个数的倍数,一个自然数的想法是从数的质因数表示形式入手.

解设第一个抽屉里放进数:1,12,122,123,124,125,126;

第二个抽屉时放进数:3,32,322,323,324,325;

第三个抽屉里放进数:5,52,522,523,524;

第二十五个抽屉里放进数:49,492;

第二十六个抽屉里放进数:51.

第五十个抽屉里放进数:99.

那么随意取出51个数中,必有两个数同属一个抽屉,其中一个数是另一个数的倍数.

制造抽屉并非总是一帆风顺的,有时要边制造边调整、改进.

例8 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数.

分析注意到这些数队以10的余数即个位数字,以0,1,,9为标准制造10个抽屉,标以[0],[1],,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数.

3. 较复杂的问题须反复地运用抽屉原则,将复杂问题转化为简单问题.

例9以(x,y,z)表示三元有序整数组,其中x、y、z为整数,试证:在任意七个三元整数组中,至少有两个三元数组,它们的x、y、z元中有两对都是奇数或都是偶数.

分析 设七个三元素组为A1(x1,y1,z1)、A2(x2,y2,z2)、、A7(x7,y7,z7).现在逐步探索,从x元开始,由抽屉原则,x1,x2,,x7这七个数中,必定有四个数具有相同的奇偶性,不妨设这四个数是x1,x2,x3,x4且为偶数,接着集中考虑A1、A2、A3、A4这四组数的y元,若比如y1,y2,y3,y4中有两个是偶数,则问题已证,否则至多有一个是偶数,比如y4是偶数,这时我们再来集中考虑A1、A2、A3的z元.在z1,z2,z3中,由抽屉原则必有两个数具有相同的奇偶性,如z1、z2,这时无论它们是奇数,还是偶数,问题都已得到证明.

下面介绍一个著名问题.

例10 任选6人,试证其中必有3人,他们互相认识或都不认识.

分析 用A、B、C、D、E、F表示这6个人,首先以A为中心考虑,他与另外五个人B、C、D、E、F只有两种可能的关系:认识或不认识,那么由抽屉原则,他必定与其中某三人认识或不认识,现不妨设A认识B、C、D三人,当B、C、D三人都互不认识时,问题得证;当B、C、D三人中有两人认识,如B、C认识时,则A、B、C互相认识,问题也得证.

本例和上例都采用了舍去保留、化繁为简、逐步缩小考虑范围的方法.

例11a,b,c,d为四个任意给定的整数,求证:以下六个差数

b-a,c-a,d-a,c-b,d-b,d-c的乘积一定可以被12整除.

证明 把这6个差数的乘积记为p,我们必须且只须证明:3与4都可以整除p,以下分两步进行.

第一步,把a,b,c,d按以3为除数的余数来分类,这样的类只有三个,故知a,b,c,d中至少有2个除以3的余数相同,例如,不妨设为a,b,这时3可整除b-a,从而3可整除p.

第二步,再把a,b,c,d按以4为除数的余数来分类,这种类至多只有四个,如果a,b,c,d中有二数除以4的余数相同,那么与第一步类似,我们立即可作出4可整除p的结论.

设a,b,c,d四数除以4的余数不同,由此推知,a,b,c,d之中必有二个奇数(不妨设为a,b),也必有二个偶数(设为c,d),这时b-a为偶数,d-c也是偶数,故4可整除(b-a)(d-c),自然也可得出4可整除p.

如果能进一步灵活运用原则,不仅制造抽屉,还根据问题的特征,制造出放进抽屉的物体,则更可收到意想不到的效果.

例12 求证:从任意n个自然数a1,a2,,an中可以找到若干个数,使它们的和是n的倍数.

分析以0,1,,n-1即被n除的余数分类制造抽屉的合理的,但把什么样的数作为抽屉里的物体呢?扣住和,构造下列和数:

S1=a1,

S2=a1+a2,

S=a1+a2+a3,

Sn=a1+a2++an,

其中任意两个和数之差仍为和数,若他们之中有一是n的倍数,问题得证,否则至少有两个数被n除余数相同,则它们的差即它们中若干数(包括1个)的和是n的倍数,问题同样得证.

例子3(北京1990年高一竞赛)910瓶红、蓝墨水,排成130行,每行7瓶,证明:不论怎样排列,红蓝墨水瓶的颜色次序必定出现下述两种情况之一种:

(1)至少有三行完全相同;

(2)至少有两组(四行)每组的两行完全相同.

解910瓶红、蓝墨水排成130行,每行7瓶,对一行来说,每个位置上有红蓝两种可能,因此,一行的红、蓝墨水排法有27=128种,对每一种不同排法设为一种行式,共有128种行式.

现有130行,在其中任取129行,依抽屉原则知,必有两行A、B行式相同.

除A、B外余下128行,若有一行P与A行式相同,知满足(1)至少有三行A、B、P完全相同,若在这128行中设直一行5A行或相同,那么这128行至多有127种行式,依抽屉原则,必有两行C、D具有相同行式,这样便找到了(A、B),(C、D)两组(四行),且两组两行完全相同.

练习十二

1. 一个篮球运动员在15分钟内将球投进篮圈20次,证明总有某一分钟他至少投进两次.

2. 有黑、白、黄筷子各8只,不用眼睛看,任意地取出筷子来,使得至少有两双筷子不同色,那么至少要取出多少只筷子才能做到?

3. 证明:在1,2,3,,10这十个数中任取六个数,那么这六个数中总可以找到两个数,其中一个是另一个的倍数.

4. 证明:任意502个整数中,必有两个整数的和或差是998的倍数.

5. 任意写一个由数字1,2,3组成的30位数,从这30位数任意截取相邻三位,可得一个三位数,证明:在从各个不同位置上截得的三位数中至少有两个相等.

6. 证明:把任意10个自然数用适当的运算符号连接起来,运算的结果总能被1890整除.

7. 七条直线两两相交,所得的角中至少有一个角小于26.

8. 用2种颜色涂3行9列共27个小方格,证明:不论如何涂色,其中必至少有两列,它们的涂色方式相同.

9. 用2种颜色涂55共25个小方格,证明:必有一个四角同色的矩形出现.

10. 求证存在形如1111的一个数,此数是1987的倍数.

练习十二

1.15分钟里在每一分钟看作一个抽屉,20次投篮看作20个物体,根据原理一即得.

2.至少要取11只筷子.因为11只筷子中必有一双筷子同色,不妨设它是黄色,则黑色或白色的筷子至少有3只,其中必有一双同色,即黑色或白色,故取11只筷子足以保证成功.但少于11只不行,如取10只筷子,闵可能出现8只黄色,黑白各一只,不合要求.

3.将10个数分成5组:(1,7),(2,6),(3,9),(4,8),(5,10).任取六个数必有两个落入同一组,而同组二数中一数是另一数的倍数.

4.每个整数被998除,余数必是0,1,2,,997中的一个.把这998个余数制造为(0),(1,997),(2,996),,(497,501),(498),(499),(500)共501个抽屉,把502个整数按被998除的余数大小分别放入上述抽屉,必有两数进入同一抽屉.若余数相同,那么它们的差是998的倍数,否则和为998的倍数.

5.从各种位置上截得的三位数有28个,但由1,2,3组成的不同三位数有333=27个,故有两个截得的三位数相同.

6.1890=23579.将10个数记为x1,x2,,x9,x10.10个数中至少有两个被9除余数相同,设为x1,x2则x1-x2可被9整除.同样剩下8个数中有两个数的差可被7整除,记为x3-x4,剩下6个数中有两个数的差可被5整除,记为x5-x6,剩下4个数中有两个数的差可被3整除,记为x7-x8.剩下两数x9,x10,若有一数为偶数,则x9,x10可被2整除,否则x9-x10可被2整除.故乘积(x1-x2)(x3-x4)(x5-x6)(x7-x8)x9x10与(x1-x2)(x3-x4)(x5-x6)(x7-x8)(x9-x10)二者之一必可被1890整除.

7.任选一点P,过P点分别作各线的平行线,则它们把一周角分成14个彼此相邻的角,其中至少有一个角小于26.

8.用两种颜色涂13的小方格共有8种方法.现有9列,由抽屉原则,必有两列涂法一样.

9.设两种颜色为红、蓝,考察第一行的涂色.必有三格同色,不妨设为红色,且在左边三列.现考察左边三列,若下面四行中某一行有两格同为红色,则出现四角同红色矩形,否则每行仅可能一格染红色,从而四行中必有二行左边三列中有两列同染蓝色,从而得到四角同为蓝色的矩形.

10.考虑1,11,共1987个数,其中必有一个是1987的倍数,否则必有两数被1987除余数相同,其差

是1987的倍数.但10i与1987没有除1外的因数,故是1987倍数导致矛盾.

点击显示
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关推荐
  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •