当前位置:首页 >> 高三数学 >> 04【数学】高中数学竞赛讲义-抽屉原理

04【数学】高中数学竞赛讲义-抽屉原理


书利华教育网 www.shulihua.net 精心打造一流新课标资料

§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 个数,证明其中一定有两个数,它们中的一个是另一 个的整数倍。

书利华教育网 www.shulihua.net 精心打造一流新课标资料

书利华教育网 www.shulihua.net 精心打造一流新课标资料
3.从前 25 个自然数中任意取出 7 个数,证明:取出的数中一定有两个数,这两个数中大 数不超过小数的 1.5 倍。

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

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

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

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

例题答案:
1. 分析:5 个点的分布是任意的。如果要证明“在边长为 1 的等边三角形内(包括边

界)有 5 个点,那么这 5 个点中一定有距离不大于 的两点”,则顺次连接三角形三边中点,

书利华教育网 www.shulihua.net 精心打造一流新课标资料

书利华教育网 www.shulihua.net 精心打造一流新课标资料
即三角形的三条中位线,可以分原等边三角形为 4 个全等的边长为 的小等边三角形,则 5 个点中必有 2 点位于同一个小等边三角形中(包括边界),其距离便不大于 。 以上结论要由定理“三角形内 (包括边界) 任意两点间的距离不大于其最大边长”来保 证,下面我们就来证明这个定理。

