ImageVerifierCode 换一换
格式:DOC , 页数:7 ,大小:42.50KB ,
资源ID:1041202      下载积分:10 文钱
快捷下载
登录下载
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。 如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝    微信支付   
验证码:   换一换

加入VIP,省得不是一点点
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【https://www.wenke99.com/d-1041202.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: QQ登录   微博登录 

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文(数学竞赛讲座之抽屉原则.doc)为本站会员(bo****9)主动上传,文客久久仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知文客久久(发送邮件至hr@wenke99.com或直接QQ联系客服),我们立即给予删除!

数学竞赛讲座之抽屉原则.doc

1、竞赛讲座 10-抽屉原则大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉里,更一般地说,只要被放置的苹果数比抽屉数目大,就一定会有两只或更多只的苹果放进同一个抽屉,可不要小看这一简单事实,它包含着一个重要而又十分基本的原则抽屉原则.1 抽屉原则有几种最常见的形式原则 1 如果把 n+k(k1)个物体放进 n 只抽屉里,则至少有一只抽屉要放进两个或更多个物体:原则本身十分浅显,为了加深对它的认识,我们还是运用反证法给予证明;如果每个抽屉至多只能放进一个物体,那么物体的总数至多是 n,而不是题设的 n+k(k1),这不可能.原则虽简单.巧妙地运用原则却可十分便利地解决一些看上去相

2、当复杂、甚至感到无从下手的总是,比如说,我们可以断言在我国至少有两个人出生的时间相差不超过 4 秒钟,这是个惊人的结论,该是经过很多人的艰苦劳动,统计所得的吧!不,只须我们稍动手算一下:不妨假设人的寿命不超过 4 万天(约 110 岁,超过这个年龄数的人为数甚少),则10 亿人口安排在 8 亿 6 千 4 百万个“抽屉”里,根据原则 1,即知结论成立.下面我们再举一个例子:例 1 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.解 从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫

3、),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)把每种搭配方式看作一个抽屉,把 7 个小朋友看作物体,那么根据原则 1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.原则 2 如果把 mn+k(k1)个物体放进 n 个抽屉,则至少有一个抽屉至多放进 m+1 个物体.证明同原则相仿.若每个抽屉至多放进 m 个物体,那么 n 个抽屉至多放进 mn 个物体,与题设不符,故不可能.原则 1 可看作原则 2 的物例(m=1)例 2 正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.证明把两种颜色当作两

4、个抽屉,把正方体六个面当作物体,那么 6=22+2,根据原则二,至少有三个面涂上相同的颜色.例 3 把 1 到 10 的自然数摆成一个圆圈,证明一定存在在个相邻的数,它们的和数大于 17.证明 如图 12-1,设 a1,a 2,a 3,a 9,a 10分别代表不超过 10 的十个自然数,它们围成一个圈,三个相邻的数的组成是(a 1,a 2,a 3),(a 2,a 3,a 4),(a 3,a 4,a 5),,(a 9,a 10,a 1),(a 10,a 1,a 2)共十组.现把它们看作十个抽屉,每个抽屉的物体数是 a1+a2+a3,a 2+a3+a4,a 3+a4+a5,a 9+a10+a1,a

5、 10+a1+a2,由于(a 1+a2+a3)+(a 2+a3+a4)+(a 9+a10+a1)+(a 10+a1+a2)=3(a1+a2+a9+a10)=3(1+2+9+10)根据原则 2,至少有一个括号内的三数和不少于 17,即至少有三个相邻的数的和不小于 17.原则 1、原则 2 可归结到期更一般形式:原则 3 把 m1+m2+mn+k(k1)个物体放入 n 个抽屉里,那么或在第一个抽屉里至少放入 m1+1 个物体,或在第二个抽屉里至少放入 m2+1 个物体,或在第 n 个抽屉里至少放入 mn+1 个物体.证明假定第一个抽屉放入物体的数不超过 m1个,第二个抽屉放入物体的数不超过m2个,

