当前位置:首页 >> 高二数学 >> 1002

1002


http://www.cenre.com/teacher/special/onespecial4.asp?id=329

高中数学竞赛系列讲座——抽屉原理 高中数学竞赛系列讲座——抽屉原理 ——
在数学问题中有一类与"存在性"有关的问题,例如:"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) . 证明:至少有两个点之间的距离不大于 (1978 年广东省数学竞赛题) 分析: 个点的分布是任意的. 5 如果要证明"在边长为 1 的等边三角形内 (包 括边界)有 5 个点,那么这 5 个点中一定有距离不大于 的两点",则顺次连接 三角形三边中点,即三角形的三条中位线,可以分原等边三角形为 4 个全等的边 长为 的小等边三角形,则 5 个点中必有 2 点位于同一个小等边三角形中(包括 边界) ,其距离便不大于 . 以上结论要由定理"三角形内(包括边界)任意两点间的距离不大于其最大 边长"来保证,下面我们就来证明这个定理.

如图 2,设 BC 是△ABC 的最大边,P,M 是△ABC 内(包括边界)任意两点, 连接 PM,过 P 分别作 AB,BC 边的平行线,过 M 作 AC 边的平行线,设各平行线
第 1 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

交点为 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)用同样的方法可证明以下结论: i)在边长为 1 的等边三角形中有 n2+1 个点,这 n2+1 个点中一定有距离不大 于 的两点. 2 2 ii)在边长为 1 的等边三角形内有 n +1 个点,这 n +1 个点中一定有距离小 于 的两点. (4)将(3)中两个命题中的等边三角形换成正方形,相应的结论中的 换 成 ,命 题仍然成立. (5)读者还可以考虑相反的问题:一般地,"至少需要多少个点,才能够 使得边长 为 1 的正三角形内(包括边界)有两点其距离不超过 ". 例 2.从 1-100 的自然数中,任意取出 51 个数,证明其中一定有两个数, 它们中的一个是另一个的整数倍. 分析:本题似乎茫无头绪,从何入手?其关键何在?其实就在"两个数", 其中一个是另一个的整数倍. 我们要构造"抽屉", 使得每个抽屉里任取两个数, 都有一个是另一个的整数倍, 这只有把公比是正整数的整个等比数列都放进去同 一个抽屉才行,这里用得到一个自然数分类的基本知识:任何一个正整数都可以 表示成一个奇数与 2 的方幂的积,即若 m∈N+,K∈N+,n∈N,则 m=(2k-1)2n, 并且这种表示方式是唯一的,如 1=1×2°,2=1×21,3=3×2°,…… 证明:因为任何一个正整数都能表示成一个奇数乘 2 的方幂,并且这种表示 方法是唯一的,所以我们可把 1-100 的正整数分成如下 50 个抽屉(因为 1-100 中共有 50 个奇数) : (1){1,1×2,1×22,1×23,1×24,1×25,1×26}; (2){3,3×2,3×22,3×23,3×24,3×25};
第 2 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

