抽屉原理的典型问题

1、奥数探秘：奥数之抽屉原理桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，有的抽屉可以放一个，有的可以放两个，有的可以放五个，但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。抽屉原理的一般含义为： “如果每个抽屉代表一个集合， 每一个苹果就可以代表一个元素， 假如有 n+1 或多于 n+1 个元素放到n 个集合中去，其中必定至少有一个集合里至少有两个元素。”抽屉原理有时也被称为鸽巢原理（ “如果有五个鸽子笼，养鸽人养了 6 只鸽子，那么当鸽子飞回笼中后，至少有一个笼子中装有2 只鸽子” ） 。它是德国数学家狄利克雷首先明确的提出来并用以证明一

2、些数论中的问题，因此， 也称为狄利克雷原理。它是组合数学中一个重要的原理。一 . 抽屉原理最常见的形式原理 1 把多于 n 个的物体放到n 个抽屉里，则至少有一个抽屉里有2 个或 2 个以上的物体。证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n,而不是题设的n+k（k > 1）,这不可能.原理2把多于mn（m乘以n）个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。证明（反证法）:若每个抽屉至多放进m个物体，那么n个抽屉至多放进 mn个物体，与题设不符，故不可能.原理 1 2 都是第一抽屉原理的表述第二抽屉原理：把 （mn-1） 个物体放

3、入n 个抽屉中，其中必有一个抽屉中至多有（m 1）个物体。证明（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能二 . 应用抽屉原理解题抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。例 1 ： 400 人中至少有两个人的生日相同.解：将一年中的366 天视为 366 个抽屉，400 个人看作400 个物体，由抽屉原理1 可以得知：至少有两人的生日相同.又如：我们从街上随便找来13 人，就可断定他们中至少有两个人属相相同.“从任意 5 双手套中任取6 只，其中至少有2 只恰为一双手套。”“从数 1， 2， .

4、 ， 10 中任取 6 个数，其中至少有2个数为奇偶性不同。”例2：幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道理.解：从三种玩具中挑选两件，搭配方式只能是下面六种：（ 兔、兔 ） ， （ 兔、熊猫） ， （ 兔、长颈鹿 ） ， （ 熊猫、熊猫） ， （ 熊猫、长颈鹿） ， （ 长颈鹿、长颈鹿） 。把每种搭配方式看作一个抽屉，把7 个小朋友看作物体，那么根据原理1 ，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式，选的玩具相同.上面数例论证的似乎都是“存在”、 “总有”

5、、“至少有”的问题，不错，这正是抽屉原则的主要作用.（ 需要说明的是，运用抽屉原则只是肯定了“存在”、 “总有”、 “至少有”，却不能确切地指出哪个抽屉里存在多少 .）抽屉原理虽然简单，但应用却很广泛，它可以解答很多有趣的问题，其中有些问题还具有相 当的难度。下面我们来研究有关的一些问题。（ 一 ） 整除问题把所有整数按照除以某个自然数m的余数分为m类，叫做m的剩余类或同余类，用0,1 , 2，m-1表示.每一个类含有无穷多个数，例如1中含有1,m+1, 2m+1, 3m+1,.在研究与整除有关的问题时，常用剩余类作为抽屉. 根据抽屉原理，可以证明：任意n+1 个自然数中，总有两个自然数的差是

6、n 的倍数。例 1 证明：任取8 个自然数，必有两个数的差是7 的倍数。分析与解答在与整除有关的问题中有这样的性质，如果两个整数a、b,它们除以自然数m的余数相同，那么它们的差 a-b是m的倍数.根据这个性质，本题只需证明这8个自然数中有 2 个自然数，它们除以7 的余数相同. 我们可以把所有自然数按被7 除所得的7 种不同的余数0、 1、 2、 3、 4、 5、 6 分成七类. 也就是 7 个抽屉 . 任取 8 个自然数，根据抽屉原理， 必有两个数在同一个抽屉中，也就是它们除以7 的余数相同，因此这两个数的差一定是7 的倍数。例 2：对于任意的五个自然数，证明其中必有3 个数的和能被3 整除

7、 .证明.任何数除以3所得余数只能是0, 1, 2,不妨分别构造为 3个抽屉：0 ， 1 ， 2若这五个自然数除以3 后所得余数分别分布在这3 个抽屉中（ 即抽屉中分别为含有余数为 0,1,2 的数 ），我们从这三个抽屉中各取1 个 （如 15中取 3,4,5） ，其和 （3+4+5=12） 必能被 3 整除 .若这 5 个余数分布在其中的两个抽屉中，则其中必有一个抽屉，包含有3 个余数（抽屉原理 ） ，而这三个余数之和或为0，或为3，或为6，故所对应的3 个自然数之和是3 的倍数.若这 5 个余数分布在其中的一个抽屉中，很显然，必有3 个自然数之和能被3整除 .例2'：对于任意的11

