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

* * 杨月 2150502012 本次介绍的内容是竞赛数学中的组合数学类题目。其中我们着重介绍和鸽巢原理（抽屉原理）和有关的题目。 原理1：如果把n + 1 个物品放入n个盒子中，那么至少有一个盒子中有两个或更多的物品。 原理2 ：把多于mn(m乘以n)+1个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。 原理3 ：把无穷多件物体放入n个抽屉，则至少有一个抽屉里 有无穷个物体。 m,n均为正整数 注：抽屉原理只断言存在一个盒子，该 盒子中存在两个或两个以上的物品，但它并没有指出是哪个盒子，所以这个原理只能用来证明某种安排的存在性，而对于找出这种安排却毫无帮助。 把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体. 利用抽屉原理解题过程中首先要注意指明什么是物体 ,什么是抽屉,元素进入抽屉的规则是什么, 以及在同一个盒子中, 所有元素具有的性质。构造抽屉是用抽屉原理解题的关键 。有的题目运用一次抽屉原理就能解决 ,有的则需反复用多次;有些问题明显能用抽屉原理解决, 但对于较复杂 的问题则需经过一番剖析转化才能用抽屉原理解决。下面用具体的例题来介绍利用抽屉原理解题的方法。 1利用几何元素构造抽屉 例：在边长为1的正方形内任取5个点，则其中至少有两个点，它们之间的距离不超过 例：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 个得分点, 即至少有 9 个同学在第一二题的得分上满足 a i ≥ b i ,再由抽屉原理, 这 9 个同学中必有两个同学在第3题的等分相同, 即命题得证 。 2利用排列组合构造抽屉 例：910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种： 1．至少三行完全相同； 2．至少有两组（四行），每组的两行完全相同. 分析：需要证明的结论都是和整行有关的，那么我们应该把130行作为物体，构造抽屉，然后把130个物体放入抽屉中，从而解题。 3利用整数性质构造抽屉 例：从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 个数 * *