专题4.1 抽屉原理+孙涛录入.docx

《专题4.1 抽屉原理+孙涛录入.docx》由会员分享，可在线阅读，更多相关《专题4.1 抽屉原理+孙涛录入.docx（4页珍藏版）》请在第一文库网上搜索。

1、4.1 抽屉原理抽屉原理又称鸽笼原理，在组合问题中常常被用到.举一个很简单的例子：将3个苹果放入2个抽屉里，一定存在一个抽屉里放了2个或更多的苹果.这就是最简单的抽屉原理.它是由德国数学家狄利克雷首先提出，所以也称为狄利克雷原理.它有许多表现形式，常见的有如下几种：抽屉原理I.把+1个元素，分别放在个“抽屉”里，那么一定存在某个“抽屉”含有两个或两个以上的元素.抽屉原理II.把m个元素，分别放在个“抽屉里W),那么至少有一个“抽屉”里至少有4个元素.这里,当整除加时，-+1当不整除用时.其中卜表示不超过X的最大整数.抽屉原理III.把无穷多个元素，分别放在有限个“抽屉”里，那么必有一个“抽屉”

2、里含有无穷多个元素.在应用抽屉原理解决问题时,一般分为三个步骤:首先确定分类对象的个数;其次构造抽屉，并说明每个抽屉中的元素符合要求；最后利用抽屉原理证明结论成立.下面通过一些典型的例题来说明这些问题.例1任给5个整数，证明：必能从中选出3个，使得它们的和能被3整除.【分析】由于结论是要证明和是3的倍数，所以可以从被3除所得的余数入手进行讨论.【解】由于任意整数被3除所得的余数只能是0,1,2,所以可以构造0,1,2这样三个抽屉，那么所有整数都可以根据被3除所得的余数对应地放入这三个抽屉中.于是有如下两种情形：(1)若这5个数分布在3个抽屉里，则从这三个抽屉中各取一个数，和一定是3的倍数；(2

3、)若这5个数分布在不超过2个抽屉里，根据抽屉原理，必有一个抽屉含有至少3个数，那么这个抽屉中的任意三个数之和也一定是3的倍数；综上所述，命题成立.例2有50名运动员进行某个项目的单循环赛，如果没有平局，也没有人全胜，证明：一定有两个运动员获胜的场次相同.【解】由于没有平局，不妨设赢一局得1分，输一局得O分.那么由题意可知，最多可能得48分(因为没有人全胜)，最少可能得O分.故得分可能种数为49种，而共有50名运动员，所以必有两名运动员得分相同.【注】这里采用了简单的极端原理，考虑了得分的两种极端值，从而构造出抽屉的数量，而元素的数量50个是显而易见的.例3在1,11,111,，111,中，是否

4、存在2011的倍数？/t个1【解】考虑数列的前2011个数：1,11,111,，111,若其中没有2011的倍数，那么2011个1它们被2011除所得的余数一定为1,2,3,2010这其中的一种，而共有2011个数，所以有抽屉原理知必有两数模2011同余.不妨设111111(mod2011),这里1ii个Ij个12011.2011111-111,即201111.1x10.又因为2011与山互素,故201IIn1.j个ij个ij-j个iy-M这与其中没有201】的倍数矛盾.所以在1,I1H1,，111,中，一定有2011的倍数.【注】无穷多个数中，必有两个数对某一确定的数同余.此题也可用原理In

5、处理.例4在1,2,3,，99,100中，任意取出51个数，试证明：在这51个数中，一定有两个数，其中一个是另一个的倍数.【分析】此类问题的关键在于构造出少于51个抽屉，要求包括所有IOO个数，且每个抽屉中的任意两个数都有倍数关系.而考虑到每个正整数都可以写成奇数与2的幕次的乘积，抽屉的构造就很明显了.【解】构造如下50个抽屉：1,2,4,8,16,32,64,3,6,12,24,48,96,5,10,20,40,80),47,94,49,98,51,53,，95,97,99.任取51个数放入这50个抽屉中，根据抽屉原理，一定有两个数取自同一抽屉，它们一定满足倍数关系.故命题得证.【注】事实上