6、第 n 个抽屉放入物体的个数不超过 mn,那么放入所有抽屉的物体总数不超过 m1+m2+mn个,与题设矛盾.例 4 有红袜 2 双,白袜 3 双,黑袜 4 双,黄袜 5 双,蓝袜 6 双(每双袜子包装在一起)若取出 9 双,证明其中必有黑袜或黄袜 2 双.证明 除可能取出红袜、白袜 3 双外.还至少从其它三种颜色的袜子里取出 4 双,根据原理 3,必在黑袜或黄袜、蓝袜里取 2 双.上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少.2 制造抽屉是运用原

7、则的一大关键首先要指出的是,对于同一问题,常可依据情况,从不同角度设计抽屉,从而导致不同的制造抽屉的方式.例 5 在边长为 1 的正方形内,任意给定 13 个点,试证:其中必有 4 个点,以此 4点为顶点的四边开面积不超过 (假定四点在一直线上构成面积为零的四边形).证明如图 12-2 把正方形分成四个相同的小正方形.因 13=34+1,根据原则 2,总有 4 点落在同一个小正方形内(或边界上),以此4 点为顶点的四边形的面积不超过小正方形的面积,也就不超过整个正方形面积的.事实上,由于解决问题的核心在于将正方形分割成四个面积相等的部分,所以还可以把正方形按图 12-3(此处无图)所示的形式分