如图 2,设 BC 是△ABC 的最大边,P,M 是△ABC 内(包括边界)任意两点,连接 PM, 过 P 分别作 AB、BC 边的平行线,过 M 作 AC 边的平行线,设各平行线交点为 P、Q、N,那么 ∠PQN=∠C,∠QNP=∠A 因为 BC≥AB,所以∠A≥∠C,则∠QNP≥∠PQN,而∠QMP≥∠QNP≥∠PQN(三角形的外 角大于不相邻的内角),所以 PQ≥PM。显然 BC≥PQ,故 BC≥PM。 由此我们可以推知,边长为 的等边三角形内(包括边界)两点间的距离不大于 。 说明: (1)这里是用等分三角形的方法来构造“抽屉”。类似地,还可以利用等分线段、等 分正方形的方法来构造“抽屉”。 例如“任取 n+1 个正数 ai, 满足 0<ai≤1 i=1,2,…,n+1) ( , 试证明:这 n+1 个数中必存在两个数,其差的绝对值小于 ”。又如:“在边长为 1 的正方

形内任意放置五个点,求证:其中必有两点,这两点之间的距离不大于 。 (2)例 1 中,如果把条件(包括边界)去掉,则结论可以修改为:至少有两个点之间 的距离小于 ",请读者试证之,并比较证明的差别。 (3)用同样的方法可证明以下结论: 2 2 i) 在边长为 1 的等边三角形中有 n +1 个点, n +1 个点中一定有距离不大于 的两点。 这 2 2 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 个奇数): 2 3 4 5 6 (1){1,1×2,1×2 ,1×2 ,1×2 ,1×2 ,1×2 }; 2 3 4 5 (2){3,3×2,3×2 ,3×2 ,3×2 ,3×2 }; 2 3 4 (3){5,5×2,5×2 ,5×2 ,5×2 }; 2 3 (4){7,7×2,7×2 ,7×2 }; 2 3 (5){9,9×2,9×2 ,9×2 }; 2 3 (6){11,11×2,11×2 ,11×2 };

书利华教育网 www.shulihua.net 精心打造一流新课标资料

书利华教育网 www.shulihua.net 精心打造一流新课标资料
…… (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}为一集合。

书利华教育网 www.shulihua.net 精心打造一流新课标资料

书利华教育网 www.shulihua.net 精心打造一流新课标资料
如此依次递推下去, 使若干个连续的自然数属于同一集合, 其中最大的数不超过最小的 数的 倍,就可以得到满足条件的六个集合。 (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 个元素的集合,它共有多少个可能的子集呢?由于在组成一个 子集的时候,每一个元素都有被取过来或者不被取过来两种可能,因此,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 中的一切公有元素,得出两个不相交的子集 A1 与 B1,很显然 A1 中各元素之和=B1 中各元素之和,因此 A1 与 B1 就是符合题目要求的子集。 说明:本例能否推广为如下命题: 已给一个由 m 个互不相等的 n 位十进制正整数组成的集合。 求证: 这个集合必有两个无 公共元素的子集合,各子集合中各数之和相等。 请读者自己来研究这个问题。 、 的中点坐标是 。 5. 分析与解答: 由中点坐标公式知, 坐标平面两点 1,y1) (x2,y2) (x 欲使 都是整数,必须而且只须 x1 与 x2,y1 与 y2 的奇偶性相同。坐标平面上的任意整点

按照横纵两个坐标的奇偶性考虑有且只有如下四种: (奇数、奇数), (偶数,偶数), (奇 数,偶数),(偶数,奇数)以此构造四个“抽屉”,则在坐标平面上任取五个整点,那么 至少有两个整点,属于同一个“抽屉”因此它们连线的中点就必是整点。 说明: 我们可以把整点的概念推广: (x1,x2,…xn) n 维 如果 是 (元) 有序数组, x1,x2,…xn 且 中的每一个数都是整数,则称(x1,x2,…xn)是一个 n 维整点(整点又称格点)。如果对所 有的 n 维整点按每一个 xi 的奇偶性来分类,由于每一个位置上有奇、偶两种可能性,因此 n 3 共可分为 2×2×…×2=2 个类。这是对 n 维整点的一种分类方法。当 n=3 时,2 =8,此时可

书利华教育网 www.shulihua.net 精心打造一流新课标资料

书利华教育网 www.shulihua.net 精心打造一流新课标资料
以构造命题:“任意给定空间中九个整点,求证它们之中必有两点存在,使连接这两点的直 线段的内部含有整点”。这就是 1971 年的美国普特南数学竞赛题。在 n=2 的情形,也可以 构造如下的命题: “平面上任意给定 5 个整点”, 对“它们连线段中点为整点”的 4 个命题 中,为真命题的是: (A)最少可为 0 个,最多只能是 5 个 (B)最少可为 0 个,最多可取 10 个 (C)最少为 1 个,最多为 5 个 (D)最少为 1 个,最多为 10 个 (正确答案(D)) 6.分析: 本题也似乎是茫无头绪,无从下手,其关键何在?仔细审题,它们的“和”能“被 100 整除”应是做文章的地方。如果把这 100 个数排成一个数列,用 Sm 记其前 m 项的和,则 其可构造 S1,S2,…S100 共 100 个"和"数。讨论这些“和数”被 100 除所得的余数。注意到 S1,S2,…S100 共有 100 个数,一个数被 100 除所得的余数有 0,1,2,…99 共 100 种可能性。 “苹果”数与“抽屉”数一样多,如何排除“故障”? 证明:设已知的整数为 a1,a2,…a100 考察数列 a1,a2,…a100 的前 n 项和构成的数列 S1, S2,…S100。 如果 S1,S2,…S100 中有某个数可被 100 整除,则命题得证。否则,即 S1,S2,…S100 均 不能被 100 整除,这样,它们被 100 除后余数必是{1,2,…,99}中的元素。由抽屉原理 I 知,S1,S2,…S100 中必有两个数,它们被 100 除后具有相同的余数。不妨设这两个数为 Si, 。命题得证。 Sj(i<j),则 100∣(Sj-Si),即 100∣ 说明:有时候直接对所给对象作某种划分,是很难构造出恰当的抽屉的。这时候,我们 需要对所给对象先作一些变换, 然后对变换得到的对象进行分类, 就可以构造出恰当的抽屉。 本题直接对{an}进行分类是很难奏效的。 但由{an}构造出{Sn}后, 再对{Sn}进行分类就容易得 多。 另外,对{Sn}按模 100 的剩余类划分时,只能分成 100 个集合,而{Sn}只有 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 条同色,不妨记为 AB1, AB2,AB3,AB4,AB5,AB6 同红色,若 Bi(i=1,2,…,6)之间有红线,则出现红色三角线, 命题已成立;否则 B1,B2,B3,B4,B5,B6 之间的连线只染有黄蓝两色。 考虑从 B1 引出的 5 条线,B1B2,B1B3,B1B4,B1B5,B1B6,用两种颜色染色,因为 5=2×2+1, 故必有 3=2+1 条线段同色,假设为黄色,并记它们为 B1B2,B1B3,B1B4。这时若 B2,B3,B4 之

书利华教育网 www.shulihua.net 精心打造一流新课标资料

书利华教育网 www.shulihua.net 精心打造一流新课标资料
间有黄线,则有黄色三角形,命题也成立,若 B2,B3,B4,之间无黄线,则△B2,B3,B4,必 为蓝色三角形,命题仍然成立。 说明:(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…记为 r1=3,r2=6,r3=17,r4=66, r5=327,r6=1958,… 我们可以得到递推关系式:rn=n(rn-1-1)+2,n=2,3,4…这样就可以构造出 327 点染 5 色 问题,1958 点染 6 色问题,都必出现一个同色三角形。

书利华教育网 www.shulihua.net 精心打造一流新课标资料


赞助商链接
更多相关文档:

23(高中竞赛讲座)抽屉原理

高中竞赛专题:抽屉原理试... 2页 2财富值 04【数学】高中数学竞赛讲... 7...高中数学竞赛讲座:抽屉原... 6页 免费 高中数学竞赛讲义-抽屉原理... 7页 ...

全国高中数学竞赛讲义-抽屉原理练习题

全国高中数学竞赛讲义-抽屉原理练习题 - §23 抽屉原理 课后练习 ? 1.幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件, 那么不管怎样挑选,...

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

高中数学竞赛讲义-抽屉原理_高三数学_数学_高中教育_教育专区。奥赛数学讲义 高考资源网(ks5u.com) 您身边的高考专家 §23 抽屉原理在数学问题中有一类与“存在性...

2011全国高中数学竞赛讲义-抽屉原理(练习题)

2011全国高中数学竞赛讲义... 3页 免费 04【数学】高中数学竞赛讲... 7页 ...//www.qyjzs.cn §23 抽屉原理课后练习≠ 1.幼儿园买来了不少白兔、熊猫、...

2011全国高中数学竞赛讲义23-抽屉原理

2011全国高中数学竞赛讲义23-抽屉原理_高二数学_数学_高中教育_教育专区。高中数学竞赛讲义数学教育网---数学试题-数学教案-数学课件-数学论文-竞赛试题-中高考试题信...

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

中学数学竞赛 抽屉原理讲义_数学_自然科学_专业资料。主要是增对高中数学联赛抽屉原理是每年数学竞赛的常考题。也是必考题第一专题 抽屉原理一、抽屉原理的基本形...

高中数学竞赛讲义1

01【数学】高中数学竞赛讲... 10页 5财富值 高中...定理6 抽屉原理:将 个元素放入 个抽屉,必有一个...例7 S 是集合{1,2,…,2004}的子集,S 中的...

13全国高中数学竞赛讲义-抽屉原理(练习题)

13全国高中数学竞赛讲义-抽屉原理(练习题) - §23 抽屉原理 课后练习 ? 1.幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件, 那么不管怎样...

高中数学竞赛讲义一

高中数学竞赛讲义一_学科竞赛_高中教育_教育专区。高中数学竞赛讲义共18讲高中...定理 5 最小数原理:自然数集的任何非空子集必有最小数。 定理 6 抽屉原理...

高中数学竞赛讲义_组合

高中数学竞赛讲义_组合_学科竞赛_高中教育_教育专区。高中数学竞赛讲义 组合 一、方法与例题 1.抽屉原理。 例 1 设整数 n≥4,a1,a2,?,an 是区间(0,2n)内...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com