设为首页 | 加入收藏夹

八文网 - 汇聚八方文档 - 做最优秀的免费文档下载网站

抽屉原理

文档类型：

Microsoft Word 文档文档大小：245KB

第五讲抽屉原理在数学问题中有一类与存在性有关的问题,例如:13个人中至少有两个人出生在相同月份;某校400名学生中、一定存在两名学生,他们在同一天过生日;2003个人任意分成200个小组,一定存在一组,其成员数不少于11;把[0,1]内的全部有理数放到100个集合中、一定存在一个集合,它里面有无限多个有理数.这类存在性问题中、存在的含义是至少有一个.在解决这类问题时,只要求指明存在,一般并不需要指出哪一个,也不需要确定通过什么方式把这个存在的东西找出来.这类问题相对来说涉及到的运算较少,依据的理论也不复杂,我们把这些理论称之为抽屉原理.
抽屉原理最先是由19世纪的德国数学家迪里赫莱(Dirichlet)运用于解决数学问题的,所以又称迪里赫莱原理,也有称鸽巢原理的.这个原理可以简单地叙述为把10个苹果,任意分放在9个抽屉里、则至少有一个抽屉里含有两个或两个以上的苹果.这个道理是非常明显的,但应用它却可以解决许多有趣的问题,并且常常得到一些令人惊异的结果.抽屉原理是国际国内各级各类数学竞赛中的重要内容、本讲就来学习它的有关知识及其应用.
(一) 抽屉原理的基本形式定理1,如果把n1个元素分成n个集合,那么不管怎么分,都存在一个集合,其中至少有两个元素.
证明:(用反证法)若不存在至少有两个元素的集合,则每个集合至多1个元素,从而n个集合至多有n个元素,此与共有n1个元素矛盾,故命题成立.
在定理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边的平行线,设各平行线交点为P,Q,N,那么因为BC≥AB,所以∠A≥∠C,则∠QNP≥∠PQN,而∠QMP≥∠QNP≥∠PQN(三角形的外角大于不相邻的内角),所以PQ≥PM.显然BC≥PQ,故BC≥PM.
由此我们可以推知,边长为的等边三角形内(包括边界)两点间的距离不大于.
说明:
(1)这里是用等分三角形的方法来构造抽屉.类似地,还可以利用等分线段,等分正方形的方法来构造抽屉.例如任取n1个正数ai,满足0n,由抽屉原则,结论就是必然的了.给n以具体值,就可以构造出不同的题目.例2中的n取值是50,还可以编制相反的题目,如:从前30个自然数中最少要(不看这些数而以任意方式地)取出几个数,才能保证取出的数中能找到两个数,其中较大的数是较小的数的倍数(2)如下两个问题的结论都是否定的(n均为正整数)想一想,为什么
①从n1中任取n1个数,是否必有两个数,它们中的一个是另一个的整数倍
②从n1中任取n1个数,是否必有两个数,它们中的一个是另一个的整数倍你能举出反例,证明上述两个问题的结论都是否定的吗(3)如果将(2)中两个问题中任取的n1个数增加1个,都改成任取n2个数,则它们的结论是肯定的还是否定的你能判断证明吗例3.从前25个自然数中任意取出7个数,证明:取出的数中一定有两个数,这两个数中大数不超过小数的1.5倍.
证明:把前25个自然数分成下面6组:1; ①
2,3; ②
③
④
⑤
⑥因为从前25个自然数中任意取出7个数,所以至少有两个数取自上面第②组到第⑥组中的某同一组,这两个数中大数就不超过小数的1.5倍.
(1)本题可以改变叙述如下:在前25个自然数中任意取出7个数,求证其中存在两个数,它们相互的比值在内.
显然,必须找出一种能把前25个自然数分成6(7-1=6)个集合的方法,不过分类时有一个限制条件:同一集合中任两个数的比值在内、故同一集合中元素的数值差不得过大.这样,我们可以用如上一种特殊的分类法:递推分类法:从1开始,显然1只能单独作为1个集合{1;否则不满足限制条件.
能与2同属于一个集合的数只有3,于是{2,3}为一集合.如此依次递推下去,使若干个连续的自然数属于同一集合,其中最大的数不超过最小的数的倍、就可以得到满足条件的六个集合.
(2)如果我们按照(1)中的递推方法依次造抽屉、则第7个抽屉为;
第8个抽屉为;
第9个抽屉为;
.
那么我们可以将例3改造为如下一系列题目:
(1)从前16个自然数中任取6个自然数;
(2)从前39个自然数中任取8个自然数;
(3)从前60个自然数中任取9个自然数;
(4)从前91个自然数中任取10个自然数.
都可以得到同一个结论:其中存在2个数,它们相互的比值在]内.上述第(4)个命题,就是前苏联基辅第49届数学竞赛试题.如果我们改变区间(p>q)端点的值,则又可以构造出一系列的新题目来.
例4.已给一个由10个互不相等的两位十进制正整数组成的集合.求证:这个集合必有两个无公共元素的子集合,各子集合中各数之和相等.(第14届1M0试题)
分析与解答:一个有着10个元素的集合,它共有多少个可能的子集呢由于在组成一个子集的时候,每一个元素都有被取过来或者不被取过来两种可能,因此,10个元素的集合就有210=1024个不同的构造子集的方法,也就是,它一共有1024个不同的子集,包括空集和全集在内.空集与全集显然不是考虑的对象,所以剩下1024-2=1022个非空真子集.
再来看各个真子集中一切数字之和.用N来记这个和数,很明显:
这表明N至多只有855-9=846种不同的情况.由于非空真子集的个数是>846,所以一定存在两个子集A与B,使得A中各数之和=B中各数之和.若A∩B=φ,则命题得证、若A∩B=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的奇偶性来分类,由于每一个位置上有奇,偶两种可能性,因此共可分为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除所得的余数有共100种可能性.苹果数与抽屉数一样多,如何排除故障
证明:设已知的整数为a1,a2.a100考察数列a1,a2.a100的前n项和构成的数列S1,S2.S100.
如果S1,S2.S100中有某个数可被100整除,则命题得证.否则,即S1,S2.S100均不能被100整除,这样,它们被100除后余数必是}中的元素.由抽屉原理I知,S1,S2.S100中必有两个数,它们被100除后具有相同的余数.不妨设这两个数为Si,Sj(in)
(1)当n能整除m时,至少有一个集合含有个元素;
(2)当n不能整除m时,则至少有一个集合含有至少1个元素,(表示不超过的最大整数)
定理2有时候也可叙述成:把m×n1个元素放进n个集合,则必有一个集合中至少放有m1个元素.
例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的面积=×=
说明:把正方形分成四个区域,可以得出至少有一个区域内有3个点的结论、这就为确定三角形面积的取值范围打下了基础.本题构造抽屉的办法不是唯一的,还可以将正方形等分成边长为的四个小正方形等.但是如将正方形等分成四个全等的小三角形却是不可行的(想一想为什么).所以适当地构造抽屉、正是应用抽屉原则解决问题的关键所在.
图5
以下两个题目可以看作是本例的平凡拓广:
(1)在边长为2的正方形内、随意放置9个点、证明:必有3个点、以它们为顶点的三角形的面积不超过.
(2)在边长为1的正方形内任意给出13个点.求证:必有4个点、以它们为顶点的四边形的面积不超过14.
例9.9条直线的每一条都把一个正方形分成两个梯形,而且它们的面积之比为2:3.证明:这9条直线中至少有3条通过同一个点.
证明:设正方形为ABCD,E,F分别是AB,CD的中点.设直线L把正方形ABCD分成两个梯形ABGH和CDHG,并且与EF相交于P(如图6)
梯形ABGH的面积:梯形CDHG的面积=2:3EP是梯形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×21,所以,必有一个抽屉内至少放有3个苹果,也就是,必有三条直线要通过一个点.
说明:本例中的抽屉比较隐蔽,正方形两双对边中点连线上的4个三等分点的发现是关键,而它的发现源于对梯形面积公式S梯形=中位线×梯形的高的充分感悟.
例10.910瓶红,蓝墨水,排成130行、每行7瓶.证明:不论怎样排列,红,蓝墨水瓶的颜色次序必定出现下述两种情况之一种:
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.在坐标平面上给出无限多个矩形,它们的顶点的直角坐标都具有如下形式:其中m,n是正整数,并且m>3,n

doc文档的标签：抽屉原理

更多推荐标签：下至未止射频功率计国际金融函电海尔购物平台重要物资外库一天记牢论文河南文化校长电话文员计划书管理学方科技类论文点维保合同空间中心网站区域方案成衣品牌战略股技术网站广告投放全面预算表格产品貭量合同直销公司会员贫困证明表格旅游可行性潍坊调查报告金融基础箱行基础近代中国主权法人任职报告年捡报告视听设备经济数学一