竞赛数学中的抽屉原理

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 至少有

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

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