关键词不能为空

当前您在: 主页 > 数学 >

高中数学竞赛讲义抽屉原理

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2020-09-17 19:48
tags:高中数学联赛

编制高中数学问题-高中数学踩点提分


§23抽屉原理

在数学问题中有一类与“存在性”有关的问题,例如:“ 13个人中至少有两个人出生在
相同月份”;“某校400名学生中,一定存在两名学生,他们在同一天 过生日”;“2003个
人任意分成200个小组,一定存在一组,其成员数不少于11”;“把[0, 1]内的全部有理数
放到100个集合中,一定存在一个集合,它里面有无限多个有理数”。这类存在性 问题中,
“存在”的含义是“至少有一个”。在解决这类问题时,只要求指明存在,一般并不需要指出哪一个,也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉及到
的运算较 少,依据的理论也不复杂,我们把这些理论称之为“抽屉原理”。
“抽屉原理”最先是由19世 纪的德国数学家迪里赫莱(Dirichlet)运用于解决数学问
题的,所以又称“迪里赫莱原理”, 也有称“鸽巢原理”的。这个原理可以简单地叙述为“把
10个苹果,任意分放在9个抽屉里,则至少有 一个抽屉里含有两个或两个以上的苹果”。这
个道理是非常明显的,但应用它却可以解决许多有趣的问题 ,并且常常得到一些令人惊异的
结果。抽屉原理是国际国内各级各类数学竞赛中的重要内容,本讲就来学 习它的有关知识及
其应用。
(一) 抽屉原理的基本形式
定理1、如果把n+1个元素分成n个集合,那么不管怎么分,都存在一个集合,其中至少
有两个元素。
证明:(用反证法)若不存在至少有两个元素的集合,则每个集合至多1个元素,从而n
个 集合至多有n个元素,此与共有n+1个元素矛盾,故命题成立。
在定理1的叙述中,可以把“元素”改为“物件”,把“集合”改成“抽屉”,抽屉原
理正是由此得名。
同样,可以把“元素”改成“鸽子”,把“分成n个集合”改成“飞进n个鸽笼中”。
“鸽 笼原理”由此得名。
例题讲解
1. 已知在边长为1的等边三角形内(包括边界)有任意 五个点(图1)。证明:至少有两
个点之间的距离不大于



2 .从1-100的自然数中,任意取出51个数,证明其中一定有两个数,它们中的一个是另一
个的整数 倍。


3.从前25个自然数中任意取出7个数,证明:取出的 数中一定有两个数,这两个数中大数
不超过小数的1.5倍。






4.已给一个由10个互不相等的两位十进制正整数组成的集合。求证 :这个集合必有两个无
公共元素的子集合,各子集合中各数之和相等。






5.在坐标平面上任取五个整点(该点的横纵坐标都取整数),证明: 其中一定存在两个整
点,它们的连线中点仍是整点。






6.在任意给出的100个整数中,都可以找出若干个数来(可以是一个数),它 们的和可被
100整除。





7. 17 名科学家中每两名科学家都和其他科学家通信,在他们通信时,只讨论三个题目,而
且任意两名科学家通 信时只讨论一个题目,证明:其中至少有三名科学家,他们相互通信时
讨论的是同一个题目。



例题答案:
1. 分析:5个点的分布是任意的。如果要 证明“在边长为1的等边三角形内(包括边界)
有5个点,那么这5个点中一定有距离不大于的两点”, 则顺次连接三角形三边中点,即三


角形的三条中位线,可以分原等边三角形为4个全等的 边长为的小等边三角形,则5个点中
必有2点位于同一个小等边三角形中(包括边界),其距离便不大于 。
以上结论要由定理“三角形内(包括边界)任意两点间的距离不大于其最大边长”来保
证,下面我们就来证明这个定理。

