初一数学竞赛系列讲座抽屉原理.doc

清华北大家教中心初一数学竞赛系列讲座(14)抽屉原理一、 知识要点1、 抽屉原理1把n+1个东西，任意地分放到n个抽屉里，那么必有一个抽屉里有2个东西。2、 抽屉原理2把m个东西，任意地分放到n个抽屉里，那么必有一个抽屉里至少有k个东西。其中的整数部分。3、 上述二个原理统称为抽屉原理。抽屉原理虽然简单、浅显，却是解决很多存在性问题的有力工具。利用抽屉原理解题的一般步骤是：(1) 构造抽屉，指出东西；(2) 将东西放入抽屉，或从抽屉里取出；(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天，故1i77。 由于每天至少参加一次比赛，但每周累计比赛不超过12次，故有 1a1<a2<<a7711´12=132， 于是，22a1+21<a2+21<<a77+21132+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、152、有22只装钢笔的文具盒，如果不管如何装都至少有4只文具盒里的钢笔数相同(不装算0个)，那么每个文具盒最多可装( )支钢笔。A、4 B、6 C、7 D、83、今有21个自然数a1，a2，a21，且a1<a2<<a2170，则值相等的差aj-ai(1i<j21)的个数为( ) 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、56、从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个点，证明其中至少有两点，它们的距离不超过。家教电话：010-62561255 北京1对1上门家教品牌