6、，在在1,2,3,，2中任意取出+1个数，也有这样的结论.构造抽屉(Aa=2Ar+1,2(2+1),2242+1),&=(),1,2,，一1)的方法完全一样.例5在3X4的长方形中，任意放置6个点.证明：可以找到两个点，它们的距离不大于不.【解】如图4-1-1,将长方形分为5个部分：三个五边形，两个四边形.并且每个部分中任意两点之间的距离都不会超过它们最长的对角线的长度6(注意到，凸五边形的对角线长度为百或2),所以六个点放入5个部分中，根据抽屉原理，必有两点处于同一部分.这两点之间的距离就不会超过有.图4-1-1例6证明：从任意给定的2011个正整数中总可以找到若干个数，使得它们的和能被20

7、11整除.【解】设这2011个正整数为4,出，,1,构造如下2011个和数:%,%+%，4+%+。3，4+生+。刈由于任意一个正整数被2011除，所得余数可能是1,2,3,，2010这2011种可能，若有余数为。的情形，则命题已经成立；若余数均不为0,那么只有2010种可能，所以上述2011个和放入2010个抽屉中，由抽屉原理知，必有两个和式模2011同余.将这两个和式相减，即可得到所要的满足条件的数.例7己知从100,101,，500中任取个不同的数，使得总能够找到其中3个数，它们的数字和相同，试求：的最小值.【分析】如何构造抽屉，一直是难点，本题”数字和相同”这个条件指引了我们方向.【解】

8、在()(),101,，500这401个数中，数字和为1的只有100这一个数，数字和最大的22也只有499这一个，其余399个数的数字和都在2至21之间，所以根据抽屉原理，在这399个数中，任取20X2+1=41个数，则必存在3个数，它们的数字之和相同，从而43都符合要求.下面来举例子：100；101,110；102,120；103,130；104,140；105,150；106,160；107,170；108,180；109,190；119,191；129,192；139,193；149,194；159,195；169,196；179,197；189,198；469,496；479,497；4

9、89,498；499它们当中没有三个数字相同，因此=42不符合题意，从而最小为43.【注】请读者体会分组的原则.例8设实数N,x2,3,x4,x5,试求具有下述性质的最小正整数：若存在个不同的，形如4+/+&(1P4r5)的和都等于0,则有X1=9=/=Z=/.【解】一方面，取Ai=24,X2=X3=4=x5=-a则形如芭+xi+xj(2ij5)的和都等于0,因此，n7.另一方面，如果存在7个不同的形如牛+%+xz.(1pqr5)的和都等于0,那么，在7个和中川2,3,x4,七共出现3x7=21次,由此，根据抽屉原理可知，至少有一个出现5次，不妨设其为,由于Xj+%(2i5)共有6个和，故其中

10、至多一个未出现，不妨设W+毛未出现，则有=xi+X3+X5=X1+A4+A=0,从而x2=x3=x=x5=在和式%+%+/中，必有一个使得i,j,k均不为1,那么xi.+xj+xk=3x2=0,由此可得X=W=W=X4=0.综上所述，最小的正整数=7.【注】本题在举例和论证过程中反复利用了抽屉原理.练习4.11 .证明：从2,4,6,，30这15个偶数中任选9个数，其中必有两数之和为34.2 .证明：任意27个小于100的不同正整数中，一定有两个不互素的数.3 .某夏令营组织1987名营员去游览故宫，景山公园、北海公园，规定每人必须去一处，且每人至多去两处游览.求证：至少有332人游览的地方完

11、全相同.4 .在半径为的圆内有任意7个点，证明：其中至少有两个点，它们之间的距离不超过5 .已知一个圆，经过圆心任意作993条直径，它们与圆共有1986个交点，在每个交点分别填写从1到496当中的一个整数（可以重免填写）.证明：一定可以找到两条直径，它们两端的数的和相等.6 .在边长为1的正三角形中，任取7个点，其中任意三点不共线.证明：其中必有三点构成的三角形的面积不超过立.127 .能否将5x5的棋盘的每个小方格分别填上4,5,6这三个数之一，使得每行、每列以及两条对角线上的五个数字之和各不相同？为什么？8 .将5x9的长方形分成10个边长为整数的长方形，无论怎么分，分得的长方形中必有两个是完全相同的.请说明理由.9 .一个正方形被分成了9x9（=81）个大小相同的小方格,在每一个小方格中,任意填写1,2,19,20中的一个数.求证：一定能够找到两对小方格，每对小方格都关于中心小方格（处在大正方形中心位置的小方格）对称，且这两对小方格所填数字之和相等.