浅谈抽屉原理在全国高中数学竞赛中的运1

《浅谈抽屉原理在全国高中数学竞赛中的运1》由会员分享，可在线阅读，更多相关《浅谈抽屉原理在全国高中数学竞赛中的运1（13页珍藏版）》请在金锄头文库上搜索。

1、浅谈抽屉原理在高中数学竞赛中的运用在数学问题中有一类与“存在性”有关的问题，例如：“13个人中至少有两个人出生在相同月份”；“某校400名学生中，一定存在两名学生，他们在同一天过生日”；“2003个人任意分成200个小组，一定存在一组，其成员数不少于11”；“把0，1内的全部有理数放到100个集合中，一定存在一个集合，它里面有无限多个有理数”。这类存在性问题中，“存在”的含义是“至少有一个”。在解决这类问题时，只要求指明存在，一般并不需要指出哪一个，也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉及到的运算较少，依据的理论也不复杂，我们把这些理论称之为“抽屉原理”.“抽屉原理

2、”最先是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题的，所以又称“迪里赫莱原理”，也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果，任意分放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类数学竞赛中的重要内容，本讲就来学习它的有关知识及其应用。一、抽屉原理的基本形式 定理1、如果把n+1个元素分成n个集合，那么不管怎么分，都存在一个集合，其中至少有两个元素。 例1 已知在边长为1的等边三角形内（包括边界）有任意五个点（如图）。证明：

3、至少有两个点之间的距离不大于（1978年广东省数学竞赛题） 矚慫润厲钐瘗睞枥庑赖。分析：5个点的分布是任意的。如果要证明“在边长为1的等边三角形内（包括边界）有5个点，那么这5个点中一定有距离不大于的两点”，则顺次连接三角形三边中点，即三角形的三条中位线，可以分原等边三角形为4个全等的边长为的小等边三角形，则5个点中必有2点位于同一个小等边三角形中（包括边界），其距离便不大于。 以上结论要由定理“三角形内（包括边界）任意两点间的距离不大于其最大边长”来保证，下面我们就来证明这个定理。聞創沟燴鐺險爱氇谴净。如图，设BC是ABC的最大边，P，M是ABC内（包括边界）任意两点，连接PM，过P分别作A

4、B、BC边的平行线，过M作AC边的平行线，设各平行线交点为P、Q、N，那么残骛楼諍锩瀨濟溆塹籟。PQN=C，QNP=A 因为BCAB，所以AC，则QNPPQN，而QMPQNPPQN（三角形的外角大于不相邻的内角），所以 PQPM。显然BCPQ，故BCPM。 酽锕极額閉镇桧猪訣锥。由此我们可以推知，边长为的等边三角形内（包括边界）两点间的距离不大于。 说明：（1）这里是用等分三角形的方法来构造“抽屉”。类似地，还可以利用等分线段、等分正方形的方法来构造“抽屉”。例如“任取n+1个正数ai，满足0ai1（i=1,2,n+1），试证明：这n+1个数中必存在两个数，其差的绝对值小于”。又如：“在边长为

5、1的正方形内任意放置五个点，求证：其中必有两点，这两点之间的距离不大于。 彈贸摄尔霁毙攬砖卤庑。（2）例1中，如果把条件（包括边界）去掉，则结论可以修改为：至少有两个点之间的距离小于，大家可以自己证明，并比较证明的差别。 謀荞抟箧飆鐸怼类蒋薔。（3）用同样的方法可证明以下结论： i）在边长为1的等边三角形中有n2+1个点，这n2+1个点中一定有距离不大于的两点。 ii）在边长为1的等边三角形内有n2+1个点，这n2+1个点中一定有距离小于的两点。 （4）将（3）中两个命题中的等边三角形换成正方形，相应的结论中的换成，命题仍然成立。 （5）我们还可以考虑相反的问题：一般地，至少需要多少个点，才能

6、够使得边长为1的正三角形内（包括边界）有两点其距离不超过。 厦礴恳蹒骈時盡继價骚。例2从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。 分析：本题似乎茫无头绪，从何入手？其关键何在？其实就在“两个数”，其中一个是另一个的整数倍。我们要构造“抽屉”，使得每个抽屉里任取两个数，都有一个是另一个的整数倍，这只有把公比是正整数的整个等比数列都放进去同一个抽屉才行，这里用得到一个自然数分类的基本知识：任何一个正整数都可以表示成一个奇数与2的方幂的积，即若mN+,KN+，nN,则m=(2k-1)2n，并且这种表示方式是唯一的，如1=12，2=121，3=32，

7、茕桢广鳓鯡选块网羈泪。证明：因为任何一个正整数都能表示成一个奇数乘2的方幂，并且这种表示方法是唯一的，所以我们可把1-100的正整数分成如下50个抽屉（因为1-100中共有50个奇数）： 鹅娅尽損鹌惨歷茏鴛賴。（1）1，12，122，123，124，125，126；（2）3，32，322，323，324，325；（3）5，52，522，523，524；（4）7，72，722，723；（5）9，92，922，923；（6）11，112，1122，1123；（25）49，492；（26）51；（50）99。 籟丛妈羥为贍偾蛏练淨。这样，1-100的正整数就无重复，无遗漏地放进这50个抽屉内了。从这

8、100个数中任取51个数，也即从这50个抽屉内任取51个数，根据抽屉原则，其中必定至少有两个数属于同一个抽屉，即属于（1）-（25）号中的某一个抽屉，显然，在这25个抽屉中的任何同一个抽屉内的两个数中，一个是另一个的整数倍。 預頌圣鉉儐歲龈讶骅籴。说明：（1）从上面的证明中可以看出，本题能够推广到一般情形：从1-2n的自然数中，任意取出n+1个数，则其中必有两个数，它们中的一个是另一个的整数倍。想一想，为什么？因为1-2n中共含1，3，2n-1这n个奇数，因此可以制造n个抽屉，而n+1n，由抽屉原则，结论就是必然的了。给n以具体值，就可以构造出不同的题目。例2中的n取值是50，还可以编制相反的

