02 抽屉原理+黄世桥录入.docx

《02 抽屉原理+黄世桥录入.docx》由会员分享，可在线阅读，更多相关《02 抽屉原理+黄世桥录入.docx（10页珍藏版）》请在第一文库网上搜索。

1、2抽屉原理抽屉原理的最简单形式如下：若把+1个苹果放入个不同的盒子中，则至少有一个盒子里有两个或两个以上的苹果.上述抽屉原理首先由讥动回（18051859）提出并在数论问题中使用.随后，更进一步地归纳为下述三种形式：抽屉原理/把+1个元素按照任意确定的方式划分成个集合，那么一定存在某个集合含含有两个或两个以上的元素.抽屉原理把小个元素按照任意确定的方式划分成个集合（制，为正整数），那么一定存在某个集合含有竺二f+1个或吧1个以上的元素.抽屉原理m把无穷多个元素按照任意确定的方式划分成有限个集合，那么一定存在某个集合含有无穷多个元素.抽屉原理的证明用反证法.假设每个集合中至多含有1个元素，则个集

2、合中至多含有三二TI个元素.又_nJ1w-W-I-m-nJn即个集合中至多含有，一1个元素，这与已知条件有?个元素放入个集合中，矛盾！假设不成立，故结论成立.抽屉原理/和抽屉原理In的证明仿上可用反证法给出证明.用抽屉原理解答数学问题的策略是：分析题意，构造“苹果”和“抽屉”，应用抽屉原理中某种形式.而应用抽屉原理解决问题的关键是恰到好处地构造“苹果”或“抽屉”，构造“抽屉”的方式有很多，如：剩余类、区间、几何图形、染色类等.例1任给12个整数，证明：其中必存在8个数，将它们用适当的用运算符号连起来后运算的结果是3465的倍数.分析注意到3465=11x9x7x5,由此可以联想到利用余数构造抽

3、屉.证明一个整数被11除后的余数分别是O,1,2,10,即剩余类构成11个抽屉.由抽屉原理，12个整数中必有两个数在同一剩余类，记为0、2，则11I（一。2）.12个整数中去掉勾、政后，剩下10个整数.这10个整数分入9的剩余类（共九个抽屉）中，由抽屉原理，必有两个数在同一剩余类，记为。3、4，则9I（内一。4）.剩下的8个整数分入7的剩余类，由抽屉原理，必有两个数在同一剩余类，记为。5、%，则7（a5%）.最后余下的6个整数分入5的剩余类，由抽屉原理，必有两个数在同一剩余类，记为田、则5I（田一。8）因此，（-2）33%）（俏）能被3465整除，即存在8个个数，将它们用适当的运算符号连起来后

4、，运算的结果是3465的倍数.注这里构造的“抽屉”是“剩余类”.例2从1至138共138个正整数中“任”取11个互异的数，证明：在取定的11个数中一定有两个2 3互异的正整数，它们的比值是满足WW2W2.3 223分析将1138的正整数分组（即构造抽屉），满足同一组中任意两数的比值介于二至三之间，且组32数不多于10个.证明将1至138共138个正整数分成10组，即A=,A2=2,3),A3=4,5,6,A4=7,8,9,10),A5=1h12,，16,A6=17,18,，25),A7=26,27,，39),A8=40,41,，60,A9=61,62,，91,A0=92,93,138,23其中