8、个整数，证明其中一定有 6个数，它们的和能被 6整除.证明：设这11个整数为：al, a2, a3all又6=2X3先考虑被3 整除的情形由例 2 知，在 11 个任意整数中，必存在：3|a1+a2+a3 ，不妨设a1+a2+a3=b1;同理，剩下的8 个任意整数中，由例2，必存在：3 | a4+a5+a6. 设 a4+a5+a6=b2;同理，其余的5 个任意整数中，有：3|a7+a8+a9 ，设：a7+a8+a9=b3再考虑b1 、 b2、 b3 被 2 整除 .依据抽屉原理，b1、 b2、 b3 这三个整数中，至少有两个是同奇或同偶，这两个同奇（ 或同偶 ） 的整数之和必为偶数. 不妨设

9、2|b1+b2则： 6|b1+b2 ，即：6|a1+a2+a3+a4+a5+a6，任意11个整数，其中必有 6个数的和是6的倍数.例 3：任意给定7 个不同的自然数，求证其中必有两个整数，其和或差是10 的倍数 .分析：注意到这些数队以10的余数即个位数字， 以0, 1,，9为标准制造10个抽屉， 标以0 , 1,，9.若有两数落入同一抽屉， 其差是10的倍数，只是仅有7个自然数， 似不便运用抽屉原则，再作调整：6 ， 7 ， 8 ， 9 四个抽屉分别与4 ， 3 ， 2 ， 1合并，则可保证至少有一个抽屉里有两个数，它们的和或差是10 的倍数 .（二 ） 面积问题例： 九条直线中的每一条直线

10、都将正方形分成面积比为2:3 的梯形，证明： 这九条直线中至少有三条经过同一点.证明：如图，设直线 EF将正方形分成两个梯形，作中位线 MN由于这两个梯形的高相 等，故它们的面积之比等于中位线长的比，即 |MH|:|NH| 。于是点H有确定白位置（它在正方形一对对边中点的连线上，且|MH|:|NH|=2:3）. 由几何上的对称性，这种点共有四个（即图中的H、J、I、K）.已知的九条适合条件的分割直线中的每一条必须经过H、J、I、K这四点中的一点.把H、J、I、K看成四个抽屉，九条直线当成 9个物体，即可得出必定有 3条 分割线经过同一点.（三 ）染色问题例 1 正方体各面上涂上红色或蓝色的油漆

11、（ 每面只涂一种色） ， 证明正方体一定有三个面颜色相同.证明：把两种颜色当作两个抽屉，把正方体六个面当作物体，那么 6=2X 2+2,根据原理二，至少有三个面涂上相同的颜色.例 2 有 5 个小朋友，每人都从装有许多黑白围棋子的布袋中任意摸出3 枚棋子 . 请你证明，这 5 个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。分析与解答首先要确定3 枚棋子的颜色可以有多少种不同的情况，可以有：3 黑， 2 黑1 白， 1 黑 2 白， 3 白共4 种配组情况，看作4 个抽屉 . 根据抽屉原理，至少有两个小朋友摸出的棋子的颜色在同一个抽屉里，也就是他们所拿棋子的颜色配组是一样的。例 3：假设

12、在一个平面上有任意六个点，无三点共线，每两点用红色或蓝色的线段连起来，都连好后，问你能不能找到一个由这些线构成的三角形，使三角形的三边同色?解：首先可以从这六个点中任意选择一点，然后把这一点到其他五点间连五条线段，如图，在这五条线段中，至少有三条线段是同一种颜色，假定是红色，现在我们再单独来研究这三条红色的线。这三条线段的另一端或许是不同颜色，假设这三条线段（ 虚线） 中其中一条是红色的， 那么这条红色的线段和其他两条红色的线段便组成了我们所需要的同色三角形，如果这三条线段都是蓝色的，那么这三条线段也组成我们所需要的同色三角形。因而无论怎样着色，在这六点之间的所有线段中至少能找到一个同色三角形

13、。例3'（六人集会问题）证明在任意6个人的集会上，或者有 3个人以前彼此相识，或者有三个人以前彼此不相识。”例 3”：17 个科学家中每个人与其余16 个人通信，他们通信所讨论的仅有三个问题，而任两个科学家之间通信讨论的是同一个问题。证明： 至少有三个科学家通信时讨论的是同一个问题。解：不妨设A是某科学家，他与其余 16位讨论仅三个问题，由鸽笼原理知，他至少与其中的6位讨论同一问题。设这 6位科学家为B, C, D, E, F, G,讨论的是甲问题。若这 6 位中有两位之间也讨论甲问题，则结论成立。否则他们6 位只讨论乙、丙两问题。这样又由鸽笼原理知 B至少与另三位讨论同一问题，不妨设

