资源简介

中小学教育资源及组卷应用平台
第 25 讲 抽屉原理
知识方法
美国一家杂志上曾刊登这样一幅漫画：三只鸽子同时往两只鸽笼子里飞.这是一幅含义深刻的漫画，它有趣地说明了抽屉原理：三只鸽子要飞进两只鸽笼，则一定有一只笼子里至少飞进两只鸽子.
抽屉原理一般可表述为：
原理1 若将n+1件物品任意放入n个抽屉里，则必有一个抽屉里至少有两件物品.
原理2 若将 mn+k(k≥1)件物品任意放入n个抽屉里，则必有一个抽屉里至少有m+1件物品.
原理1是原理2在m=k=1时的特殊情形.它的正确性是显然的，可用反证法很容易证明.请同学们自证.
抽屉原理尽管简单，但却有许多出人意料的应用，它是组合数学中一条重要的论证存在性的原理.
应用抽屉原理解决问题的关键在于制造合适的抽屉.如何制造抽屉呢 基本的想法是有的放矢，围绕题设要求，在充分考虑问题自身特点的基础上制造抽屉，这往往要求我们认真观察，善于联想，努力想象，大胆尝试，并灵活运用数学、代数、几何等方面知识，本讲通过典型例题介绍几种常见的制造抽屉的方法.
经典例题解析
1.分割图形制造抽屉
在讨论有关点在几何图形中的分布和性质时，我们常常将几何图形分割成若干部分，将每一部分看成一个“抽屉”.一般来说，采取均等分割图形制造抽屉，如等分正方形、等分矩形、等分线段、等分圆周等.
【例25-1】 在边长为1的正三角形内，有5个点.证明：其中至少有两个点，它们的距离不大于
分析与解 只需证明至少有两个点在边长 的正三角形内即可如图25-1所示，连接正三角形各边的中点，将边长为1的正三角形分为四个全等的边长 的小正三角形.由原理1，以这四个小正三角形作四个抽屉，5个点放入后必有一个小正三角形中至少有两个点，则这两个点的距离不大于正三角形的边
例 25-1是用等分三角形的方法来制造“抽屉”，用类似的作法，将5个点扩充为10 个点，此题可推广为：
在边长为1的正三角形内，有10个点，则其中至少有两个点，它们的距离不大
如图25-2(a)所示，将边长为1的正三角形分割为九个全等的边长 的小正三角形，样就制造出九个抽屉，再利用原理1即得证.
若用正方形代替正三角形，并相应地把它分别等分为四个小正方形(如图25-2(b)所示)和九个小正方形(如图25-2(c)所示)，则立即得到下列两个命题：
(1) 在边长为1的正方形内，有5个点，则其中至少有两个点，它们的距离不大于
(2)在边长为1的正方形内，有10个点，则其中至少有两个点，它们的距离不大于
【例25-2】 在面积为1的圆中有 1993个点，求证：从中可以找到三个点，以这三个点为顶点的三角形的面积小于 0.0011.
证明 将已知圆等分为996个中心角为 的全等扇形,则由原理2,1993=2×996+1个点放入996个扇形中，必有一个扇形中至少含有2+1=3个点(包括在扇形边界上的点).以这三个点为顶点的三角形当然完全含于这个扇形内，因此三角形的面积小于扇形的面积 而 故结论成立.
例 25-2如果制造不同的抽屉，还可以证明更强的结论：能找到三个点，以这三点为顶点的三角形的面积小于0.00076.事实上，由于 1993=3×664+1，故若将已知圆等分为664个中心角为 的全等扇形，则必有一个扇形至少含有3+1=4个点.以这四个点为顶点的四边形的面积小于扇形的面积 于是可以从这四个点中选出三个点，以它们为顶点的三角形面积小于四边形面积的一半，即小于
由此可见，对同一个问题，考虑问题的角度不同，制造的抽屉不同，会产生不同的效果.
2. 按同余类制造抽屉
【例25-3】 求证：任意三个整数中，总有两个整数之差能被 2整除.
分析与解要使两个整数的差被2整除，必须使这两个整数被2除余数相同.于是我们考虑把整数按除以2所得余数为0或1分成两类，这两类即为两个抽屉，由原理1，将3个整数放入两个抽屉，总有两数被2除的余数相同，则此两数之差能被2整除.
评注 例25-3是利用同余类制造抽屉，即以2为除数，把整数分为余数为0和余数为1的两个抽屉.同样，以3为除数，可将全体整数分余数为0、1、2的共3类，即制造3个抽屉.一般地，可将全体整数分为余数为0，1，…，n-1的共n类，即制造n个抽屉.因此，任给n+1个整数，总有两个整数对n同余，于是这两个整数的差能被n整除.因此本题可推广为：
任意n+1个整数中，总有两个整数之差能被n 整除.
【例25-4】 设 n 是大于1 的奇数,证明在 中至少有一个数能被n 整除.
证明 因为n是大于1的奇数，所以n不能整除1,2,2 ,…,2" 中的任何一个，又因为1，2，2 ,…,2n-1共有n个数，它们被n除所得的余数均不为0，但至多只有n-1个余数，于是构造n—1个抽屉，由原理1知，必有两个数被n除的余数相等.例如，设2 与2'(k>t)被n除的余数相等,于是n |(2*—2`),即 由于2` 不能被n 整除，故
冲进 类似例 25-4在证明存在某些整数，使之满足和、差、倍等关系时，则用小于n 的m个正整数构造m个抽屉(特别地有m=n-1)或把整数分组制造抽屉.
【例25-5】 设自然数a ,a ,…, an被某个自然数m 除的余数各不相同，且 试证：其中一定存在两个自然数a 、aj，对某个整数k，使得a + aj -k被m 整除.
分析 直接运用抽屉原理受阻，注意到已知条件2n>m及结论‘ aj)被m整除”,由此启发我们构造2n个数:a ,a ,…, an,k-a ,k-a ,…,k-an并设计m个抽屉，再利用抽屉原理证之.
证明 考虑2n 个数a ,a ,…, an,k-a ,k-a ,…,k-an.因为2n>m，所以其中至少有两个数被m除的余数相同.由题设条件，a ，a ，…，an被m 除的余数各不相同，因此. k-a ,…,k- an被m除的余数也不相同.于是余数相同的两个数只能是a 和k-a aj，所以它们的差 被m 整除.
3. 将整数分组制造抽屉
【例25-6】 任给7个不同的整数，求证：必有两个整数，其和或差是10的倍数.
分析与解 任何整数被10除的余数有10个：0，1，2，…，9.如果利用余数把全体整数分成10类(即10个抽屉)，对给定的7个整数，不能运用抽屉原理.因此，考虑把这10个抽屉合并成6个大“抽屉”:{0},{5},{1,9},{2,8},{3,7},{4,6}.这里{1,9}表示被 10 除余数为 1 或9的全体整数，其他类似.于是至少有一个抽屉里有7个整数中的2个，如果这两个整数同在抽屉{0}或{5}内,其差或和是10的倍数;如果这两个数在{1,9},{2,8},{3,7},{4,6}内的某一个之中，其和是 10的倍数.
【例25-7】 在1~3n这些整数中,任取n+2个数.试证:当n>1时,在这n+2个数中必可找到两个数，使它们的差比n 大，比2n 小.
证明 如果在这n+2个数中不出现3n，那么把其中最大的一个数增大到3n，而其余各数也增大相同的值，则它们任两数之差的值不变.所以，只需考查在选取的数中有一个是3n的情形.
如果在所选取的数中有n+1，n+2，…，2n-1诸数中的一个，则它与3n的差便大于n而小于2n；如果在所选取的数中没有上列数中的任何一个，那就表明除3n外，其余n+1个数是在1,2,3,…,n,2n,2n+1,2n+2,…,3n-1 中选取的.将上述2n 个数分为n 组:(1,2n),(2,2n+1),(3,2n+2),…,(n,3n-1),要从中取n+1个数,由抽屉原理,总有某一组中的两个数全被取到，而此两数之差等于2n-1，正好大于n(因为n>1)而小于2n.
评注 例25-6和例25-7都是针对题目本身的需要，将整数适当分组来制造抽屉.
4. 利用染色制造抽屉
染色实质上是对分类的一种形象描述，对点、线段、区间、区域、图形等按要求染上颜色，按不同颜色制造不同的抽屉，可转化为利用抽屉原理证题.
【例25-8】 世界上任意六个人中，一定有三个人或者互相认识或者互相不认识.
分析与解 用平面上无三点共线的六个点 A ，A ，…，A。表示世界上任意六个人.如果两个人互相认识，就在这两个点之间连一条红线；如果两个人互相不认识，就在这两个点之间连一条蓝线,将由点A 连出的5=2×2+1条线段 A A 、A A 、A A 、A A 、A A 放入红、蓝两个“抽屉”,至少有2+1=3条同色.不妨设A A 、A A 、A A 皆为红色.考虑线段 A A 、A A 、A A ,分两种情况讨论:①若三条都是蓝色,则△A A A 三边同是蓝色,即 A 、A 、A 互相不认识;②若三条中有一条是红色,不妨设为A A ,则△A A A 三边同是红色,即A 、A 、A 互相认识.
评注 例 25-8实质上是著名的同色三角形问题，即任给六个点，其中任三点不共线，每两点都用线段相连(共连15条线)，并且每条线段上任意染上红、蓝两色中一种，则其中必有一个三边同色的三角形.
由若干个不同的顶点与连接其中某些(或全部)顶点的边所组成的图形称为图.如果图中有n个顶点，每两点之间都有一条边，则称之为n点完全图，记为 Kn.将每条边都染上红、蓝两色之一，称之为二染色；每条边都染上K 种颜色之一，称之为K 染色.将Kn的n个顶点中选出m个顶点，则这m个顶点连同它们之间的连线所构成的图形称为原图的一个有m个顶点的完全子图.如果以图中三个顶点为顶点的三角形的三条边染有同种颜色，则称之为同色三角形.
在二染色的K。中，总存在同色三角形(这就是例25-8的图论表述).
【例25-9】 平面上有六个点，其中任意三点不共线.以这六个点为顶点，构成三角形.求证：一定存在一条线段，它既是某个三角形的最短边，同时又是另一个三角形的最长边.
分析 例 25-8中使用的染色方法及结论对本题的解决有极大的启示.
证明 将每一个三角形的最短边染成红色，其余的未染色的边一律染成蓝色(如果某个三角形有两条最短边，那么从中任选一条边染上红色).
根据例 25-8的证明知，一定存在一个三条边同色的三角形.根据染色规则知，每个三角形至少有一条红边，即不存在三条边都是蓝色的三角形，从而一定存在一个三条边都是红色的三角形.这个三角形有最长边，由于这条边染红色，所以这条边一定是某个三角形的最短边.这条线段符合题目要求.
强化训练
1.边长为1的正方形内，任意放入9个点，则至少存在3个点，其所形成的三角形面积不超
2.在边长为1的正方形内，任取101个点，同时任三点不共线.证明：存在以这些点为顶点的三角形，它的面积不大于0.01.
3.在边长为1的正方形内有51个点.证明：其中存在某三个点，可以被半径 的圆纸覆盖.
4.假设a、b、c、d是四个整数,证明:b-a、c-a、d-a,d-c、d-b、c-b 的乘积能被12整除.
5.设a ，a ，…，a 都是整数，则这些整数中必有一些相邻的，如( n+k≤100),使它们的和被 100 整除.
6.对任给的97个互异的正整数a ，a ，…，a ，试证：其中一定存在四个整数，仅用减号、乘号和括号将它们适当组合成为一个算式，其结果是1984的倍数.
7.两条直线相交，四个交角中的一个锐角或一个直角称为这两条直线的“夹角”(见图25-3).现平面上有若干条直线，它们两两相交，并且“夹角”只能是 30°、60°或 90°.问：至多有多少条直线
8.平面上有5条直线，其中任意两条都不平行，则在这5条直线两两相交所成的角中，至少有一个角不超过36°.说明理由.
9.小明有n 张卡片，每张上写有两个不超过n 的正整数，一个用红笔写在左边，另一个用蓝笔写在右边.他的写法：任意两张红色数字相同的卡片，蓝色数字一定不同.写好后再将两数的乘积写在卡片的另一面.最后将乘积加起来得到的和为1296.问：小明有多少张卡片
10.有17位数学家，其中每一个人均和其他所有的人通信，他们的通信中只讨论三个题目.求证：至少有三个数学家相互之间讨论同一个题目.
11.将无穷方格纸的格点涂上两种颜色.证明：在方格纸上存在两条水平直线和两条竖直直线，它们相交的格点被涂上同一颜色.
12.在n×n表格的每格涂上n-1种颜色中的一种.然后可以进行如下的操作：如果在某行或某列中至少有两格是涂颜色a的，那么这行或这列都改涂颜色a.问：能否经若干步后，表格中所有的格都改涂成一种颜色
13.一个书架有五层，从下到上依次称为第1层，第2 层，……，第5 层.今把 15 册图书分放到书架的各层上，有些层上可以不放.证明：无论怎样放，书架每层上的图书册数，以及相邻两层上图书册数之和，这些数中至少有两个是相等的.
14.把无穷方格纸片的每一个方格都染上n种颜色中的一种(n≥1).证明：能找出同样颜色的四个方格，其中心是某个矩形的顶点，此矩形的边平行于方格纸的格线.
1.【解析】把单位正方形等分为四个1×0.25 的小矩形或等分为四个边长为0.5的小正方形.
2.【解析】将单位正方形等分为50个 0.1×0.2的小矩形.
3.【解析】把单位正方形分成25个边长为 0.2 的小正方形，必有一个小正方形内落入三个点，而该小正方形外接圆半径等于
4.【解析】记差的乘积为 P，利用同余类制造抽屉，分别证明 P 能被 3 整除，P能被 4 整除.
5.【解析】考虑下列 101 个数,0,a ,a +a ,…, 被 100除所得的余数的情况，再利用抽屉原理.
6.【解析】注意 1984=64×31,先从所给 97 个数中任取 65 个.如a ,a ,…,a ,则必须有两数之差被 64 整除，不妨设 能被 64 整除，再考虑余下的32个数a ,a ,…,a ,同样有两数之差被31整除，不妨设a66-a67能被 31 整除,又(64,31)=1,所以( 能被 64×31=1984 整除,其结果是1984的倍数.
7.【答案】6.
【解析】固定一条直线，其他直线与此条直线的交角逆时针计算，如答图25-1(a)所示，只能是 30°、60°、90°、120°、150°之一,用抽屉原理,最多有 6 条直线.否则，必有两条直线平行.答图 25-1(b)给出6条直线的情况，所以至多有6条直线.
评注 将答图25-1(b)中所有直线做平行移动，使它们交于同一个点，这样的平行移动显然不改变两条直线的“夹角”，如答图25-1(c)所示.此时，至多有多少条直线就更清楚了.
8.【答案】证明：如答图25-2所示，在平面上任取一点O，过O 点作已知的5条直线的平行线 l 、l 、l 、l 、l .将以O为中心的周角分为10个彼此依次相邻的小角,记为θ ,θ ,…,θ ,θ 。.每个小角θ (i=1,2,…,9,10)都等于这5条直线相交的一个交角.这10 个小角的和恰等于360°，即 根据抽屉原理，至少有一个小角不超过36°.
9.【答案】64.
【解析】由卡片上红、蓝色数字写法，即任意两张红色数字相同的卡片，蓝色数字一定不同，则将写有红色数字k的卡片都拿出来，这些卡片上写的蓝色数字是1，2，…，n中的一个，它们不能超过n张.另外，它们也不能少于n张，这是因为，如果写有某一红色数字k的卡片少于n 张，必定有另一个固定的红色数字，写有这个红色数字的卡片就会多于 n张.所以，对于任意k(1≤k≤n)，写有红色数字k 的所有卡片恰有n 张，它们上面的蓝字恰是1，2，…，n.因此，写有红字k 的卡片的背面数字之和是 全体卡片背面数字和就是 即 n=8.所以，共有 64张卡片.
10.【解析】利用染色制造抽屉并应用本章例 25-8的结论，将科学家对应于点，两科学家之间讨论的题目对应两点连线的颜色，原题转化为：17个点两两相连，相连的边分别用红、蓝、白之一染色，每边一色.证明必存在同色三角形.
A 点引出的 16 条边，根据抽屉原理，其中至少有6条同色，不妨设6条边同为红色，另外 6 个端点分别为A ，A ，…，A ，再考虑这6个点两两连线的颜色，如果其中有一条为红色，则存在红色三角形；如果其中任一边都不是红色的，那么只能是蓝、白两色，于是由 A 引出的5 条边A A ,A A ,…,A A 至少有3条同色.不妨设A A 、A A 、A A 同为蓝色,考虑△A A A 的三边，若有一边为蓝色，则存在蓝色三角形；若任一边都是白色，则△A A A 为白色三角形.命题成立.
11.【解析】取三条竖直直线和九条水平直线，我们仅研究这些直线的交点.因为三个点上涂两种颜色，仅有 种不同方式，所以在九条直线中存在两条，其交点处具有同样涂色方式、我们选择这两条水平直线，涂两种颜色的三个点中，一定能找到两个具有同样涂色的点.通过这两点的竖直直线和前面选出的两条水平线即满足要求.
12.【答案】能.理由如下：在表格的每行中至少可以找到两格是涂同一颜色的，因此可以把每行所有格改涂成与这两格相同的颜色.又至少有两行涂相同颜色的，例如都涂蓝色.这也就是说表格的每列中，至少有两格是涂蓝色的，所以可以把每列所有格都改涂成蓝色，即表格中所有格都将改涂为蓝色.
13.【答案】证明：用x 表示第i 层所放的图书册数，i=1,2,3,4,5.对于出现某个 的情形，结论显然成立.因此,只需考虑x;≥1(i=1,2,3,4,5)的情形.可分为两种情形：
(1) x 、x 、x 、x 、x 中某两个数相等,则结论成立.
(2)x 、x 、x 、x 、x 各不相等,这时这五个数必各取1、2、3、4、5之一,且两两不同.考虑x 、x 、x 、x 、x 、x +x 、x +x 、x +x 、x +x 这九个数，最大的可能是 9，最小的可能是1.如果这九个数中有某一个为9，则必是由4+5构成，此时，无论怎样放，都不会同时出现8册和 7册.因此这九个数只有八种可能，必有两数相等.
14.【答案】证明：首先考查方格纸中有n+1个方格宽的水平带形，这个带形的每条竖直小条中含有n+1个方格.对n+1个方格染上不多于 n 种颜色，即构造n个抽屉，由抽屉原理知每个小条中至少有2个方格同色.
由于这样的竖直小条有无限多个，而对小条的方格染色的所有方法至多有n" 种，所以从这无限多个小条中可以找出两条染色方法相同的小条来，而实际只需要 个方格的格纸就可以了.
在两个染色方法相同的小条中一定有四个同色的方格，这四个方格各自的中心恰为某个矩形的四个顶点，且这矩形的边分别与方格的格线平行.

展开更多......

收起↑