1、竞赛讲座竞赛讲座 1010 -抽屉原则抽屉原则 大家知道，两个抽屉要放置三只苹果，那么一定有两只苹果放在同一个抽屉里， 更一般地说，只要被放置的苹果数比抽屉数目大，就一定会有两只或更多只的苹果 放进同一个抽屉，可不要小看这一简单事实，它包含着一个重要而又十分基本的原 则抽屉原则. 1 抽屉原则有几种最常见的形式 原则 1 如果把 n+k(k1)个物体放进 n 只抽屉里，则至少有一只抽屉要放进两个或 更多个物体： 原则本身十分浅显，为了加深对它的认识，我们还是运用反证法给予证明；如果每 个抽屉至多只能放进一个物体， 那么物体的总数至多是 n， 而不是题设的 n+k(k1)， 这不可能. 原则虽简
2、单.巧妙地运用原则却可十分便利地解决一些看上去相当复杂、 甚至感到无 从下手的总是，比如说，我们可以断言在我国至少有两个人出生的时间相差不超过 4 秒钟，这是个惊人的结论，该是经过很多人的艰苦劳动，统计所得的吧！不，只 须我们稍动手算一下： 不妨假设人的寿命不超过 4 万天（约 110 岁，超过这个年龄数的人为数甚少），则 10 亿人口安排在 8 亿 6 千 4 百万个“抽屉”里，根据原则 1，即知结论成立. 下面我们再举一个例子： 例 1 幼儿园买来了不少白兔、 熊猫、 长颈鹿塑料玩具， 每个小朋友任意选择两件， 那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道 理.
3、 解 从三种玩具中挑选两件，搭配方式只能是下面六种： （兔、兔），（兔、熊猫），（兔、长颈鹿），（熊猫、熊猫），（熊猫、长颈鹿）， （长颈鹿、长颈鹿） 把每种搭配方式看作一个抽屉，把 7 个小朋友看作物体，那么根据原则 1，至少有 两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式， 选的玩具相同. 原则 2 如果把 mn+k(k1)个物体放进 n 个抽屉， 则至少有 一个抽屉至多放进 m+1 个物体.证明同原则相仿.若每个抽 屉至多放进 m 个物体,那么 n 个抽屉至多放进 mn 个物体, 与题设不符，故不可能. 原则 1 可看作原则 2 的物例（m=1） 例 2 正方体
4、各面上涂上红色或蓝色的油漆（每面只涂一种色），证明正方体一定有 三个面颜色相同. 证明把两种颜色当作两个抽屉，把正方体六个面当作物体，那么 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
5、+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 个物体.
6、证明假定第一个抽屉放入物体的数不超过 m1个，第二个抽屉放入物体的数不超过 m2 个，第 n 个抽屉放入物体的个数不超过 mn，那么放入所有抽屉的物体总数不 超过 m1+m2+mn个，与题设矛盾. 例 4 有红袜 2 双，白袜 3 双，黑袜 4 双，黄袜 5 双，蓝袜 6 双（每双袜子包装在一 起）若取出 9 双，证明其中必有黑袜或黄袜 2 双. 证明 除可能取出红袜、白袜 3 双外.还至少从其它三种颜色的袜子里取出 4 双，根 据原理 3，必在黑袜或黄袜、蓝袜里取 2 双. 上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题，不错，这正是 抽屉原则的主要作用.需要说明的是， 运用抽屉
7、原则只是肯定了“存在”、 “总有”、 “至少有”，却不能确切地指出哪个抽屉里存在多少. 2 制造抽屉是运用原则的一大关键 首先要指出的是，对于同一问题，常可依据情况，从不同角度设计抽屉，从而导致 不同的制造抽屉的方式. 例 5 在边长为 1 的正方形内，任意给定 13 个点，试证：其中必有 4 个点，以此 4 点为顶点的四边开面积不超过（假定四点在一直线上构成面积为零的四边形）. 证明如图 12-2 把正方形分成四个相同的小正方形. 因 13=34+1，根据原则 2，总有 4 点落在同一个小正方形内（或边界上），以此 4 点为顶点的四边形的面积不超过小正方形的面积， 也就不超过整个正方形面积的
8、. 事实上，由于解决问题的核心在于将正方形分割成四个面积相等的部分，所以还可 以把正方形按图 12-3（此处无图）所示的形式分割. 合理地制造抽屉必须建立在充分考虑问题自身特点的基础上. 例 6 在一条笔直的马路旁种树，从起点起，每隔一米种一棵树，如果把三块“爱护 树木”的小牌分别挂在三棵树上，那么不管怎样挂，至少有两棵挂牌的树之间的距 离是偶数（以米为单位），这是为什么？ 解如图 12-4（设挂牌的三棵树依次为 A、B、C.AB=a，BC=b，若 a、b 中有一为偶数， 命题得证.否则 a、b 均为奇数，则 AC=a+b 为偶数，命题得证. 下面我们换一个角度考虑：给每棵树上编上号， 于是两
9、棵树之间的距离就是号码差， 由于树的号码只能为奇数和偶数两类，那么挂牌的三棵树号码至少有两个同为奇数 或偶数，它们的差必为偶数，问题得证. 后一证明十分巧妙，通过编号码，将两树间距离转化为号码差.这种转化的思想方法 是一种非常重要的数学方法 例 7 从自然数 1，2，3，99，100 这 100 个数中随意取出 51 个数来，求证：其中 一定有两个数，它们中的一个是另一个的倍数. 分析设法制造抽屉： （1） 不超过 50 个； （2） 每个抽屉的里的数 （除仅有的一个外） ， 其中一个数是另一个数的倍数，一个自然数的想法是从数的质因数表示形式入手. 解设第一个抽屉里放进数：1，12，12 2，
10、123，124，125，126； 第二个抽屉时放进数：3，32，32 2，323，324，325； 第三个抽屉里放进数：5，52，52 2，523，524； 第二十五个抽屉里放进数：49，492； 第二十六个抽屉里放进数：51. 第五十个抽屉里放进数：99. 那么随意取出 51 个数中， 必有两个数同属一个抽屉， 其中一个数是另一个数的倍数. 制造抽屉并非总是一帆风顺的，有时要边制造边调整、改进. 例 8 任意给定 7 个不同的自然数，求证其中必有两个整数，其和或差是 10 的倍数. 分析注意到这些数队以 10 的余数即个位数字，以 0，1，9 为标准制造 10 个抽 屉，标以0，1，9.若有
11、两数落入同一抽屉，其差是 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 元开始，由抽屉原则，
12、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 个人，首先
13、以 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 都
14、可以整除 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
15、为偶数，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 的倍数，问题得证，否则至 少
16、有两个数被 n 除余数相同，则它们的差即它们中若干数（包括 1 个）的和是 n 的 倍数，问题同样得证. 例子 3（北京 1990 年高一竞赛）910 瓶红、蓝墨水，排成 130 行，每行 7 瓶，证明： 不论怎样排列，红蓝墨水瓶的颜色次序必定出现下述两种情况之一种： （1）至少有三行完全相同； （2）至少有两组（四行）每组的两行完全相同. 解 910 瓶红、蓝墨水排成 130 行，每行 7 瓶，对一行来说，每个位置上有红蓝两种 可能，因此，一行的红、蓝墨水排法有 2 7=128 种，对每一种不同排法设为一种“行 式”，共有 128 种行式. 现有 130 行，在其中任取 129 行，依抽屉原
17、则知，必有两行 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
18、，2，3，10 这十个数中任取六个数，那么这六个数中总可以 找到两个数，其中一个是另一个的倍数. 4 证明：任意 502 个整数中，必有两个整数的和或差是 998 的倍数. 5 任意写一个由数字 1，2，3 组成的 30 位数，从这 30 位数任意截取相邻三位， 可得一个三位数，证明：在从各个不同位置上截得的三位数中至少有两个相等. 6 证明：把任意 10 个自然数用适当的运算符号连接起来，运算的结果总能被 1890 整除. 7 七条直线两两相交，所得的角中至少有一个角小于 26. 8 用 2 种颜色涂 3 行 9 列共 27 个小方格，证明：不论如何涂色，其中必至少有 两列，它们的涂色方式相
19、同. 9 用 2 种颜色涂 55 共 25 个小方格，证明：必有一个四角同色的矩形出现. 10 求证存在形如 1111 的一个数，此数是 1987 的倍数. 练习十二 1 15 分钟里在每一分钟看作一个抽屉， 20 次投篮看作 20 个物体， 根据原理一即得. 2.至少要取只筷子因为只筷子中必有一双筷子同色，不妨设它是黄色， 则黑色或白色的筷子至少有只，其中必有一双同色，即黑色或白色，故取只 筷子足以保证成功但少于只不行，如取只筷子，闵可能出现只黄色， 黑白各一只，不合要求 将个数分成组：（，），（，），（，），（，）， （，）任取六个数必有两个落入同一组，而同组二数中一数是另一数的倍 数 每
20、个整数被除，余数必是，中的一个把这 个余数制造为（），（，），（，），（， ），（），（），（）共个抽屉，把个整数按 被除的余数大小分别放入上述抽屉，必有两数进入同一抽屉若余数相同， 那么它们的差是的倍数，否则和为的倍数 从各种位置上截得的三位数有个，但由，组成的不同三位数有 个，故有两个截得的三位数相同 将个数记为， ， ， ， 个数中至少有两个被除余数相同，设为，则可被整除同样 剩下个数中有两个数的差可被整除，记为，剩下个数中有两个数的 差可被整除，记为，剩下个数中有两个数的差可被整除，记为 剩下两数，若有一数为偶数，则，可被整除，否则 可被整除故乘积（）（）（）（） 与（）（）（）（）（） 二者之一必可被整除 任选一点，过点分别作各线的平行线，则它们把一周角分成个彼此相 邻的角，其中至少有一个角小于 用两种颜色涂的小方格共有种方法现有列，由抽屉原则，必有两 列涂法一样 设两种颜色为红、蓝，考察第一行的涂色必有三格同色，不妨设为红色，且 在左边三列现考察左边三列，若下面四行中某一行有两格同为红色，则出现四角 同红色矩形，否则每行仅可能一格染红色，从而四行中必有二行左边三列中有两列 同染蓝色，从而得到四角同为蓝色的矩形 考虑，共个数，其中必有一个是的倍数， 否则必有两数被除余数相同，其差 是的倍数但 与没 有除外的因数，故是倍数导致矛盾
