您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 咨询培训 > 高中数学竞赛讲座抽屉原理
抽屉原理抽屉原理又叫重叠原则或鸽原则,抽屉原则有如下几种情形。抽屉原则I把1n件东西任意放入n只抽屉里,那么至少有一个抽屉里有两件东西。抽屉原则II把m件东西放入n个抽屉里,那么至少有一个抽屉里至少有nm件东西。抽屉原则III如果有无穷件东西,把它们放在有限多个抽屉里,那么至少有一个抽屉里含无穷件东西。利用抽屉原则解题时,其关键是如何利用题中已知条件构造出与题设密切相关的“抽屉”,下面通过例子说明抽屉原则的应用。例1.在边长为1的正方形内任意放置5个点,试证:其中必有两个点,它们之间的距离不大于22。证明:将边长为1的正方形划分成如图所示的四个边长为21的小正方形,则每个小正方形中任意两点间的距离不大于22,据抽屉原理:5个点放入四个正方形中,其中至少有一个正方形中至少有2个点,则这两个点间的距离不大于22。例2.证明:边长为1的的正三角形内任意放置5个点,其中必有两点,其距离不超过21。证明:将边长为1的正三角形的各边中点连结起来,得到四个小正三角形,则每个小正三角形中任意两点间的距离不大于21,据抽屉原理:5个点放入4个小正三角形中,其中至少有一个小正三角形中至少有2个点,则这两个点间的距离不超过21。例3.在边长为1的正方形中有任意九个点。试证:在以这些为顶点的各个三角形中,至少有一个三角形,其面积不大于81。证明:将边长为1的正方形划分为如图所示的4个441的小长方形,9个点放入4个小长方形中,则必有一个长方形中放入了至少3个点,设为CBA,,,则三角形ABC的面积不大于过81,证明如下:A作边的平行线交BC于A,则:CAABAAABCSSS8141121。例4.求证:任给五个整数,必能从中选出三个,使得它们的和能被3整除。证明:因为任意一个整数被3除的余数只能是0,1,2,若任给的5个整数被3除的余数中0,1,2都出现,则余数为0,1,2的三个整数之和能被3整除;若5个数被3除的余数只出现0,1,2中的两个,则据抽屉原理知:必有3个整数的余数相同,而余数相同的3个数之和能被3整除。故任给五个整数,必能从中选出三个,使得它们的和能被3整除。例5.求证:在100,97,,10,7,4,1中任选20个不同的整数,其中必有二整数之和为104。证明:将100,97,,10,7,4,1这34个自然数分成如下18个集合:52,55,49,,97,7,100,4,1,从100,97,,10,7,4,1中任选20个数,即从上述18个集合中选20个数,则必有一个集合中选了2个数,而这两个数的和为104。例6.设naaa,,,21是自然数n,,3,2,1随意打乱次序重新排列而成的一串数,n是奇数。证明:)()1)(1(21naaan总是偶数。证明:因n为奇数,设12kn,则n,,3,2,1中共有1k个奇数,从而n,,3,2,1,naaa,,,21中共2(1k)=122nk个奇数,这1n个奇数放入n个括号中,则必有一个括号中的两个数均为奇数,从而这两个数之差为偶数,所以)()1)(1(21naaan总是偶数。例7.求证:对于任给的1987个自然数198721,,,aaa,从中总可以找到若干个数,使它们的和能被1987整除。证明:构造如下1987个和:198721321211,,,,aaaaaaaa,若其中有一个和能被1987整除,则结论成立。否则上述1987个和除以1987的余数只能为1986,,2,1,则其中必有两个和的余数相同,设为iaaa21,jaaa21()ji,则)()()(212121jiiijaaaaaaaaa能被1987整除。例8.在任意一次集会中,其中必有两个人,他们认识的人一样多,试证明之。证明:设参加集会的共有n个人,制造如下抽屉:认识的人的人数为0的人属于集合0A;认识的人的人数为1的人属于集合1A;认识的人的人数为2的人属于集合2A,…;认识的人的人数为1n的人属于集合1nA这里得到n个集合,可以证明0A,1nA中至少有一个集合为空集。若0A中有一个元素,则其余1n个人最多认识2n个人,所以1nA为空集;同理可证:若1nA中有一个元素,则0A为空集。所以上述n个集合,其实至多只有1n个集合。n个人放入1n个集合中,其中必有一个集合中有两个人,结论得证。例9.证明:在全世界所有人中任选六个人,其中一定有三个人,他们之间或者互相认识,或者互相不认识。证明:从6个人中任一个人记为A,则其余5个同A或者认识,或者不认识,据抽屉原理:其中必有三个人同A认识,或者不认识;若有三个人同A认识,则这三个人或者互不认识,则结论成立。或者有两个人相互认识,则这两个人同A三人互相认识。若有三个人同A不认识,则这三个人或者互相认识,则结论成立,或者有两个人互不认识,则这两个人同A三人互不认识。结论成立。例10.平面上有1987个点,任取三个点都有两点的距离小于1。求证:存在半径为1的圆,它至少盖住994个点。证明:在所给的1987个点中任选一点,记为A,以A为圆心作一个半径为1的圆,若其余的1986个点都在圆A内,则结论成立;否则,在圆A外的点中任一点,记为B,以B为圆心作一个半径为1的圆,则除去BA,之外的其余1985个点必在圆A或圆B内,否则,至少存在一点C在圆A或圆B的外部,则CBA,,三点任两点间的距离均大于1,与条件矛盾,所以除去BA,之外的其余1985个点必在圆A或圆B内。据抽屉原理:必有一个圆内至少有9931211985个点,加上圆心共994个点。知结论成立。例11.十七个科学家,其中每一个和其他所有的人都通信。在他们的通信中,只讨论三个题目,而且每两个科学家之间只讨论一个题目。求证:至少有三个科学家相互之间在讨论同一个题目。证明:在17位科学家中任选一位,记为A,则A至少与其余16位科学家中的613116位科学家讨论同一题目,记为题目1,若这6位科学家中有两位科学家在讨论题目1,则结论成立;若这6位科学家都不讨论题目1,则他们只能讨论另外两题目,据抽屉原理:他们中至少有3位科学家在讨论同一题目。从而知:结论成立。例12.一个国际社团的成员来自六个国家,共有1978人,用1978,,2,1来编号。试证明:该社团至少有一个成员的编号与他的两个同胞的编号之和相等,或是其一个同胞编号的二倍。证明:证明:用反证法,即设每个国家成员编号mkkk,,21中不存在kjikkk我们将用抽屉原理引出矛盾。六个国家共有成员1978人,而1978=64329,所以总有一个国家1A的成员至少有330人,设他们编号数为,,,33021aaa且33021aaa作329个差,12aa133013,,aaaa(1)由反证法假定,它们不能是1A国成员的编号数(若aaai1是1A国成员的编号,则aaai1,与反证法假定矛盾),所以这329个差数是另外五国成员的编号,由于329=5465,因此有一个国家(记为2A)至少有66个成员的编号数落在差数(1)的范围,记这66个编号当选为66216621,,,bbbbbb由反证法假设又知道5个差为数1661312,,,bbbbbb(2)不可能是2A国成员的编号数,也不可能是1A国的,因为若某11(Aabbi国成员编号),则,)()(11aaaaanm故aaanm,与反证假定型矛盾。于是(2)的数只能是另四国成员编号,由于116465所以有某国3A的确良17位成员的编号数落在(2)中,记这些编17211721,,,,CCCCCC,作6个差数1171312,,,CCCCCC(3)则它们不是3A,也不是2A、1A国的成员的编号数,故必是另三个国家的。由于15316,因些有某国4A的6位成员的编数落在(3)中,记这6个编号数为6321dddd,作五个差数,161312,dddddd(4)同样道理知它们只能是其余两个国家成员的编号数,因些有5A国的3个成员编号数落在(4)中,这3个编号记为321eee。又作差,,1312eeee它不是54321,,,,AAAAA国的成员编号数,所以131eef是第六国6A成员的编号,此时12ff不能是156,,,AAA的成员编号,但1978012ff总是某成员编号,这就矛盾了。可见原命题成立。例13.在100个连续自然数100,,2,1中,任取51个数,试证明在这51个数中,一定有两个数,其中一个是另一个的倍数。证明:任意一个自然数都能表示成为tm2)12((m为自然数,t为非负整数)的形式。将前100个自然数分为如下50个集合:6543210121,21,21,21,21,21,21A543210223,23,23,23,23,23A43210325,25,25,25,25A…9749A,9950A,其中前100个自然数中的每个自然数都属于其中一个集合,而且只属于一个集合。据抽屉原理:从中选51个数,必有两个数是取自同一个集合,在同一个集合中,较大的数必是较小数的倍数。例14.设M是由1985个不同的自然数组成的集合,M中的元素的素因子均不超26,求证:存在Mdcba,,,,使得abcd是某个自然数的四次方。证明:不超过26的质数共9个:23,19,17,13,11,7,5,3,2,所以这1985个正整数可表示为:9212332的形式,0,,0,0921,考虑),,,(921的奇偶性类型,共有51229种类型。在1985全正整数中可找出一对),,,(921、),,,(921有相同奇偶性,即i与i奇偶性相同,9,,2,1i。然后在剩下的21985个数中又可以找出两个,他们的指数),,,(921、),,,(921也有相同的奇偶性。如此下去,由于51251321985,故可得513对),,,(921、),,,(921,且有ii2i(9,,2,1i),最后,在上述的513个),,,(921中,又必有两个),,,(921、),,,(921奇偶性相同,所以iii2,9,,2,1i,设ii2i,iii2,9,,2,1i,则iiii4i,9,,2,1i。此时所求四个数为:9212332,9212332,9212332,9212332。例15.平面上有两个定点A和B及任意四点4321,,,PPPP,求证:这四点中一定有两点jiPP,(jiji,4,3,2,1,)使得31|sinsin|BAPBAPji。证明:显然:BAPi0,1sin0BAPi(4,3,2,1i),即在]1,0[内有四个实数BAPBAPBAPBAP4321sin,sin,sin,sin,把]1,0[分成三个子区间1,32,32,31,31,0,由抽屉原理知:BAPBAPBAPBAP4321sin,sin,sin,sin中必有两个数在同一区间中,不妨设为)4,3,2,1,,(sin,sinjijiBAPBAPji,则:31|sinsin|BAPBAPji,命题得证。例16.任给7个实数,证明其中必有两个数,记为yx,,满足3310xyyx证明:设7个实数为721,,,xxx,令)2,2(ii
本文标题:高中数学竞赛讲座抽屉原理
链接地址:https://www.777doc.com/doc-1946185 .html