(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 }; …… (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 个自然数中任意取出 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 个数,求证其 中存在两个数,它们相互的比值在 内.

2

3

4

第 3 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

显然,必须找出一种能把前 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 个互不相等的两位十进制正整数组成的集合.求证: 这个集合必有两个无公共元素的子集合,各子集合中各数之和相等.(第 14 届 1M0 试题) 分析与解答:一个有着 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 位十进制正整数组成的集合.求证:这个集合 必有两个无公共元素的子集合,各子集合中各数之和相等. 请读者自己来研究这个问题.
第 4 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

例 5.在坐标平面上任取五个整点(该点的横纵坐标都取整数),证明:其 中一定存在两个整点,它们的连线中点仍是整点. 分析与解答:由中点坐标公式知,坐标平面两点(x1,y1),(x2,y2)的中点 坐标是 .欲使 都是整数,必须而且只须 x1 与 x2,y1 与 y2 的奇偶性相同. 坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有 如下四种:(奇数,奇数),(偶数,偶数),(奇数,偶数),(偶数,奇数) 以此构造四个"抽屉",则在坐标平面上任取五个整点,那么至少有两个整点, 属于同一个"抽屉"因此它们连线的中点就必是整点. 说明:我们可以把整点的概念推广:如果(x1,x2,…xn)是 n 维(元)有序 数组,且 x1,x2,…xn 中的每一个数都是整数,则称(x1,x2,…xn)是一个 n 维整点 (整点又称格点).如果对所有的 n 维整点按每一个 xi 的奇偶性来分类,由于 每一个位置上有奇,偶两种可能性,因此共可分为 2×2×…×2=2n 个类.这是 对 n 维整点的一种分类方法.当 n=3 时,23=8,此时可以构造命题:"任意给定 空间中九个整点,求证它们之中必有两点存在,使连接这两点的直线段的内部含 有整点".这就是 1971 年的美国普特南数学竞赛题.在 n=2 的情形,也可以构 造如下的命题:"平面上任意给定 5 个整点",对"它们连线段中点为整点"的 4 个命题中,为真命题的是: (A)最少可为 0 个,最多只能是 5 个 (B)最少可为 0 个,最多可取 10 个 (C)最少为 1 个,最多为 5 个 (D)最少为 1 个,最多为 10 个 (正确答案(D)) 例 6. 在任意给出的 100 个整数中, 都可以找出若干个数来 (可以是一个数) , 它们的和可被 100 整除. 分析:本题也似乎是茫无头绪,无从下手,其关键何在?仔细审题,它们的 "和"能"被 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 个数分配在剩下的
第 5 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

99 个类中.这种处理问题的方法应当学会,它会助你从"山穷水尽疑无路"时, 走入"柳暗花明又一村"中. 最后,本例的结论及证明可以推广到一般情形(而且有加强的环节): 在任意给定的 n 个整数中,都可以找出若干个数来(可以是一个数),它们 的和可被 n 整除,而且,在任意给定的排定顺序的 n 个整数中,都可以找出若干 个连续的项(可以是一项),它们的和可被 n 整除. 将以上一般结论中的 n 赋以相应的年份的值如 1999,2000,2001…,就可 以编出相应年份的试题来.如果再赋以特殊背景,则可以编出非常有趣的数学智 力题来,如下题: 有 100 只猴子在吃花生, 每只猴子至少吃了 1 粒花生, 多者不限. 请你证明: 一定有若干只猴子(可以是一只),它们所吃的花生的粒数总和恰好是 100 的倍 数. (二)于无声处听惊雷--单色三角形问题 前面数例我们看到, 抽屉原理的应用多么奇妙, 其关键在于恰当地制造抽屉, 分割图形, 利用自然数分类的不同方法如按剩余类制造抽屉或按奇数乘以 2 的方 幂制造抽屉,利用奇偶性等等,都是制造"抽屉"的方法.大家看到,抽屉原理 的道理极其简单,但"于无声处听惊雷",恰当地精心地应用它,不仅可以解决 国内数学竞赛中的问题, 而且可以解决国际中学生数学竞赛, 例如 IM0 中的难题. 本节我们就来看几个这样的例子. 例 7. (第 6 届国际中学生数学奥林匹克试题)17 名科学家中每两名科学家 都和其他科学家通信,在他们通信时,只讨论三个题目,而且任意两名科学家通 信时只讨论一个题目,证明:其中至少有三名科学家,他们相互通信时讨论的是 同一个题目. 证明:视 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 之间有黄线,则有黄色三角形,命题也成立,若 B2,B3, B4,之间无黄线,则△B2,B3,B4,必为蓝色三角形,命题仍然成立. 说明:(1)本题源于一个古典问题--世界上任意 6 个人中必有 3 人互相认 识,或互相不认识.(美国普特南数学竞赛题). (2)将互相认识用红色表示,将互相不认识用蓝色表示,(1)将化为一个 染色问题,成为一个图论问题:空间六个点,任何三点不共线,四点不共面,每 两点之间连线都涂上红色或蓝色. 求证: 存在三点, 它们所成的三角形三边同色. (3)问题(2)可以往两个方向推广:其一是颜色的种数,其二是点数. 本例便是方向一的进展,其证明已知上述.如果继续沿此方向前进,可有下 题:
第 6 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

在 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, 2=6, 3=17, r r r4=66,r5=327,r6=1958,… 我们可以得到递推关系式: n=n(rn-1-1)+2, r n=2,3,4…这样就可以构造出 327 点染 5 色问题,1958 点染 6 色问题,都必出现一个同色三角形. (三)抽屉原理的其他形式. 在例 7 的证明过程中,我们实际上用到了抽屉原理的其他形式,我们把它作 为定理 2. 定理 2:把 m 个元素分成 n 个集合(m>n) (1)当 n 能整除 m 时,至少有一个集合含有 个元素; ([ ] (2) n 不能整除 m 时, 当 则至少有一个集合含有至少[ ]+1 个元素, 表示不超过 的最大整数) 定理 2 有时候也可叙述成:把 m×n+1 个元素放进 n 个集合,则必有一个集 合中至少放有 m+1 个元素. 例 8.在边长为 1 的正方形内任意放入九个点,求证:存在三个点,以这三 个点为顶点的三角形的面积不超过 (1963 年北京市数学竞赛题). 分析与解答:如图 3,四等分正方形,得到 A1,A2,A3,A4 四个矩形.在正 方形内任意放入九个点,则至少有一个矩形 Ai 内存在[ ]+1=3 个或 3 个以上的 点,设三点为 A,B,C,具体考察 Ai(如图 4),过 A,B,C 三点分别作矩形长 边的平行线,过 A 点的平行线交 BC 于 A'点,A 点到矩形长边的距离为 h=(0≤h ≤ ),则△ABC 的面积

S△ABC=S△AA'C+S△AA'B ≤ ×1×h+ ×1×( -h) = × =

第 7 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

说明:把正方形分成四个区域,可以得出"至少有一个区域内有 3 个点"的 结论,这就为确定三角形面积的取值范围打下了基础.本题构造"抽屉"的办法 不是唯一的,还可以将正方形等分成边长为 的四个小正方形等.但是如将正方 形等分成四个全等的小三角形却是不可行的(想一想为什么?).所以适当地构 造"抽屉",正是应用抽屉原则解决问题的关键所在.

图5 以下两个题目可以看作是本例的平凡拓广: (1)在边长为 2 的正方形内,随意放置 9 个点,证明:必有 3 个点,以它 们为顶点的三角形的面积不超过 . (2)在边长为 1 的正方形内任意给出 13 个点.求证:必有 4 个点,以它们 为顶点的四边形的面积不超过 1/4. 例 9.9 条直线的每一条都把一个正方形分成两个梯形,而且它们的面积之 比为 2:3.证明:这 9 条直线中至少有 3 条通过同一个点. 证明:设正方形为 ABCD,E,F 分别是 AB,CD 的中点. 设直线 L 把正方形 ABCD 分成两个梯形 ABGH 和 CDHG, 并且与 EF 相交于 P(如图 6) 梯形 ABGH 的面积:梯形 CDHG 的面积=2:3 EP 是梯形 ABGH 的中位线,PF 是梯形 CDHG 的中位线, 由于 梯形的面积=中位线×梯形的高,并且两个梯形的高相等(AB=CD),所以 梯形 ABGH 的面积:梯形 CDHG 的面积 =EP:PF,也就是 EP:PF=2:3 这说明,直线 L 通过 EF 上一个固定的点 P,这个点把 EF 分成长度为 2:3 的两部分.这样的点在 EF 上还有一个,如图上的 Q 点(FQ:QE=2:3). 同样地,如果直线 L 与 AB,CD 相交,并且把正方形分成两个梯形面积之比 是 2:3, 那么这条直线必定通过 AD, 中点连线上的两个类似的点 BC (三等分点) . 这样, 在正方形内就有 4 个固定的点, 凡是把正方形面积分成两个面积为 2: 3 的梯形的直线,一定通过这 4 点中的某一个.我们把这 4 个点看作 4 个抽屉, 9 条直线看作 9 个苹果,由定理 2 可知, 9=4×2+1, 所以,必有一个抽屉内至少放有 3 个苹果,也就是,必有三条直线要通过一 个点. 说明:本例中的抽屉比较隐蔽,正方形两双对边中点连线上的 4 个三等分点 的发现是关键,而它的发现源于对梯形面积公式 S 梯形=中位线×梯形的高的充 分感悟. 例 10.910 瓶红,蓝墨水,排成 130 行,每行 7 瓶.证明:不论怎样排列, 红,蓝墨水瓶的颜色次序必定出现下述两种情况之一种:
第 8 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

1.至少三行完全相同; 2.至少有两组(四行),每组的两行完全相同.(北京市高中一年级数学 竞赛 1990 年复赛试题) 证明:910 瓶红,蓝墨水,排成 130 行,每行 7 瓶.每行中的 7 个位置中的 每个位置都有红,蓝两种可能,因而总计共有 27=128 种不同的行式(当且仅当 两行墨水瓶颜色及次序完全相同时称为"行式"相同) 任取 130 行中的 129 行,依抽屉原理可知,必有两行(记为 A,B)"行式" 相同. 在除 A,B 外的其余 128 行中若有一行 P 与 A(B)"行式"相同,则 P,A, B 满足"至少有三行完全相同";在其余(除 A,B 外)的 128 行中若没有与 A (B)行式相同者,则 128 行至多有 127 种不同的行式,依抽屉原则,必有两行 (不妨记为 C,D)行式相同,这样便找到了(A,B),(C,D)两组(四行), 每组两行完全相同. 说明: 本例构造抽屉时用到了乘法原理, 2×2×2×2×2×2×2=27=128 个 "行 式"是制造和应用抽屉原理的关键. (四)抽屉原理的无限形式 定理 3.如果把无穷多个元素分成 n 个集合,那么不管怎么分,都至少存在 一个集合,其中有无穷多个元素. 例 11.在坐标平面上给出无限多个矩形,它们的顶点的直角坐标都具有如 下形式: (0,0),(0,m ),(n,0),(n,m) 其中 m,n 是正整数,并且 m>3,n<6,求证:在这些矩形中一定存在无限 多个矩形,其中任意两个矩形必有一个被包含在另一个之中. 证明:由 n<6 知,n=1,2,3,4,5,只有 5 种情形,由定理 3 知,将所给的无 穷多个矩形按 n 的取值分成 5 类,当作 5 个抽屉,其中必有一个抽屉(一类)里 包含有无穷多个矩形.不妨设这一类矩形的 n 的取值为 n.对于这一类矩形中的 任意两个矩形而言,由于 n 的取值相同,因此 m 取值较小的一个矩形必然被包含 在 m 取值较大的一个矩形之中. (五)抽屉原理的多次使用. 在例 7 的解答中, 我们已经看到了多次使用抽屉原理的方法, 下面再看两例. 例 12.有苹果,梨,桔子若干个,任意分成 9 堆,求证一定可以找到两堆, 其苹果数,梨数,桔子数分别求和都是偶数. 证明:因为每一堆里的每一种水果数或为奇数或为偶数(两个抽屉),而 9=2×4+1,故对于苹果,9 堆中必有 5 堆的奇偶性相同;这 5 堆对于梨数来说, 由于 5=2×2+1,故必有 3 堆的奇偶性相同;这 3 堆对于桔子数也必有 2 堆的奇 偶性相同.于是,就找到这样的两堆,它们的苹果数,梨数,桔子数的奇偶性都 分别相同,从而其和数分别都是偶数. 说明:为了得出和是偶数,需要两加数的奇偶性相同.对 3 类水果逐一找用 了 3 次抽屉原理, 若将过程合并简化可将苹果数, 梨数, 桔子数作为 3 锥坐标 (X, Y,Z),按其坐标的奇偶性构造 8 个抽屉: (奇,奇,奇),(奇,奇,偶),(奇,偶,奇),(偶,奇,奇), (奇,偶,偶),(偶,奇,偶),(偶,偶,奇),(偶,偶,偶),9 堆当中必有 2 堆属于同一抽屉,其坐标的奇偶性完全相同.(参考例 5 说明)

第 9 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

例 13.(1995 年全国高中数学联赛试题)将平面上每个点以红蓝两色之一 着色,证明:存在这样的两个相似三角形,它们的相似比为 1995,并且每一个 三角形的三个顶点同色. 证明:如图 7,作两个半径分别为 1 和 1995 的同心 圆,在内圆上任取 9 个点,必有 5 点同色,记为 A1,A2, A3,A4,A5.连半径 0Ai 交大圆于 Bi(i=1,2,3,4,5),对 B1,B2,B3,B4,B5,必有 3 点同色,记为 Bi,Bj,Bk,则△ BiBjBk 与△AiAjAk 为三项点同色的位似三角形,位似比等 于 1995,满足题设条件. 说明: 这里连续用了两次抽屉原理 (以染色作抽屉) . 也可以一开始就取位似比为 1995 的 9 个位似点组 i,Bi) (A (i=1,2,3,…,9),对 4 个抽屉(红,红),(红,蓝),(蓝,红),(蓝, 蓝)应用抽屉原理,得出必有 3 个位似点属于同一抽屉,从题目的证明过程中可 以看出,位似比 1995 可以改换成另外一个任意的正整数,正实数.当然,不用 同心圆也可证得,如在平面上取任三点都不共线的 9 点,由抽屉原理必有 5 点同 色,设为 A,B,C,D,E;以 A 为位似中心,以 1995 为位似比作 ABCDE 的位似 形 A'B'C'D'E',则 5 点 A,B',C',D',E'中必有 3 点同色,设为 B'D'E',则即为 所求.

更一般地可以证明,在这个二染色的平面上存在无数个内角为 30°,60°, 90°的直角三角形三顶点同色:任取 a∈R+,以 a 为边作等边三角形,则必有两 点同色,记为 A,B 同红色,以 AB 为直径作一圆,再作圆内接正六边形 AC1C2BC3C4 (如图 9),当 Ci 中有红点时△ACiB 即为所求;当 Ci 中无红点即 Ci 全为蓝色时, Rt△C1C2C3 即为所求.再由 a 的任意性知,这样的三角形有无数个. 更进一步还可得到:对任何 a∈R+,可得到两个相似比为 a 的顶点同色的相 似三角形.对于多染色的情形,还可以得出多个相似三角形的结论:用红,黄, 蓝三种颜色对平面上的点染色,对任意的 a,b∈R+,必存在三个三角形,它们彼 此相似,相似比为 1:a:b,且每个三角形的三顶点同色.请读者试证. 练习五 1.从集合 A={1,2,…,2n}中任取 n+1 个数,证明:其中必有 2 个数互质. 2.任意给定 7 个整数,求证:其中必有两个数,其和或差可被 10 整除. 3.任给 7 个实数,求证:其中必有至少两个数(记为 x,y)满足 0≤ ≤

4.给定 n+1 正整数所组成的集合,其中每个数都不超过 2n,证明:这个集 合中至少有一个元素能整除另一个元素. 5.设 a1,a2,…,an 是 n 个自然数,证明:从这 n 个数中总可以选出若干个数,
第 10 页 共 11 页

http://www.cenre.com/teacher/special/onespecial4.asp?id=329

使它们的和是 n 的倍数. 6.求证:平面上任意 13 个整点中,必有某 4 个点的重心为整点. 7.任给 5 个整数,证明:必然从其中选出 3 个,使得它们的和被 3 整除.

需要更多高中数学竞赛资料,请点击: 需要更多高中数学竞赛资料,请点击: http://www.cenre.com/teacher/special/onespecial4.a sp?id=329

第 11 页 共 11 页


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

BSD-1002E设备接地在线监控仪说明书

BSD-1002E 手腕带在线接地监测仪 说明书手腕带在线监测仪是连续,准确,快速地监测人体配带的手腕带接地状态,具有声光自动报警功能。使用简单, 工作无噪音,可为防...

QBT1002-2015 更新与应对

QBT1002-2015 更新与应对_纺织/轻工业_工程科技_专业资料。电商资质测试标准(国标) 由中华人民共和国工业和信息化部发布的 QB/T 1002-2015《皮鞋》标准于 2016...

1002银行存款

1002银行存款_金融/投资_经管营销_专业资料。总页: 1002 银行存款 总分类帐 会计 记帐 总页: 帐户编号及名称 12 年 凭证 号数 摘要 借(收)方千百十万千百十...

ISMS-1002信息安全适用性声明

ISMS-1002信息安全适用性声明_生产/经营管理_经管营销_专业资料。有限公司 信息安全适用性声明 编号:ISMS-1002 编写:行政部 审核:印峰 批准:邓庆平 发布版次:第 ...

内置肖特基二极管YY1002,可替代QX2304

33:3.3V YY1002_DS01CN 深圳市芯为电子技术有限公司 2 www.szseven.cn YY1002 高效率同步升压 DC-DC 变换器封装及管脚分配 VOUT 3 LX 5 GND 4 DXXX 1...

QSY1002.2健康、安全与环境管理体系 第2部分:实施指南-...

II Q/SY 1002.2-20XX 健康、安全与环境管理体系 1 范围 第 2 部分: 实施指南 本部分给出了组织建立、实施、保持和改进健康、安全与环境管理体系的指南。 本...

服务器编译链接1002_$

服务器编译链接1002_$_电脑基础知识_IT/计算机_专业资料。编译: 编译器对源代码进行编译,是将以文本形式存在的源代码翻译为机器语言 形式的目标文件的过程。 编译...

QSY1002.3-2008健康、安全与环境管理体系 第3部分:审核...

13 I Q/SY 1002.3-2008 前 言 Q/SY 1002 《健康、安全与环境管理体系》分为三个部分: ——第 1 部分:规范; ——第 2 部分:实施指南; ——第 3 ...

GA_1002-2012

GA 1002-2012 剧毒化学品、放射源存放场所治安防范要求 l 范围 本标准规定了剧毒化学品、放射源存放场地(部位) 风险等级划分与治安防范级别、治安防 范要求和管理...

B1002

B1002_信息与通信_工程科技_专业资料。儿科学—理论综合(B1 第二分册) 第1页 ——— B1 型题 (最佳配伍型) 每一道题有 A,B,C,D,E 五个备选答案,然后...

更多相关标签:
网站地图

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