14、这三位是C, D, E,且讨论的是乙问题。若 C， D， E 中有两人也讨论乙问题，则结论也就成立了。否则，他们间只讨论丙问题，这样结论也成立。三 . 制造抽屉是运用原则的一大关键例1从2、4、6、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34。分析与解答我们用题目中的15 个偶数制造8 个抽屉：凡是抽屉中有两个数的，都具有一个共同的特点：这两个数的和是34。现从题目中的15 个偶数中任取9个数，由抽屉原理（因为抽屉只有8个 ），必有两个数在同一个抽屉中. 由制造的抽屉的特点，这两个数的和是34。例2:从1、2、3、4、19、20这20个自然数中，至少任选几个数，就可以保证其中

15、一定包括两个数，它们的差是12。分析与解答在这20个自然数中，差是12的有以下8对：20, 8 , 19, 7 , 186, 17, 5 , 16 , 4 , 15 , 3 , 14, 2 , 13, 1。另外还有4个不能配对的数9 , 10 , 11 , 12,共制成12个抽屉（每个括号看成一个抽屉）. 只要有两个数取自同一个抽屉，那么它们的差就等于12，根据抽屉原理至少任选13个数，即可办到（取12个数：从12个抽屉中各取一个数（例如取1, 2, 3,，12） ，那么这12 个数中任意两个数的差必不等于12）。例3：从 1 到 20这 20 个数中，任取11 个数，必有两个数，其中一个数是

16、另一个数的倍数。分析与解答根据题目所要求证的问题，应考虑按照同一抽屉中，任意两数都具有倍数关系的原则制造抽屉. 把这 20 个数按奇数及其倍数分成以下十组，看成 10 个抽屉 （ 显然， 它们具有上述性质） ：1 , 2, 4, 8, 16 ,3,6, 12 , 5 ,10, 20 , 7 , 14 , 9 , 18 , 11 , 13 , 15 , 17 , 19。从这 10 个数组的20 个数中任取11 个数，根据抽屉原理，至少有两个数取自同一个抽屉 . 由于凡在同一抽屉中的两个数都具有倍数关系，所以这两个数中，其中一个数一定是另一个数的倍数。例4： 某校校庆，来了 n 位校友，彼此认识的

17、握手问候. 请你证明无论什么情况，在这n个校友中至少有两人握手的次数一样多。分析与解答共有n 位校友， 每个人握手的次数最少是0 次， 即这个人与其他校友都没有握过手 ; 最多有 n-1 次， 即这个人与每位到会校友都握了手. 然而， 如果有一个校友握手的次数是 0 次，那么握手次数最多的不能多于n-2 次 ; 如果有一个校友握手的次数是n-1 次，那么握手次数最少的不能少于1次.不管是前一种状态 0、1、2、n-2,还是后一种状态1、2、3、n-1 ,握手次数都只有 n-1种情况.把这n-1种情况看成n-1个抽屉，到会的n 个校友每人按照其握手的次数归入相应的“抽屉”， 根据抽屉原理，至少有

18、两个人属于同一抽屉，则这两个人握手的次数一样多。在有些问题中， “抽屉”和“物体”不是很明显的， 需要精心制造“抽屉”和“物体”.如何制造“抽屉”和“物体”可能是很困难的，一方面需要认真地分析题目中的条件和问题，另一方面需要多做一些题积累经验。抽屉原理把八个苹果任意地放进七个抽屉里，不论怎样放，至少有一个抽屉放有两个或两个以上的苹果。 抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。形式一：证明：设把 n+1个元素分为n个集合A1, A2,，An,用al

19、, a2,，an表 示这 n 个集合里相应的元素个数，需要证明至少存在某个ai 大于或等于2（用反证法）假设结论不成立，即对每一个ai都有ai<2 ,则因为ai是整数，应有ai < 1,于是有：a1+a2+anw 1+1+1=n形式二：设把n?m+1个元素分为n个集合A1, A2,，An,用al, a2,，an表示这 n个集合里相应的元素个数，需要证明至少存在某个ai大于或等于m+%用反证法）假设结论不成立，即对每一个ai 都有 aia1+a2+anw m+m +m=n?mn个m这与题设相矛盾。所以，至少有存在一个ai >m+1高斯函数：对任意的实数x,冈表示“不大于x的最大