如图2,设BC是△ABC的最大边,P,M是△ ABC内(包括边界)任意两点,连接PM,过
P分别作AB、BC边的平行线,过M作AC边的平行线 ,设各平行线交点为P、Q、N,那么
∠PQN=∠C,∠QNP=∠A
因为B C≥AB,所以∠A≥∠C,则∠QNP≥∠PQN,而∠QMP≥∠QNP≥∠PQN(三角形的外角
大于不相邻的内角),所以 PQ≥PM。显然BC≥PQ,故BC≥PM。
由此我们可以推知,边长为的等边三角形内(包括边界)两点间的距离不大于。
说明:
(1)这里是用等分三角形的方法来构造“抽屉”。类似地,还可以利用等分线段、等分
正 方形的方法来构造“抽屉”。例如“任取n+1个正数a
i
,满足0<a
i
≤ 1(i=1,2,…,n+1),
试证明:这n+1个数中必存在两个数,其差的绝对值小于”。又如: “在边长为1的正方形
内任意放置五个点,求证:其中必有两点,这两点之间的距离不大于。
(2)例1中,如果把条件(包括边界)去掉,则结论可以修改为:至少有两个点之间的
距 离小于,请读者试证之,并比较证明的差别。
(3)用同样的方法可证明以下结论:
22
i)在边长为1的等边三角形中有n+1个点,这n+1个点中一定有距离不大于的两点。
22
ii)在边长为1的等边三角形内有n+1个点,这n+1个点中一定有距离小于的两点。
(4)将(3)中两个命题中的等边三角形换成正方形,相应的结论中的换成,命
题仍然成立。
(5)读者还可以考虑相反的问题:一般地,“至少需要多少个点,才能够使得边长
为1的正三角形内(包括边界)有两点其距离不超过”。
2.分析:本题似乎茫无头绪,从 何入手?其关键何在?其实就在“两个数”,其中一个是另
一个的整数倍。我们要构造“抽屉”,使得每 个抽屉里任取两个数,都有一个是另一个的整
数倍,这只有把公比是正整数的整个等比数列都放进去同一 个抽屉才行,这里用得到一个自
然数分类的基本知识:任何一个正整数都可以表示成一个奇数与2的方幂 的积,即若
n
m∈N+,K∈N+,n∈N,则m=(2k-1)·2,并且这种表示方式是唯 一的,如1=1×2°,2=1×21,
3=3×2°,……
证明:因为任何一个正整 数都能表示成一个奇数乘2的方幂,并且这种表示方法是唯一
的,所以我们可把1-100的正整数分成 如下50个抽屉(因为1-100中共有50个奇数):
23456
(1){1,1×2,1×2,1×2,1×2,1×2,1×2};
2345
(2){3,3×2,3×2,3×2,3×2,3×2};
234
(3){5,5×2,5×2,5×2,5×2};
23
(4){7,7×2,7×2,7×2};
23
(5){9,9×2,9×2,9×2};
23
(6){11,11×2,11×2,11×2};


……
(25){49,49×2};
(26){51};
……
(50){99}。
这样,1-100的正整数就无重复,无遗漏地放进这50个抽屉内了。从 这100个数中任取
51个数,也即从这50个抽屉内任取51个数,根据抽屉原则,其中必定至少有两 个数属于同
一个抽屉,即属于(1)-(25)号中的某一个抽屉,显然,在这25个抽屉中的任何同一 个抽
屉内的两个数中,一个是另一个的整数倍。
说明:
(1)从上面 的证明中可以看出,本题能够推广到一般情形:从1-2n的自然数中,任意
取出n+1个数,则其中必 有两个数,它们中的一个是另一个的整数倍。想一想,为什么?因
为1-2n中共含1,3,…,2n- 1这n个奇数,因此可以制造n个抽屉,而n+1>n,由抽屉原
则,结论就是必然的了。给n以具体值 ,就可以构造出不同的题目。例2中的n取值是50,
还可以编制相反的题目,如:“从前30个自然数 中最少要(不看这些数而以任意方式地)取
出几个数,才能保证取出的数中能找到两个数,其中较大的数 是较小的数的倍数?”
(2)如下两个问题的结论都是否定的(n均为正整数)想一想,为什么?
①从2,3,4,…,2n+1中任取n+1个数,是否必有两个数,它们中的一个是另一个的
整数倍?
②从1,2,3,…,2n+1中任取n+1个数,是否必有两个数,它们中的一个是另一个的
整数倍?
你能举出反例,证明上述两个问题的结论都是否定的吗?
(3)如果将(2)中两 个问题中任取的n+1个数增加1个,都改成任取n+2个数,则它
们的结论是肯定的还是否定的?你能 判断证明吗?
3.证明:把前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个 数,求证其中存在两个
数,它们相互的比值在内。
显然,必须找出一种能把前25个自 然数分成6(7-1=6)个集合的方法,不过分类时有一
个限制条件:同一集合中任两个数的比值在内 ,故同一集合中元素的数值差不得过大。这
样,我们可以用如上一种特殊的分类法:递推分类法:
从1开始,显然1只能单独作为1个集合{1};否则不满足限制条件。
能与2同属于一个集合的数只有3,于是{2,3}为一集合。
如此依次递推下去,使若干个连 续的自然数属于同一集合,其中最大的数不超过最小的
数的倍,就可以得到满足条件的六个集合。
(2)如果我们按照(1)中的递推方法依次造“抽屉”,则第7个抽屉为




