8、割.合理地制造抽屉必须建立在充分考虑问题自身特点的基础上.例 6 在一条笔直的马路旁种树,从起点起,每隔一米种一棵树,如果把三块“爱护树木”的小牌分别挂在三棵树上,那么不管怎样挂,至少有两棵挂牌的树之间的距离是偶数(以米为单位),这是为什么?解如图 12-4(设挂牌的三棵树依次为 A、B、C.AB=a,BC=b,若 a、b 中有一为偶数,命题得证.否则 a、b 均为奇数,则 AC=a+b 为偶数,命题得证.下面我们换一个角度考虑:给每棵树上编上号,于是两棵树之间的距离就是号码差,由于树的号码只能为奇数和偶数两类,那么挂牌的三棵树号码至少有两个同为奇数或偶数,它们的差必为偶数,问题得证.后一证明

9、十分巧妙,通过编号码,将两树间距离转化为号码差.这种转化的思想方法是一种非常重要的数学方法例 7 从自然数 1,2,3,99,100 这 100 个数中随意取出 51 个数来,求证:其中一定有两个数,它们中的一个是另一个的倍数.分析设法制造抽屉:(1)不超过 50 个;(2)每个抽屉的里的数(除仅有的一个外),其中一个数是另一个数的倍数,一个自然数的想法是从数的质因数表示形式入手.解设第一个抽屉里放进数:1,12,12 2,12 3,12 4,12 5,12 6;第二个抽屉时放进数:3,32,32 2,32 3,32 4,32 5;第三个抽屉里放进数:5,52,52 2,52 3,52 4;第

10、二十五个抽屉里放进数:49,492;第二十六个抽屉里放进数:51.第五十个抽屉里放进数:99.那么随意取出 51 个数中,必有两个数同属一个抽屉,其中一个数是另一个数的倍数.制造抽屉并非总是一帆风顺的,有时要边制造边调整、改进.例 8 任意给定 7 个不同的自然数,求证其中必有两个整数,其和或差是 10 的倍数.分析注意到这些数队以 10 的余数即个位数字,以 0,1,9 为标准制造 10 个抽屉,标以0,1,9.若有两数落入同一抽屉,其差是 10 的倍数,只是仅有 7 个自然数,似不便运用抽屉原则,再作调整:6,7,8,9四个抽屉分别与4,3,2,1合并,则可保证至少有一个抽屉里有两个数,它

11、们的和或差是 10 的倍数.3 较复杂的问题须反复地运用抽屉原则,将复杂问题转化为简单问题.例 9 以(x,y,z)表示三元有序整数组,其中 x、y、z 为整数,试证:在任意七个三元整数组中,至少有两个三元数组,它们的 x、y、z 元中有两对都是奇数或都是偶数.分析 设七个三元素组为 A1(x 1,y 1,z 1)、A 2(x 2,y 2,z 2)、A 7(x 7,y 7,z 7).现在逐步探索,从 x 元开始,由抽屉原则,x 1,x2,x 7这七个数中,必定有四个数具有相同的奇偶性,不妨设这四个数是 x1,x 2,x 3,x 4且为偶数,接着集中考虑 A1、A 2、A 3、A 4这四组数的

12、y 元,若比如 y1,y 2,y 3,y 4中有两个是偶数,则问题已证,否则至多有一个是偶数,比如 y4是偶数,这时我们再来集中考虑 A1、A 2、A 3的 z 元.在 z1,z 2,z 3中,由抽屉原则必有两个数具有相同的奇偶性,如 z1、z 2,这时无论它们是奇数,还是偶数,问题都已得到证明.下面介绍一个著名问题.例 10 任选 6 人,试证其中必有 3 人,他们互相认识或都不认识.分析 用 A、B、C、D、E、F 表示这 6 个人,首先以 A 为中心考虑,他与另外五个人B、C、D、E、F 只有两种可能的关系:认识或不认识,那么由抽屉原则,他必定与其中某三人认识或不认识,现不妨设 A 认识

13、 B、C、D 三人,当 B、C、D 三人都互不认识时,问题得证;当 B、C、D 三人中有两人认识,如 B、C 认识时,则 A、B、C互相认识,问题也得证.本例和上例都采用了舍去保留、化繁为简、逐步缩小考虑范围的方法.例 11a,b,c,d 为四个任意给定的整数,求证:以下六个差数b-a,c-a,d-a,c-b,d-b,d-c 的乘积一定可以被 12 整除.证明 把这 6 个差数的乘积记为 p,我们必须且只须证明:3 与 4 都可以整除 p,以下分两步进行.第一步,把 a,b,c,d 按以 3 为除数的余数来分类,这样的类只有三个,故知a,b,c,d 中至少有 2 个除以 3 的余数相同,例如,

14、不妨设为 a,b,这时 3 可整除 b-a,从而 3 可整除 p.第二步,再把 a,b,c,d 按以 4 为除数的余数来分类,这种类至多只有四个,如果 a,b,c,d 中有二数除以 4 的余数相同,那么与第一步类似,我们立即可作出4 可整除 p 的结论.设 a,b,c,d 四数除以 4 的余数不同,由此推知,a,b,c,d 之中必有二个奇数(不妨设为 a,b),也必有二个偶数(设为 c,d),这时 b-a 为偶数,d-c 也是偶数,故 4 可整除(b-a)(d-c),自然也可得出 4 可整除 p.如果能进一步灵活运用原则,不仅制造抽屉,还根据问题的特征,制造出放进抽屉的物体,则更可收到意想不到

15、的效果.例 12 求证:从任意 n 个自然数 a1,a 2,a n中可以找到若干个数,使它们的和是 n 的倍数.分析以 0,1,n-1 即被 n 除的余数分类制造抽屉的合理的,但把什么样的数作为抽屉里的物体呢?扣住“和”,构造下列和数:S1=a1,S2=a1+a2,S=a1+a2+a3,Sn=a1+a2+an,其中任意两个和数之差仍为和数,若他们之中有一是 n 的倍数,问题得证,否则至少有两个数被 n 除余数相同,则它们的差即它们中若干数(包括 1 个)的和是 n 的倍数,问题同样得证.例子 3(北京 1990 年高一竞赛)910 瓶红、蓝墨水,排成 130 行,每行 7 瓶,证明:不论怎样排

16、列,红蓝墨水瓶的颜色次序必定出现下述两种情况之一种:(1)至少有三行完全相同;(2)至少有两组(四行)每组的两行完全相同.解 910 瓶红、蓝墨水排成 130 行,每行 7 瓶,对一行来说,每个位置上有红蓝两种可能,因此,一行的红、蓝墨水排法有 27=128 种,对每一种不同排法设为一种“行式”,共有 128 种行式.现有 130 行,在其中任取 129 行,依抽屉原则知,必有两行 A、B 行式相同.除 A、B 外余下 128 行,若有一行 P 与 A 行式相同,知满足(1)至少有三行A、B、P 完全相同,若在这 128 行中设直一行 5A 行或相同,那么这 128 行至多有127 种行式,依抽屉原则,必有两行 C、D 具有相同行式,这样便找到了(A、B),(C、D)两组(四行),且两组两行完全相同.

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。