欢迎来到天天文库
浏览记录
ID:8755936
大小:145.00 KB
页数:11页
时间:2018-04-06
《2012届高中数学竞赛辅导资料《抽屉原理》》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、§23抽屉原理 在数学问题中有一类与“存在性”有关的问题,例如:“13个人中至少有两个人出生在相同月份”;“某校400名学生中,一定存在两名学生,他们在同一天过生日”;“2003个人任意分成200个小组,一定存在一组,其成员数不少于11”;“把[0,1]内的全部有理数放到100个集合中,一定存在一个集合,它里面有无限多个有理数”。这类存在性问题中,“存在”的含义是“至少有一个”。在解决这类问题时,只要求指明存在,一般并不需要指出哪一个,也不需要确定通过什么方式把这个存在的东西找出来。这类问题相对来说涉及到的运算较少,依据的理论也不复杂,我们把这些理论称之为“抽屉原理”。 “抽屉原理
2、”最先是由19世纪的德国数学家迪里赫莱(Dirichlet)运用于解决数学问题的,所以又称“迪里赫莱原理”,也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果,任意分放在9个抽屉里,则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的,但应用它却可以解决许多有趣的问题,并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类数学竞赛中的重要内容,本讲就来学习它的有关知识及其应用。 (一)抽屉原理的基本形式 定理1、如果把n+1个元素分成n个集合,那么不管怎么分,都存在一个集合,其中至少有两个元素。 证明:(用反证法)若不存在至少有两个元素的集合,则每个集
3、合至多1个元素,从而n个集合至多有n个元素,此与共有n+1个元素矛盾,故命题成立。 在定理1的叙述中,可以把“元素”改为“物件”,把“集合”改成“抽屉”,抽屉原理正是由此得名。 同样,可以把“元素”改成“鸽子”,把“分成n个集合”改成“飞进n个鸽笼中”。“鸽笼原理”由此得名。例题讲解1.已知在边长为1的等边三角形内(包括边界)有任意五个点(图1)。证明:至少有两个点之间的距离不大于2.从1-100的自然数中,任意取出51个数,证明其中一定有两个数,它们中的一个是另一个的整数倍。3.从前25个自然数中任意取出7个数,证明:取出的数中一定有两个数,这两个数中大数不超过小数的1.5倍。4
4、.已给一个由10个互不相等的两位十进制正整数组成的集合。求证:这个集合必有两个无公共元素的子集合,各子集合中各数之和相等。5.在坐标平面上任取五个整点(该点的横纵坐标都取整数),证明:其中一定存在两个整点,它们的连线中点仍是整点。6.在任意给出的100个整数中,都可以找出若干个数来(可以是一个数),它们的和可被100整除。7.17名科学家中每两名科学家都和其他科学家通信,在他们通信时,只讨论三个题目,而且任意两名科学家通信时只讨论一个题目,证明:其中至少有三名科学家,他们相互通信时讨论的是同一个题目。课后练习1.幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不
5、管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.2.正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.3.把1到10的自然数摆成一个圆圈,证明一定存在在个相邻的数,它们的和数大于17.4.有红袜2双,白袜3双,黑袜4双,黄袜5双,蓝袜6双(每双袜子包装在一起)若取出9双,证明其中必有黑袜或黄袜2双.5.在边长为1的正方形内,任意给定13个点,试证:其中必有4个点,以此4点为顶点的四边开面积不超过(假定四点在一直线上构成面积为零的四边形).6.在一条笔直的马路旁种树,从起点起,每隔一米种一棵树,如果把三块“爱护树木”的小牌分别挂在三
6、棵树上,那么不管怎样挂,至少有两棵挂牌的树之间的距离是偶数(以米为单位),这是为什么?课后练习答案1.解从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原则1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.原则2如果把mn+k(k≥1)个物体放进n个抽屉,则至少有一个抽屉至多放进m+1个物体.证明同原则相仿.若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.原则
7、1可看作原则2的物例(m=1)2.证明把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原则二,至少有三个面涂上相同的颜色.3.证明如图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+
此文档下载收益归作者所有