5、同一组中任意两数比值介于W至9之间(事实上，只须证明每组中最大数与最小数之比不超过3236310/316j32533936039131383、2427211217226240261292223由抽屉原理知，任取11个数中至少有两个数属于同一组，从而这两个数之比介于W至士之间.32注这里构造的“抽屉”是“区间”.例3在3x4的长方形中，任意放置6个点.证明：可以找到两个点，它们的距离不大于分析若简单地设计抽屉为1x2的长方形，这时每个区域内两点距离不超过其对角线之长有.但此时共有6个抽屉，还不能用抽屉原理.因此，必须改变抽屉形状，一共只构造五个抽屉，且使每个抽屉内任意两点间的距离不大于右.证明如

6、图21,把长方形划分为5个区域:五边形44小。2。1、五边形48882A2、五边形A2B2GC2D2、四边形O16C2O、四边形BCGB2.这五个区域形状有两类，而每个区域中任意两点之间的距离都不超过它们的最长对角线之长右.图21因此6个点放入此长方形内，必有两点在同一区域，从而它们的距离不大于有.注这里构造的“抽屉”是“几何图形”.例4在5列33行的方格棋盘上染色，每格或染黑色或染白色，证明：至少有两行染的颜色完全一样.分析由于所证为至少有两行染的颜色一样，故抽屉应为一行方格的不同染法.由于一行有5格，故有(24=)32种不同染法.证明对某一行，此行由5格组成，每格可染黑色或白色，故有(25

7、=)32种不同染法.但现有33行，故由抽屉原理知，必存在两行，它们染的颜色是一样的.注这里构造的抽屉”是“染色类”.构造“抽屉”的形式是多样的，再通过下面的例子提高我们构造“抽屉”解决问题的能力.例5某班有60人，任意两人要么相互认识，要么相互不认识，证明：必有两个人，他们认识的人的个数是一样的.分析由于证明存在两人认识的人数一样，我们可以将认识人的不同的个数设为抽屉，而60人中每人认识的人数可以是0,1,，59,60个抽屉60个人，还不能运用抽屉原理.证明班上60个人，班上的人可以认识0人，1人，59人，但若某人只认识0人，则必无人认识59人，若认识59人，则每人至少认识1人，故不管何种情况

8、，60人认识的不同人数至多为59种，而现在有60人，由抽屉原理知，必有两人认识的人数是一样的.注本题是根据每个人认识人的个数不同构造抽屉.而在上述抽屉中有两个抽屉不同时存在，即两种极端情形的抽屉不同时存在.仿照本题思路有更一般的结论：在任何一次聚会中，必有两个人，他们所认识的人一样多.例6证明：任意50个整数中，或可找到两个数，它们的和或差是100的倍数，或可找到一个数，它的两倍是100的倍数.分析先对这50个数对I(M)取模，则若有两个数之和或差或一个数的两倍为100倍数，则取模后也满足条件.关键是如何构造抽屉.由于两个数可以求和，也可以求差，故不妨将50+i和50-i(1WiW49)放在同

9、一抽屉中，而。和50也放在同一抽屉中，从而有50个抽屉(0,50),(1,99),(2,98),(3,97),，(49,51).此时有50个抽屉，但若(0,50)中有一个数，则它的两倍，是100的倍数.证明对这50个数对100取模，则这50个数取模后都为0-99中某一个.现构造抽屉(0,50),(1,99),(2,98),，(49,51).若50个数中有一个取模后在(0,50)中，则它的两倍是100的倍数；若50个数取模后均不在(0,50)中，则必有两个数取模后在某一个(50-i,50+i)(其中1WiW49)中，如果这两个数取模后相同，那么它们之差为100的倍数，如果这两个数取模后不同，那么

10、它们之和为100的倍数.综上，证明了命题.例7某次竞赛共有122名队员参赛，证明：这122人要么有12人来自不同学校，要么有一所学校至少有12名队员.分析可以利用抽屉原理，也可以运用反证法来证明.证明1若有12人来自不同学校，已证明命题；若仅有11所学校派队员参赛，由于史11,由抽屉原理知，必存在一所学校，队员至少有12人.11证明2用反证法.假设命题不成立，即至多有11所学校派队员参赛，而每所学校至多有11人，则一共至多有(IIXII=121名队员参赛，而现在有12名队员参赛，矛盾！故假设不成立，命题得证.例8有17座城市，每两座城市间要么有陆路、要么有水路、要么有飞机航线连接着，而且每两座

11、城市间只有一条线路连接，证明：必存三座城市，它们之间的交通路线是一样的.分析对命题进行抽象化，命题可以改为17个点，每两点间有一条边相连，每条边染红、黄、蓝色中一色，现要证明存在同色三角形.证明将17座城市看成17个点，陆路、水路和飞机航线分别用红、黄和蓝三种颜色的边表示，则问题转化为证明存在同色三角形.取一点8,则与该点相连的16条边中，由抽屉原理，必有一种颜色的边出现了6次.设这6条边为红色，由它们相连的6个点为Ai、A2、A3、A外A5、A6.若存在4(1WiVjW6)为红色，则已有同色三角形BA/若不存在A4(1WiVW6)为红色，则A、A2、A3、A八A5、4之间只有黄色和蓝色边.由

12、我们熟知的定理易证，必存在一个同色三角形.综上，即证明了命题.例9设A=1,2,3,，25,若某个集合由A中5个不同元素组成，则称之为A的一个“五元集”.证明：至多可以有A的30个“五元集”使其中任意两个“五元集”的交集至多有一个数.分析我们要证明的是“至多可以有30个”，所以比较好的方法是用反证法，再利用抽屉原理来导出矛盾.证明用反证法.设有A的31个“五元集”，使其中任意两个“五元集”的交集至多有一个数.因为31个“五元集”共有(31x5=)155个数，由空6知，必有某一个数i(1WiW25)这31个“五元集”中至25少出现了7次，对于含有i的这7个“五元集”，除i外其他数应该都不相同，于

13、是A至少有(4x7=)28个不同的数，而A中仅有25个元素，即得到矛盾！故假设不成立，命题得证.例10袋中有109个球，每次从袋中拿若干个（至少1个），分20次拿完，证明：必定存在3次，这3次拿的球数相同.分析此问题不太易入手,不妨用反证法,假设拿相同数量的次数至多为2次，则20次拿球的个数IO一至少为2=110109,即可导出矛盾./=1证明假设拿相同数量的次数至多为2次，则20次后拿球的个数最少的情况为1个，2个，10个均拿2次，此时拿球个数为2W=110109,这与题设矛盾！/=1故假设不成立，命题得证.例11某次聚会共有4m+2（/为正整数）个同学，其中男生和遏各占们围成一圈，席地而坐

14、，开篝火晚会.求证：必能找到一位同学两旁都是女生.证明若有一男生两旁都是女生，则结论成立.否则，没有一个男生的两旁都是女生，于是每一个男生至少与一个男生相邻，而男生有（47+2）=）2阳+1个，围成一圈后，至多只有加个间隔供2加+1个2女生插位而坐.由抽屉原理，至少有3位女生坐在同一间隔中，从而这3位女生中有一女生的两旁都是女生.例12有8个点，每两个点之间连一条有向线段（单向的），证明：必存在4个点A、B、C、D,其中A指向B,B指向C,C指向D证明8个点之间共有（*=）28条线段，即28条有向线段从8个点射出，由于28=3x8+4,故必有从A至少射出4条有向线段，射向4个点.在这4个点中，

15、同上分析知，必有一个点8,从B至少射出2条有向线段，射向2个点.在这两个点之间的有向线段设为C到D那么所得A、B、C、。四点满足A到B,B至JC,C至JO.例13证明：个整数中必可找到5个数，这5个数之和为5的倍数.证明这17个数可以按除以5所得余数分为5类，分别为%、5攵+1,5攵+2、52+3、5攵+4的形式.若5类数中每类都至少有一个数，那么每类任取一数相加为5的倍数.否则至多有4类，由抽屉原理，必有一类至少有5个数，取此类中5个数，则这5个数之和为5的倍数.故总能找到5个数，它们之和为5的倍数.例14是否存在5个不同的正整数，使得它们中的任何三个数之和是一个质数？解不存在.设0,欧，。5是5个互异的正整数，易知其中任意3个不同的正整数之和均大于3.按模3将这5个数分成剩余类：余数为0、1、2.若这5个数中有三个数分别属于三个不同的剩余类，不妨设m三OsQz3）,S三1。Wd3）,3三2（od3）,则。1+。2+