竞赛数学中的抽屉原理.ppt

《竞赛数学中的抽屉原理.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学课程与数学论杨月2150502012内容：本次介绍的内容是竞赛数学中的组合数学类题目。其中我们着重介绍和鸽巢原理（抽屉原理）和有关的题目。相关概念：第一抽屉原理原理1：如果把n+1个物品放入n个盒子中，那么至少有一个盒子中有两个或更多的物品。原理2：把多于mn(m乘以n)+1个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。原理3：把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体。m,n均为正整数相关概念：第二抽屉原理注：抽屉原理只断言存在一个盒子，该盒子中存在两个或两个以上的物品，但它并没有指

2、出是哪个盒子，所以这个原理只能用来证明某种安排的存在性，而对于找出这种安排却毫无帮助。把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体.基本构造利用抽屉原理解题过程中首先要注意指明什么是物体,什么是抽屉,元素进入抽屉的规则是什么,以及在同一个盒子中,所有元素具有的性质。构造抽屉是用抽屉原理解题的关键。有的题目运用一次抽屉原理就能解决,有的则需反复用多次;有些问题明显能用抽屉原理解决,但对于较复杂的问题则需经过一番剖析转化才能用抽屉原理解决。下面用具体的例题来介绍利用抽屉原理解题的方法。例题：1利用几

3、何元素构造抽屉例：在边长为1的正方形内任取5个点，则其中至少有两个点，它们之间的距离不超过练习：在边长为2米的正方形内任意放入13个点。求证:必有4个点以它们为顶点的四边形的面积不超过1平方米。练习：例：49名学生回答3个问题,每个问题的得分是0,1,...,7,证明:存在两个学生A,B对于每个问题,A的得分不少于B的得分。分析：将一二题得分用数对(x,y)表示,所有得分点情况如图2所示,将四条折线以及一个正方形区域作为五个抽屉,49个得分点中位于正方形ABCD中的点最多只有16个,所以在折线L1,L2,L3,L4至少有49-

4、16=33个得分点,则由抽屉原理,必有一条折线上至少有9个得分点,即至少有9个同学在第一二题的得分上满足ai≥bi,再由抽屉原理,这9个同学中必有两个同学在第3题的等分相同,即命题得证。2利用排列组合构造抽屉例：910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种：1．至少三行完全相同；2．至少有两组（四行），每组的两行完全相同.分析：需要证明的结论都是和整行有关的，那么我们应该把130行作为物体，构造抽屉，然后把130个物体放入抽屉中，从而解题。3利用整数性质构造抽

5、屉例：从1到200的所有整数中随机选出101个整数，则这101个整数中至少有一对数字，其中的一个一定能被另一个整除。分析：101个整数，证明存在两个存在整除关系，那应该是构造100个抽屉来解决问题，那么关键就是怎样构造抽屉。4利用集合构造抽屉例：在1,4,7,10,13,…,100中任意选出20个数,其中至少有不同的两组数,其和等于104,试证明之。分析：把这些数分成如下如下18个不相交的集合:{1},{52},{4,100},{7,97},…,{49,55},且把它看成是18个抽屉。从已知的34个数中选20个数练习：已给一个

6、由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。分析：由题意，把集合作为物体，把每个没有公共数字的集合中的数字的和的所有可能作为抽屉。练习：5利用函数单调区间构造抽屉例：给九个不同的实数，a1,a2,……,a9,证明：至少存在两个实数ai,aj使得分析：看这个结构可以联想到正切差角公式，并且正切函数的值域是R，所以可以将每个ai都表示成某个角度的正切值，从而进行分析。小结：利用抽屉原理解题时，最主要的步骤就是找到“物体”和“抽屉”。从上述几个例子中我们可以看到，构

7、造抽屉的时候有很多种方法：有几何元素的方法，有将排列组合个数当成抽屉个数的情况，有利用整数性质构造抽屉法，有构造函数和利用单调区间法等。抽屉原理看似简单，但是在很多有趣的数学问题上可以带给我们非常好的解法。谢谢观看