高中数学竞赛讲座 10抽屉原则
上传者:卢海涛|上传时间:2015-04-15|密次下载
高中数学竞赛讲座 10抽屉原则
竞赛讲座10
--抽屉原则
大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉里,更一般地说,只要被放置的苹果数比抽屉数目大,就一定会有两只或更多只的苹果放进同一个抽屉,可不要小看这一简单事实,它包含着一个重要而又十分基本的原则——抽屉原则.
1. 抽屉原则有几种最常见的形式
原则1 如果把n+k(k≥1)个物体放进n只抽屉里,则至少有一只抽屉要放进两个或更多个物体:
原则本身十分浅显,为了加深对它的认识,我们还是运用反证法给予证明;如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
原则虽简单.巧妙地运用原则却可十分便利地解决一些看上去相当复杂、甚至感到无从下手的总是,比如说,我们可以断言在我国至少有两个人出生的时间相差不超过4秒钟,这是个惊人的结论,该是经过很多人的艰苦劳动,统计所得的吧!不,只须我们稍动手算一下:
不妨假设人的寿命不超过4万天(约110岁,超过这个年龄数的人为数甚少),则
内容需要下载文档才能查看
10亿人口安排在8亿6千4百万个“抽屉”里,根据原则1,即知结论成立. 下面我们再举一个例子:
例1 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.
解 从三种玩具中挑选两件,搭配方式只能是下面六种:
(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)
把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原则1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.
原则2 如果把mn+k(k≥1)个物体放进n个抽屉,则至少有
一个抽屉至多放进m+1个物体.证明同原则相仿.若每个抽
屉至多放进m个物体,那么n个抽屉至多放进mn个物体,
与题设不符,故不可能.
原则1可看作原则2的物例(m=1)
例2正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.
证明把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原则二,至少有三个面涂上相同的颜色.
例3 把1到10的自然数摆成一个圆圈,证明一定存在在个相邻的数,它们的和数大于17.
证明 如图12-1,设a1,a2,a3, ,a9,a10分别代表不超过10的十个自然数,它们围成一个圈,三个相邻的数的组成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5), ,(a9,a10,a1),(a10,a1,a2)共十组.现把它们看作十个抽屉,每个抽屉的物体数是a1+a2+a3,a2+a3+a4,a3+a4+a5, a9+a10+a1,a10+a1+a2,由于
(a1+a2+a3)+(a2+a3+a4)+ +(a9+a10+a1)+(a10+a1+a2)
=3(a1+a2+ +a9+a10)
=3×(1+2+ +9+10)
内容需要下载文档才能查看
根据原则2,至少有一个括号内的三数和不少于17,即至少有三个相邻的数的和不小于17.
原则1、原则2可归结到期更一般形式:
原则3把m1+m2+ +mn+k(k≥1)个物体放入n个抽屉里,那么或在第一个抽屉里至少放入m1+1个物体,或在第二个抽屉里至少放入m2+1个物体, ,或在第n个抽屉里至少放入mn+1个物体.
证明假定第一个抽屉放入物体的数不超过m1个,第二个抽屉放入物体的数不超过m2个, ,第n个抽屉放入物体的个数不超过mn,那么放入所有抽屉的物体总数不超过m1+m2+ +mn个,与题设矛盾.
例4 有红袜2双,白袜3双,黑袜4双,黄袜5双,蓝袜6双(每双袜子包装在一起)若取出9双,证明其中必有黑袜或黄袜2双
内容需要下载文档才能查看.
证明 除可能取出红袜、白袜3双外.还至少从其它三种颜色的袜子里取出4双,根据原理3,必在黑袜或黄袜、蓝袜里取2双.
上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少.
2. 制造抽屉是运用原则的一大关键
首先要指出的是,对于同一问题,常可依据情况,从不同角度设计抽屉,从而导致不同的制造抽屉的方式.
例5 在边长为1的正方形内,任意给定13个点,试证:其中必有4个点,以此4点为顶点的四边开面积不超过(假定四点在一直线上构成面积为零的四边形). 证明如图12-2把正方形分成四个相同的小正方形.
因13=3×4+1,根据原则2,总有4点落在同一个小正方形内(或边界上),以此4点为顶点的四边形的面积不超过小正方形的面积,也就不超过整个正方形面积的
内容需要下载文档才能查看 内容需要下载文档才能查看.
事实上,由于解决问题的核心在于将正方形分割成四个面积相等的部分,所以还可以把正方形按图12-3(此处无图)所示的形式分割.
合理地制造抽屉必须建立在充分考虑问题自身特点的基础上.
例6 在一条笔直的马路旁种树,从起点起,每隔一米种一棵树,如果把三块“爱护树木”的小牌分别挂在三棵树上,那么不管怎样挂,至少有两棵挂牌的树之间的距离是偶数(以米为单位),这是为什么?
解如图12-4(设挂牌的三棵树依次为A、B、C.AB=a,BC=b,若a、b中有一为偶数,命题得证.否则a、b均为奇数,则AC=a+b为偶数,命题得证.
下面我们换一个角度考虑:给每棵树上编上号,于是两棵树之间的距离就是号码差,由于树的号码只能为奇数和偶数两类,那么挂牌的三棵树号码至少有两个同为奇数或偶数,它们的差必为偶数,问题得证.
后一证明十分巧妙,通过编号码,将两树间距离转化为号码差.这种转化的思想方法是一种非常重要的数学方法
内容需要下载文档才能查看
例7 从自然数1,2,3, 99,100这100个数中随意取出51个数来,求证:其中一定有两个数,,它们中的一个是另一个的倍数.
分析设法制造抽屉:(1)不超过50个;(2)每个抽屉的里的数(除仅有的一个外),其中一个数是另一个数的倍数,一个自然数的想法是从数的质因数表示形式入手. 解设第一个抽屉里放进数:1,1×2,1×2,1×2,1×2,1×2,1×2; 第二个抽屉时放进数:3,3×2,3×2,3×2,3×2,3×2;
第三个抽屉里放进数:5,5×2,5×2,5×2,5×2;
第二十五个抽屉里放进数:49,49×2;
第二十六个抽屉里放进数:51.
第五十个抽屉里放进数:99.
那么随意取出51个数中,必有两个数同属一个抽屉,其中一个数是另一个数的倍数. 234234523456
制造抽屉并非总是一帆风顺的,有时要边制造边调整、改进.
例8 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数. 分析注意到这些数队以10的余数即个位数字,以0,1, ,9为标准制造10个抽屉,标以[0],[1], ,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数.
3. 较复杂的问题须反复地运用抽屉原则,将复杂问题转化为简单问题.
例9以(x,y,z)表示三元有序整数组,其中x、y、z为整数,试证:在任意七个三元整数组中,至少有两个三元数组,它们的x、y、z元中有两对都是奇数或都是偶数.
分析 设七个三元素组为A1(x1,y1,z1)、A2(x2,y2,z2)、 、A7(x7,y7,z7).现在逐步探索,从x元开始,由抽屉原则,x1,x2, ,x7这七个数中,必定有四个数具有相同的奇偶性,不妨设这四个数是x1,x2,x3,x4且为偶数,接着集中考虑A1、A2、A3、A4这四组数的y元,若比如y1,y2,y3,y4中有两个是偶数,则问题已证,否则至多有一个是偶数,比如y4是偶数,这时我们再来集中考虑A1、A2、A3的z元.在z1,z2,z3中,由抽屉原则必有两个数具有相同的奇偶性,如z1、z2,这时无论它们是奇数,还是偶数,问题都已得到证明.
下面介绍一个著名问题.
例10 任选6人,试证其中必有3人,他们互相认识或都不认识.
分析 用A、B、C、D、E、F表示这6个人,首先以A为中心考虑,他与另外五个人
B、C、D、E、F只有两种可能的关系:认识或不认识,那么由抽屉原则,他必定与其中某三人认识或不认识,现不妨设A认识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的余数相同,例如,不妨设为a,b,这时3可整除b-a,从而3可整除p.
下载文档
热门试卷
- 2016年四川省内江市中考化学试卷
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
- 山东省滨州市三校2017届第一学期阶段测试初三英语试题
- 四川省成都七中2017届高三一诊模拟考试文科综合试卷
- 2017届普通高等学校招生全国统一考试模拟试题(附答案)
- 重庆市永川中学高2017级上期12月月考语文试题
- 江西宜春三中2017届高三第一学期第二次月考文科综合试题
- 内蒙古赤峰二中2017届高三上学期第三次月考英语试题
- 2017年六年级(上)数学期末考试卷
- 2017人教版小学英语三年级上期末笔试题
- 江苏省常州西藏民族中学2016-2017学年九年级思想品德第一学期第二次阶段测试试卷
- 重庆市九龙坡区七校2016-2017学年上期八年级素质测查(二)语文学科试题卷
- 江苏省无锡市钱桥中学2016年12月八年级语文阶段性测试卷
- 江苏省无锡市钱桥中学2016-2017学年七年级英语12月阶段检测试卷
- 山东省邹城市第八中学2016-2017学年八年级12月物理第4章试题(无答案)
- 【人教版】河北省2015-2016学年度九年级上期末语文试题卷(附答案)
- 四川省简阳市阳安中学2016年12月高二月考英语试卷
- 四川省成都龙泉中学高三上学期2016年12月月考试题文科综合能力测试
- 安徽省滁州中学2016—2017学年度第一学期12月月考高三英语试卷
- 山东省武城县第二中学2016.12高一年级上学期第二次月考历史试题(必修一第四、五单元)
- 福建省四地六校联考2016-2017学年上学期第三次月考高三化学试卷
- 甘肃省武威第二十三中学2016—2017学年度八年级第一学期12月月考生物试卷
网友关注
- 2018江西公务员考试面试模拟题:环境保护与GDP的爱恨情仇
- 2016江西公务员面试模拟题:飞机“选座收费”惹争议
- 2018江西公务员考试申论每周一练答案:品牌建设
- 2016江西公务员面试模拟题:保护好祖国花朵
- 2017江西公务员考试行测真题解读
- 2016江西公务员面试模拟题:如何阻止购票插队
- 2018江西公务员考试申论每周一练:大学生就业多元化
- 2018江西公务员面试中情景模拟题:巧用生活智慧
- 2016江西公务员面试模拟题:研招乌龙新闻
- 2018江西公务员考试提出对策模拟题之微商
- 2017江西公务员考试真题及答案解析
- 2018江西公务员考试申论每周一练:恢复高考40周年议高考
- 2018江西公务员考试面试模拟题:“状元”的未来
- 2016年江西公务员考试面试真题(7月2日)
- 2017江西公务员考试行测真题及答案解析
- 2017年江西公务员考试面试真题(7月2日上午)
- 2017江西公务员面试真题预测及答案解析
- 2016江西公务员面试模拟题:改变“重涨不重跌”现象 切实保障农民利益
- 2018江西公务员考试申论每周一练答案:“礼让斑马线”成城市最美风景
- 历年江西公务员考试申论真题特点及命题趋势分析
- 2016江西公务员面试模拟题:城管执法的五条建议
- 江西公务员考试历年真题下载
- 2018江西公务员考试归纳概括模拟题之城乡差距
- 2017江西公务员考试常识解题技巧
- 2018江西公务员考试行测演练厅之生活常识模拟题
- 2016江西公务员面试模拟题:全面放开二孩政策
- 2018江西公务员考试申论每周一练:品牌建设
- 2017江西公务员考试申论真题答案要点
- 2018江西公务员面试热点模拟题:电商逼死了实体店?
- 2017江西公务员考试申论:“特色小镇”成亮点
网友关注视频
- 化学九年级下册全册同步 人教版 第25集 生活中常见的盐(二)
- 冀教版英语三年级下册第二课
- 沪教版八年级下册数学练习册21.3(3)分式方程P17
- 外研版英语七年级下册module3 unit1第二课时
- 外研版英语三起5年级下册(14版)Module3 Unit1
- 冀教版小学英语五年级下册lesson2教学视频(2)
- 冀教版小学英语四年级下册Lesson2授课视频
- 沪教版八年级下册数学练习册21.3(2)分式方程P15
- 沪教版牛津小学英语(深圳用) 五年级下册 Unit 12
- 七年级英语下册 上海牛津版 Unit9
- 外研版英语七年级下册module1unit3名词性物主代词讲解
- 苏科版数学七年级下册7.2《探索平行线的性质》
- 【部编】人教版语文七年级下册《逢入京使》优质课教学视频+PPT课件+教案,安徽省
- 【获奖】科粤版初三九年级化学下册第七章7.3浓稀的表示
- 3.2 数学二年级下册第二单元 表内除法(一)整理和复习 李菲菲
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 3
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 8
- 七年级英语下册 上海牛津版 Unit5
- 外研版八年级英语下学期 Module3
- 【部编】人教版语文七年级下册《老山界》优质课教学视频+PPT课件+教案,安徽省
- 第8课 对称剪纸_第一课时(二等奖)(沪书画版二年级上册)_T3784187
- 冀教版小学数学二年级下册第二单元《租船问题》
- 沪教版牛津小学英语(深圳用) 四年级下册 Unit 7
- 二年级下册数学第三课 搭一搭⚖⚖
- 北师大版数学四年级下册第三单元第四节街心广场
- 二年级下册数学第二课
- 第19课 我喜欢的鸟_第一课时(二等奖)(人美杨永善版二年级下册)_T644386
- 冀教版小学数学二年级下册1
- 六年级英语下册上海牛津版教材讲解 U1单词
- 沪教版八年级下册数学练习册一次函数复习题B组(P11)
精品推荐
- 2016-2017学年高一语文人教版必修一+模块学业水平检测试题(含答案)
- 广西钦州市高新区2017届高三11月月考政治试卷
- 浙江省湖州市2016-2017学年高一上学期期中考试政治试卷
- 浙江省湖州市2016-2017学年高二上学期期中考试政治试卷
- 辽宁省铁岭市协作体2017届高三上学期第三次联考政治试卷
- 广西钦州市钦州港区2016-2017学年高二11月月考政治试卷
- 广西钦州市钦州港区2017届高三11月月考政治试卷
- 广西钦州市钦州港区2016-2017学年高一11月月考政治试卷
- 广西钦州市高新区2016-2017学年高二11月月考政治试卷
- 广西钦州市高新区2016-2017学年高一11月月考政治试卷
分类导航
- 互联网
- 电脑基础知识
- 计算机软件及应用
- 计算机硬件及网络
- 计算机应用/办公自动化
- .NET
- 数据结构与算法
- Java
- SEO
- C/C++资料
- linux/Unix相关
- 手机开发
- UML理论/建模
- 并行计算/云计算
- 嵌入式开发
- windows相关
- 软件工程
- 管理信息系统
- 开发文档
- 图形图像
- 网络与通信
- 网络信息安全
- 电子支付
- Labview
- matlab
- 网络资源
- Python
- Delphi/Perl
- 评测
- Flash/Flex
- CSS/Script
- 计算机原理
- PHP资料
- 数据挖掘与模式识别
- Web服务
- 数据库
- Visual Basic
- 电子商务
- 服务器
- 搜索引擎优化
- 存储
- 架构
- 行业软件
- 人工智能
- 计算机辅助设计
- 多媒体
- 软件测试
- 计算机硬件与维护
- 网站策划/UE
- 网页设计/UI
- 网吧管理