初一竞赛讲座14（抽屉原理）.doc

初一数学竞赛系列讲座(14)
抽屉原理

一、 一、知识要点
1、 1、  抽屉原理1
把n+1个东西，任意地分放到n个抽屉里，那么必有一个抽屉里有2个东西。
2、 2、  抽屉原理2
把m个东西，任意地分放到n个抽屉里，那么必有一个抽屉里至少有k个东西。其中
的整数部分。
3、 3、  上述二个原理统称为抽屉原理。抽屉原理虽然简单、浅显，却是解决很多存在性问题的有力工具。利用抽屉原理解题的一般步骤是：
(1) (1)    构造抽屉，指出东西；
(2) (2)    将东西放入抽屉，或从抽屉里取出；
(3) (3)    说明理由，得出结论。

二、 二、例题精讲
例1 用2种颜色涂3行9列共27个小方格，证明：不论如何涂色，其中必至少有两列，它们的涂色方式相同.
分析：把用两种颜色涂１×３的小方格的方法当作抽屉。
解：用两种颜色涂１×３的小方格共有８种方法．现有９列，由抽屉原理，必有两列涂法一样．
评注：用抽屉原理解题的关键在于构造抽屉，另外还要搞清什么是抽屉？什么是东西？

例2 已知一个圆。经过圆心任意作993条直径，它们与圆共有1986个交点，在每个交点处分别填写从1到496中的一个整数(可重复填写)。证明：一定可以找到两条直径，它们两端的数的和相等。(第二届迎春杯决赛试题)
分析：直径两端的数都在1到496之间，所以它们两端的数的和在2到992之间，
则可构造991只抽屉，而东西有993个，因而得到证明。
证明：直径两端的数都在1到496之间，所以直径两端的数的和≥2，且≤992
所以，这种和只有991种。
而直径有993条，993>991，所以一定可以找到两条直径，它们两端的数的和相等。
评注：由解题过程知本题将“993条直径”改为“992条直径”结论仍然成立。
如果将结论改为“可以找到两条直径，它们两端的数的和相等”，那么条件“经过圆心任意作993条直径”就要改为“经过圆心任意作1983条直径”。

例3夏令营组织1987名营员去游览故宫、景山公园、北海公园，规定每人最少去一处，最多去两处游览，至少有几个人游览的地方完全相同？试证明你的结论。(第二届迎春杯决赛试题)
分析：将游览方案当作抽屉，将人当作东西，由抽屉原理可得结论。
解：去一处的可能有3种(故宫、景山公园、北海公园)，去两处的可能也有3种(故宫与景山公园、北海公园与故宫、景山公园与北海公园)，由于每人最少去一处，最多去两处游览，所以游览方案共有6种。
因此，1987个人中至少有个人游览的地方完全相同。

例4在1，4，7，…，100中任选20个不同的数。证明其中至少有4个数a、b、c、d，使a+b=c+d=104.(第39届普特南数学竞赛试题)
分析：考虑和为104的数对。如果两个数取自同一个数对，则它们的和必是104，所以应当将和为104的数对作为抽屉。
解：将1，4，7，…，100这34个数，去掉1与52，分成16个数对：
{4，100}，{7，97}，…，{49，55}，显然每个数对中两数的和为104
所取的20个数中，至少有18个取自这16个数对，则根据抽屉原理，其中必有两个数a、b在同一数对中，它们的和a+b=104。
剩下的16个数，取自其余的15个数对，同样根据抽屉原理，其中必有两个数c、d在同一数对中，它们的和c+d=104。
所以其中至少有4个数a、b、c、d，使a+b=c+d=104.
评注：本题两次使用了抽屉原理。

例5 910瓶红、蓝墨水，排成130行，每行7瓶，证明：不论怎样排列，红蓝墨水瓶的颜色次序必定出现下述两种情况之一种：
（1）至少有三行完全相同；
（2）至少有两组（四行）每组的两行完全相同. （北京1990年高一竞赛）
解：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）两组（四行），且两组两行完全相同.

例6 从自然数1，2，3，…99，100这100个数中随意取出51个数来，求证：其中一定有两个数，它们中的一个是另一个的倍数.
分析：设法制造抽屉，使它们符合如下条件：（1）不超过50个；（2）每个抽屉的里的数（除仅有的一个外），其中一个数是另一个数的倍数。一个自然的想法是从数的质因数表示形式入手。
解：设第一个抽屉里放进数：1，1×2，1×22，1×23，1×24，1×25，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.
…………
第五十个抽屉里放进数：99.
那么随意取出51个数中，必有两个数同属一个抽屉，其中一个数是另一个数的倍数.
评注：本题构造的抽屉比较别致，它必须符合分析中的两个条件。这种构造抽屉的方法值得我们体会。