9、题目，如：“从前30个自然数中最少要（不看这些数而以任意方式地）取出几个数，才能保证取出的数中能找到两个数，其中较大的数是较小的数的倍数？” 渗釤呛俨匀谔鱉调硯錦。（2）如下两个问题的结论都是否定的（n均为正整数）想一想，为什么？ 从2，3，4，2n+1中任取n+1个数，是否必有两个数，它们中的一个是另一个的整数倍？ 从1，2，3，2n+1中任取n+1个数，是否必有两个数，它们中的一个是另一个的整数倍？你能举出反例，证明上述两个问题的结论都是否定的吗？ （3）如果将（2）中两个问题中任取的n+1个数增加1个，都改成任取n+2个数，则它们的结论是肯定的还是否定的？你能判断证明吗？ 铙誅卧泻噦圣骋

10、贶頂廡。例3从前25个自然数中任意取出7个数，证明：取出的数中一定有两个数，这两个数中大数不超过小数的1.5倍。 擁締凤袜备訊顎轮烂蔷。证明：把前25个自然数分成下面6组： 1； 2，3； 4，5，6； 7，8，9，10； 11，12，13，14，15，16； 17，18，19，20，21，22，23， 贓熱俣阃歲匱阊邺镓騷。因为从前25个自然数中任意取出7个数，所以至少有两个数取自上面第组到第组中的某同一组，这两个数中大数就不超过小数的1.5倍。 坛摶乡囂忏蒌鍥铃氈淚。说明：（1）本题可以改变叙述如下：在前25个自然数中任意取出7个数，求证其中存在两个数，它们相互的比值在内。 蜡變黲癟報伥铉

11、锚鈰赘。显然，必须找出一种能把前25个自然数分成6（7-1=6）个集合的方法，不过分类时有一个限制条件：同一集合中任两个数的比值在内，故同一集合中元素的数值差不得过大。这样，我们可以用如上一种特殊的分类法：递推分类法： 買鲷鴯譖昙膚遙闫撷凄。从1开始，显然1只能单独作为1个集合1；否则不满足限制条件。 能与2同属于一个集合的数只有3，于是2，3为一集合。 如此依次递推下去，使若干个连续的自然数属于同一集合，其中最大的数不超过最小的数的倍，就可以得到满足条件的六个集合。 綾镝鯛駕櫬鹕踪韦辚糴。（2）如果我们按照（1）中的递推方法依次造“抽屉”，则第7个抽屉为 26，27，28，29，30，31，

12、32，33，34，35，36，37，38，39；第8个抽屉为：40，41，42，60；第9个抽屉为：61，62，63，90，91； 驅踬髏彦浃绥譎饴憂锦。那么我们可以将例3改造为如下一系列题目： （1）从前16个自然数中任取6个自然数；（2）从前39个自然数中任取8个自然数；（3）从前60个自然数中任取9个自然数； （4）从前91个自然数中任取10个自然数；猫虿驢绘燈鮒诛髅貺庑。都可以得到同一个结论：其中存在2个数，它们相互的比值在内。 上述第（4）个命题，就是前苏联基辅第49届数学竞赛试题。如果我们改变区间（pq）端点的值，则又可以构造出一系列的新题目来。 锹籁饗迳琐筆襖鸥娅薔。例4已给一个

13、由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，使子集合中各数之和相等。（第14届1M0试题） 構氽頑黉碩饨荠龈话骛。分析与解答：一个有着10个元素的集合共有210=1024个不同的子集，包括空集和全集在内。空集与全集显然不是考虑的对象，所以剩下1024-2=1022个非空真子集。 輒峄陽檉簖疖網儂號泶。再来看各个真子集中一切数字之和。用N来记这个和数，很明显： 10N91+92+93+94+95+96+97+98+99=855这表明N至多只有855-9=846种不同的情况。由于非空真子集的个数是1022，1022846，所以一定存在两个子集A与B，使得

14、A中各数之和=B中各数之和。 尧侧閆繭絳闕绚勵蜆贅。若AB=，则命题得证，若AB=C，即A与B有公共元素，这时只要剔除A与B中的一切公有元素，得出两个不相交的子集A1与B1，很显然 ，A1中各元素之和=B1中各元素之和，因此A1与B1就是符合题目要求的子集。 识饒鎂錕缢灩筧嚌俨淒。思考：本例能否推广为如下命题： 已给一个由m个互不相等的n位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。 凍鈹鋨劳臘锴痫婦胫籴。例5在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明：其中一定存在两个整点，它们的连线中点仍是整点。 恥諤銪灭萦欢煬鞏鹜錦。分析：由中点坐标公式，坐标平面两点的中点坐标。欲使都是整数，必须而且只须x1与x2，y1与y2的奇偶性相同。坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数，偶数），（奇数，偶数），（偶数，奇数）以此构造四个“抽屉”，则在坐标平面上任取五个整点，那么至少有两个整点，属于同一个“抽屉”因此它们连线的中点就必是整点。 鯊腎鑰诎褳鉀沩懼統庫。说明：我们可以把整点的概念推广：如果（x1,x2,xn）是n维（元）有序数组，且x1,x2,xn中的每一个数都是整数，则称（x1,x2,xn）是一个n维整点。如果对所有的n维整点按每一个xi的奇偶性来分类，由于每一个位置上有奇、偶