20、整数”.例如：3.5=3 , 2.9=2 ，-2.5=-3 ，=7 ,一般地，我们有：x <x<x+1形式三：证明：设把 n个元素分为k个集合A1, A2,，Ak,用al, a2,，ak表示 这 k 个集合里相应的元素个数，需要证明至少存在某个ai 大于或等于n/k 。 （ 用反证法）假设结论不成立，即对每一个ai 都有 ai<n/k ，于是有：a1+a2+ +ak<n/k+n/k+n/k =k?n/k< k?（n/k）=nk 个n/ka1+a2+ak形式四：证明：设把q1+q2+qn-n+1个元素分为n个集合A1, A2,，An,用al ,i ，使得 ai 大于

21、或a2,，an表示这n个集合里相应的元素个数，需要证明至少存在某个等于 qi 。 （ 用反证法） 假设结论不成立，即对每一个ai 都有 ai所以，假设不成立，故必有一个i,在第i个集合中元素个数 ai >qi形式五：证明： （ 用反证法） 将无穷多个元素分为有限个集合，假设这有限个集合中的元素的个数都是有限个，则有限个有限数相加，所得的数必是有限数，这就与题设产生矛盾，所以，假设不成立，故必有一个集合含有无穷多个元素。例题 1： 400 人中至少有两个人的生日相同. 分析： 生日从 1 月 1 日排到 12 月 31 日， 共有 366 个不相同的生日，我们把 366 个不同的生日看作3

22、66 个抽屉， 400 人视为 400 个苹果，由表现形式1 可知，至少有两人在同一个抽屉里，所以这400 人中有两人的生日相同.解：将一年中的366 天视为 366 个抽屉，400 个人看作400 个苹果，由抽屉原理的表现形式 1 可以得知：至少有两人的生日相同.例题2：任取5个整数，必然能够从中选出三个，使它们的和能够被3 整除 .证明：任意给一个整数，它被3 除，余数可能为0， 1， 2，我们把被3 除余数为0， 1，2 的整数各归入类r0 ， r1 ， r2. 至少有一类包含所给5 个数中的至少两个. 因此可能出现两种情况： 1° . 某一类至少包含三个数;2° .

23、 某两类各含两个数，第三类包含一个数.若是第一种情况，就在至少包含三个数的那一类中任取三数，其和一定能被3 整除 ; 若是第二种情况，在三类中各取一个数，其和也能被3 整除 . 综上所述，原命题正确.例题3：某校派出学生204 人上山植树15301 株，其中最少一人植树50 株，最多一人植树 100 株，则至少有5 人植树的株数相同.证明：按植树的多少，从50 到 100 株可以构造51 个抽屉，则个问题就转化为至少有5人植树的株数在同一个抽屉里.（ 用反证法） 假设无 5 人或 5 人以上植树的株数在同一个抽屉里，那只有 5 人以下植树的株数在同一个抽屉里，而参加植树的人数为204 人，所以

24、，每个抽屉最多有4 人， 故植树的总株数最多有：4（50+51 +100）=4 X =15300<15301 得出矛盾.因此，至少有 5人植树的株数相同练习： 1. 边长为 1 的等边三角形内有5 个点， 那么这 5 个点中一定有距离小于0.5 的两点.2. 边长为 1 的等边三角形内，若有n2+1 个点，则至少存在2 点距离小于.3. 求证：任意四个整数中，至少有两个整数的差能够被3 整除 .4. 某校高一某班有50 名新生，试说明其中一定有二人的熟人一样多.5. 某个年级有202 人参加考试，满分为100 分，且得分都为整数，总得分为10101 分，则至少有3 人得分相同.“任意36

25、7 个人中，必有生日相同的人。”“从任意 5 双手套中任取6 只，其中至少有2 只恰为一双手套。”“从数 1， 2， . ， 10 中任取 6 个数，其中至少有2个数为奇偶性不同。”大家都会认为上面所述结论是正确的。这些结论是依据什么原理得出的呢?这个原理叫做抽屉原理。它的内容可以用形象的语言表述为：“把m个东西任意分放进n个空抽屉里（m>n）,那么一定有一个抽屉中放进了至少2个东西。”在上面的第一个结论中，由于一年最多有366 天， 因此在 367 人中至少有2 人出生在同月同日。这相当于把367 个东西放入366 个抽屉，至少有2 个东西在同一抽屉里在第二个结论中，不妨想象将5 双手套分别编号，即号码为1， 2， . ， 5 的手套各有两只，同号的两只是一双。任取6 只手套，它们的编号至多有5 种，因此其中至少有两只的号码相同。这相当于把6 个东西放