例7 在边长分别为2和4的矩形中任取9个点(任三点不共线)，证明至少存在三点，以它们为顶点的三角形的面积不大于1。
分析：矩形中任一三角形的面积不超过该矩形面积的一半，而已知矩形面积为8，故若将该矩形分为4个等积的小矩形，则小矩形的面积为2，其内的任一三角形的面积不超过1，因而只须将已知矩形分为4个等积的小矩形，证明其中至少有一份含有9个点中的3个点即可。
证明：将已知矩形分为4个全等的小矩形，则由抽屉原理，任取9个点中至少有3个点在一个小矩形中。由于这个小矩形的面积等于，故以这3个点为顶点的三角形面积不超过该小矩形面积的一半1，问题得证。

例8 有一位国际象棋大师，用11周时间准备一次锦标赛。在准备期间，他决定每天至少参加一次比赛，但每周累计比赛不超过12次。证明：存在连续若干天，这位大师恰好共进行了21次比赛。
证明：设前i天这位大师累计比赛的次数为a i，11周共有77天，故1≤i≤77。
由于每天至少参加一次比赛，但每周累计比赛不超过12次，故有
1≤a1<a2<…<a77≤11´12=132，
于是，22≤a1+21<a2+21<…<a77+21≤132+21=153
则在1到153之间共有154个整数：a1，a2，…，a77，a1+21，a2+21，…，a77+21
由抽屉原理，其中至少有两个数相等。由于a1，a2，…，a77不可能相等，a1+21，a2+21，…，a77+21也不可能相等，所以只可能是某个a i与某个a j+21(j<i) 相等，即a i- a j=21。这说明这位大师第j+1天，第j+2天，…，第i天累计比赛21次。

三、 三、巩固练习
选择题
1、一副扑克有4种花色，每种花色有13张，从中任意抽牌，最少要抽( )张才能保证有4张牌是同一花色。
A、12 B、13 C、14 D、15
2、有22只装钢笔的文具盒，如果不管如何装都至少有4只文具盒里的钢笔数相同(不装算0个)，那么每个文具盒最多可装( )支钢笔。
A、4 B、6 C、7 D、8
3、今有21个自然数a1，a2，…，a21，且a1<a2<…<a21≤70，则值相等的差aj-ai(1≤i<j≤21)的个数为( )
A、0个 B、2个 C、至多有3个 D、至少有4个
4、从1，2，3，4，5，6，7，8，9中任取5个数，则(1)其中必有两数互质；(2)其中必有一数是另一数的倍数；(3) 其中必有一数的两倍是另一数的倍数。以上结论中，正确的个数为( )
A、0个 B、1个 C、2个 D、3个
5、某校有1200人，则全校在同一天过生日的人至少有（ ）个
A、2 B、3 C、4 D、5
6、从1，2，3，…，n中任取8个数且使其中一定至少有两个数的商不小于又不大于，则n的最大值是（ ）
A、25 B、32 C、39 D、60
填空题
7、把130只苹果分给若干小朋友，如果不管如何分，都至少有一个小朋友分得4只或4只以上的苹果，则小朋友最多有 个。
8、黑色、白色、黄色的筷子各有8根，混杂地放在一起，黑暗中想从这些筷子中取出颜色不同的两双筷子(一双筷子指同色的两根)，则至少要取 根筷子。
9、在一副扑克牌中取牌，至少取 张，才能保证其中必有3张牌的点数相同。
10、不大于10的k个自然数，从中选出三个数，使得其中两数之和等于第三个数，则k的最小值是
11、在面积为1的平行四边形内有任意五点，则一定存在三点，以这三点为顶点的三角形面积不大于
12、在1，3，5，7，…，m连续奇数中任取17个数，使其中至少有两个数之差为8，则奇数m的最大值为
解答题
13、在不超过91的自然数中任取10个数，证明：这10个数中一定有两个数的比值在区间中。
14、设a1，a2，…，an是1，2，…，n的某种排列，且n是奇数，求证：(a1-1)( a2-2)…(a n-n)必是偶数。
15、用2种颜色涂5×5共25个小方格，证明：必有一个四角同色的矩形出现.
16、把圆周分成36段，将1，2，…，35，36这36个数字任意写在每一段内，使每一段内恰好有一个数字。求证：一定存在连续的三段，它们的数字和至少是56。
17、在一次集会上，其中必有两个人，他们认识的人数一样多。试证明之(这里甲认识乙，则乙也认识甲)
18、任选6人，试证其中必有3人，他们互相认识或都不认识.
19、a，b，c，d为四个任意给定的整数，求证：以下六个差数b-a，c-a，d-a，c-b，d-b，d-c的乘积一定可以被12整除.
20、在边长为1的正三角形内任取10个点，证明其中至少有两点，它们的距离不超过。