{26,27,28,29,30,31,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届数学竞赛试题。如果我们改变区间[](p
>q)端点的值,则又可以构造出一系列的新题目来 。
4.分析与解答:一个有着10个元素的集合,它共有多少个可能的子集呢?由于在组成一个子< br>集的时候,每一个元素都有被取过来或者不被取过来两种可能,因此,10个元素的集合就有
10
2=1024个不同的构造子集的方法,也就是,它一共有1024个不同的子集,包括空集和全集在内。空集与全集显然不是考虑的对象,所以剩下1024-2=1022个非空真子集。
再来看各个真子集中一切数字之和。用N来记这个和数,很明显:
10≤N≤91+92+93+94+95+96+97+98+99=855
这表明N至多只有 855-9=846种不同的情况。由于非空真子集的个数是1022,1022>846,
所以一定存 在两个子集A与B,
使得A中各数之和=B中各数之和。
若A∩B=φ,则命题 得证,若A∩B=C≠φ,即A与B有公共元素,这时只要剔除A与B
中的一切公有元素,得出两个不相 交的子集A
1
与B
1
,很显然
A
1
中各元 素之和=B
1
中各元素之和,因此A
1
与B
1
就是符合题目 要求的子集。
说明:本例能否推广为如下命题:
已给一个由m个互不相等的n 位十进制正整数组成的集合。求证:这个集合必有两个无
公共元素的子集合,各子集合中各数之和相等。
请读者自己来研究这个问题。
5.分析与解答:由中点坐标公式知,坐标平面两点(x
1
,y
1
)、(x
2
,y
2
)的中点坐标 是。
欲使都是整数,必须而且只须x
1
与x
2
,y
1
与y
2
的奇偶性相同。坐标平面上的任意整点
按照横纵两个坐标的奇偶性考虑有且只 有如下四种:(奇数、奇数),(偶数,偶数),(奇
数,偶数),(偶数,奇数)以此构造四个“抽屉 ”,则在坐标平面上任取五个整点,那么
至少有两个整点,属于同一个“抽屉”因此它们连线的中点就必 是整点。
说明:我们可以把整点的概念推广:如果(x
1
,x
2,…x
n
)是n维(元)有序数组,且x
1
,x
2
,… x
n
中的每一个数都是整数,则称(x
1
,x
2
,…xn
)是一个n维整点(整点又称格点)。如果对所有
的n维整点按每一个x
i的奇偶性来分类,由于每一个位置上有奇、偶两种可能性,因此共可
n3
分为2×2×…× 2=2个类。这是对n维整点的一种分类方法。当n=3时,2=8,此时可以构造
命题:“任意给定空 间中九个整点,求证它们之中必有两点存在,使连接这两点的直线段的
内部含有整点”。这就是1971 年的美国普特南数学竞赛题。在n=2的情形,也可以构造如下
的命题:“平面上任意给定5个整点”, 对“它们连线段中点为整点”的4个命题中,为真
命题的是:


(A)最少可为0个,最多只能是5个 (B)最少可为0个,最多可取10个
(C)最少为1个,最多为5个 (D)最少为1个,最多为10个
(正确答案(D)) 6.分析:本题也似乎是茫无头绪,无从下手,其关键何在?仔细审题,它们的“和”能“被
100 整除”应是做文章的地方。如果把这100个数排成一个数列,用S
m
记其前m项的和,则其< br>可构造S
1
,S
2
,…S
100
共100个和数。讨 论这些“和数”被100除所得的余数。注意到S
1

S
2
,…S< br>100
共有100个数,一个数被100除所得的余数有0,1,2,…99共100种可能性。 “苹
果”数与“抽屉”数一样多,如何排除“故障”?
证明:设已知的整数为a
1
,a
2
,…a
100
考察数列a
1
,a
2
,…a
100
的前n项和构成的数列S
1

S
2
,…S
100

如果S
1
,S
2
,…S
100
中有某个数可被100整除,则命题得证。否则,即S
1
,S
2
,…S
100
均不
能被100整除,这样,它们被100除后余数 必是{1,2,…,99}中的元素。由抽屉原理I知,
S
1
,S
2
,…S
100
中必有两个数,它们被100除后具有相同的余数。不妨设这两个数为S
i
,S
j
(i
<j),则100∣(S
j
-S
i< br>),即100∣。命题得证。
说明:有时候直接对所给对象作某种划分,是很难构造出恰 当的抽屉的。这时候,我们
需要对所给对象先作一些变换,然后对变换得到的对象进行分类,就可以构造 出恰当的抽屉。
本题直接对{a
n
}进行分类是很难奏效的。但由{a
n}构造出{S
n
}后,再对{S
n
}进行分类就容易得
多。
另外,对{S
n
}按模100的剩余类划分时,只能分成100个集合,而{S< br>n
}只有100项,似乎
不能应用抽屉原则。但注意到余数为0的类恰使结论成立,于是 通过分别情况讨论后,就可
去掉余数为0的类,从而转化为100个数分配在剩下的99个类中。这种处 理问题的方法应当
学会,它会助你从“山穷水尽疑无路”时,走入“柳暗花明又一村”中。
最后,本例的结论及证明可以推广到一般情形(而且有加强的环节):
在任意给定的n个整数中 ,都可以找出若干个数来(可以是一个数),它们的和可被n
整除,而且,在任意给定的排定顺序的n个 整数中,都可以找出若干个连续的项(可以是一
项),它们的和可被n整除。
将以上一 般结论中的n赋以相应的年份的值如1999,2000,2001…,就可以编出相应年
份的试题来。 如果再赋以特殊背景,则可以编出非常有趣的数学智力题来,如下题:
有100只猴子在吃花生 ,每只猴子至少吃了1粒花生,多者不限。请你证明:一定有若
干只猴子(可以是一只),它们所吃的花 生的粒数总和恰好是100的倍数。
7.证明:视17个科学家为17个点,每两个点之间连一 条线表示这两个科学家在讨论同
一个问题,若讨论第一个问题则在相应两点连红线,若讨论第2个问题则 在相应两点连条黄
线,若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找 到一
个三边同颜色的三角形。
考虑科学家A,他要与另外的16位科学家每人通信讨论 一个问题,相应于从A出发引出
16条线段,将它们染成3种颜色,而16=3×5+1,因而必有6= 5+1条同色,不妨记为AB
1
,AB
2

AB
3
,AB
4
,AB
5
,AB
6
同红色,若B
i
(i=1,2,…,6)之间有红线,则出现红色三角线,命题已
成立;否则B
1
, B
2
,B
3
,B
4
,B
5
,B
6
之间的连线只染有黄蓝两色。
考虑从B
1
引出的5条线,B
1
B
2
,B
1
B
3
,B
1
B4
,B
1
B
5
,B
1
B
6
, 用两种颜色染色,因为5=2×2+1,
故必有3=2+1条线段同色,假设为黄色,并记它们为B1
B
2
,B
1
B
3
,B
1
B
4
。这时若B
2
,B
3
,B
4
之间
有黄线,则有黄色三角形,命题也成立,若B
2
,B
3
,B
4,之间无黄线,则△B
2
,B
3
,B
4
,必为蓝
色三角形,命题仍然成立。
说明:(1)本题源于一个古典问题-- 世界上任意6个人中必有3人互相认识,或互相不
认识。(美国普特南数学竞赛题)。


(2)将互相认识用红色表示,将互相不认识用蓝色表示,(1)将化为一个染色问 题,
成为一个图论问题:空间六个点,任何三点不共线,四点不共面,每两点之间连线都涂上红
色或蓝色。求证:存在三点,它们所成的三角形三边同色。
(3)问题(2)可以往两个方向推广:其一是颜色的种数,其二是点数。
本例便是方向一的进展,其证明已知上述。如果继续沿此方向前进,可有下题:
在66个科学家 中,每个科学家都和其他科学家通信,在他们的通信中仅仅讨论四个题目,
而任何两个科学家之间仅仅讨 论一个题目。证明至少有三个科学家,他们互相之间讨论同一
个题目。
(4)回顾上面 证明过程,对于17点染3色问题可归结为6点染2色问题,又可归结为3
点染一色问题。反过来,我们 可以继续推广。从以上(3,1)→(6,2)→(17,3)的过程,
易发现
6=(3-1)×2+2,17=(6-1)×3+2,66=(17-1)×4+2,
同理可得 (66-1)×5+2=327,(327-1)×6+2=1958…记为r
1
=3,r2
=6,r
3
=17,r
4
=66,
r
5=327,r
6
=1958,…
我们可以得到递推关系式:r
n< br>=n(r
n-1
-1)+2,n=2,3,4…这样就可以构造出327点染5色问题,1958点染6色问题,都必出现一个同色三角形。









上教版高中数学高一课本答案-高中数学4-5试题


高中数学在线辅导老师-山西高中数学老师招聘信息


高中数学辅导电子书-广东省2018高中数学教材


高中数学费曼岛-高中数学满分突破第六季


高中数学概率乘法和加法-与高中数学有关的软件


高中数学哪个内容适合做微课-高中数学试题答题卡可改


高中数学题题及答案解析-教学反思总结百度文库高中数学


北京市高中数学会考答题卡-高中数学选修直线与椭圆的关系



本文更新与2020-09-17 19:48,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/401846.html

高中数学竞赛讲义抽屉原理的相关文章