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

《竞赛数学中的抽屉原理.ppt》由会员分享，可在线阅读，更多相关《竞赛数学中的抽屉原理.ppt（15页珍藏版）》请在三一办公上搜索。

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

2、安排的存在性，而对于找出这种安排却毫无帮助。,把（mn1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m1）个物体.,基本构造,利用抽屉原理解题过程中首先要注意指明什么是物体,什么是抽屉,元素进入抽屉的规则是什么,以及在同一个盒子中,所有元素具有的性质。构造抽屉是用抽屉原理解题的关键。有的题目运用一次抽屉原理就能解决,有的则需反复用多次;有些问题明显能用抽屉原理解决,但对于较复杂的问题则需经过一番剖析转化才能用抽屉原理解决。下面用具体的例题来介绍利用抽屉原理解题的方法。,例题：,1利用几何元素构造抽屉例：在边长为1的正方形内任取5个点，则其中至少有两个点，它们之间的距离不超过,练习：在 边

3、长 为2 米的 正 方形 内任 意 放 入1 3 个 点。求 证:必有4 个点以 它 们 为 顶 点的 四 边形 的 面 积 不 超 过1 平方 米。,练习：,例：49 名学生回答 3 个问题,每个问题的得分是 0,1,.,7,证明:存在两个学生 A,B 对于每个问题,A 的得分不少于B 的得分。,分析：将一二题得分用数对(x,y)表示,所有得分点情况如图 2 所示,将四条折线以及一个正方形区域作为五个抽屉,49 个得分点中位于正方形 ABCD 中的点最多只有16 个,所以在折线 L 1,L 2,L 3,L 4 至少有 49-16=33 个得分点,则由抽屉原理,必有一条折线上至少有 9 个得分

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

5、。,分析：101个整数，证明存在两个存在整除关系，那应该是构造100个抽屉来解决问题，那么关键就是怎样构造抽屉。,4利用集合构造抽屉例：在 1,4,7,10,13,100 中任意选出20 个数,其中至少有不同的两组数,其和等于104,试证明之。,分析：把这些数分成如下如下 18 个不相交的集合:1,52,4,100,7,97,49,55,且把它看成是 18 个抽屉。从已知的 34 个数中选 20 个数,练习：已给一个由10个互不相等的两位十进制正整数组成的集合。求证：这个集合必有两个无公共元素的子集合，各子集合中各数之和相等。,分析：由题意，把集合作为物体，把每个没有公共数字的集合中的数字的和的所有可能作为抽屉。,练习：,5利用函数单调区间构造抽屉例：给九个不同的实数，a1,a2,a9,证明：至少存在两个实数ai,aj使得,分析：看这个结构可以联想到正切差角公式，并且正切函数的值域是R，所以可以将每个ai都表示成某个角度的正切值，从而进行分析。,小结：,利用抽屉原理解题时，最主要的步骤就是找到“物体”和“抽屉”。从上述几个例子中我们可以看到，构造抽屉的时候有很多种方法：有几何元素的方法，有将排列组合个数当成抽屉个数的情况，有利用整数性质构造抽屉法，有构造函数和利用单调区间法等。抽屉原理看似简单，但是在很多有趣的数学问题上可以带给我们非常好的解法。,谢谢观看,