抽屉原理的构造及其应用

抽屉原理的构造及其应用

摘要：抽屉原理是组合数学中最基本的计数原理之一，是处理存在性问题的一个重要方法，本文主要介绍抽屉原理的几个构造方法以及一些应用。 关键词：抽屉原理、构造、应用。

抽屉原理 将m个物品放入n个抽屉，则至少有一个抽屉中的物品个数不少于[（m-1/n]+1个，其中m-1/n向下取整

由此可知，在利用抽屉原理解题时，首先要明确哪些是“物品”，哪些是“抽屉”，而这两者通常不会现存于题目中，尤其是抽屉，这个往往需要我们用一些巧妙的方法去构造，下面举例说明常见的抽屉构造方法。

1、 利用分割图形的方法构造抽屉

本方法主要用于解决点在几何图形中的位置分布和性质问题，通常我们把一个几何图形分割成几部分，然后把每一部分当做一个“抽屉”，每个抽屉里放入相应的元素．通常情况下，我们分割图形构造抽屉的最好方法是等分这个几何图形。

例1：从边长为2的正方形中任选5个点，则它们当中存在两个点，这两个点之间的距离至多为1.4. 证明：将此正方形分割成4个边长为1的小正方形。当有两点位于其中一个小正方形时，这两个点之间的距离不会超过小正方形对角线的长度1.4.由抽屉原理知，5个点中必至少有两个点位于一个小正方形中。

2、 利用划分数组的方法来构造抽屉

利用此方法解题的关键是要明确分组的“对象”，然后将这些对象分成适当的数组。再应用抽屉原理，问题便得以解决 。

例2：由小于100的27个不同的奇数组成的集合中，必有两个数其和为102. 证明：将小于100的奇数分为26个组（抽屉）：{3,99}、{5,97}…{49,53}

因为有27个奇数，把它看作物品，由抽屉原理可知，必有两个奇数落在同一抽屉中，这两个数之和恰好为102.

例3：任意给定7个不同的整数，求证：其中必有两数之和或差是lO的倍数． 证明：设这7个不同的整数分别为，a0…a，它们分别除以10后。得到的余数是从0到9中的数．

(1)若这7个余数中有两个数相同：设ai=10p+k，aj=10q+k(p、q为整数)，则ai-aj=10（p-q)，即ai-aj是lO的倍数，即存在两数之差是10的倍数． (2)若这7个余数中任何两个都不同．由抽屉原理知，至

少有一数被lO除余数为6、7、8、9之一．将余数为6的数与余数为4的数划为一组余数为7的数与余数为3的数划为一组，余数为8的数与余数为2的数划为一组，余数为9的数与余数为1的数划为一组。于是便有，这7个不同的余数，除0，5外，其余的必有一组数它们的和为10的倍数。

3、利用物体所处的状态构造抽屉

通常是根据各个物体所存在的状态，将它们的状态看作抽屉原理中的“抽屉”和“元素”，从而来解决问题的．

例4、设有这样的六点，任意两点间都用红色或蓝色线段连接，且任意三点均不共线，

证明：一定可以找到这样的三点，以它们为顶点的三角形三边涂有相同的颜色。 分析假设已知六点为A。Az、凡、九、氐、氏由于任三点不共线，所以任意的三点能够构成一个三角形．证明任取一点为与其余五点相连得线段：A，A2，AtA3。 A。凡，A。A，，A，A6，由于这五条线段涂有红色或蓝色，由抽屉原理知，这五条线段中至少有三条涂有同一种颜色。(设颜色表示抽屉，线段表示元素)，我们不妨假设A。A：，A。凡，A，凡三边均为红色，接下来探讨△AAA三边的颜色以便找到三边相同颜色的三角形．

(1)若△AAA．中至少有一条红色边，则△A，AA就是三边均为红色的三角形；(2)若△虬～A中无红色边，则△AAA一就是三边均为蓝色的三角形。综上所述，总可以找到这样的三点，由它们构成的三角形三变颜色相同。 注：这个例子的应用也是Ramsey定理的一个最简单的特例。

4、 应用映射的概念来构造抽屉

就是通过某种对应方法或变换手段把原问题转化为更易于求解的新问题，一旦新问题解决了，原问题也随之解决了。

例5;从不大于2n的正整数中任取n+1个数，则其中必有一个数整除另一个数。 证明: 因为任意整数总可以表示为2的幂与某一奇数之积，因此我们可以将n+1个整数写成ai=2的si次幂*ri，i=1,2,…，n+1，而取出的n+1个数的奇数都属于{1,3,5，…，2n-1}这n个正整数的集合，根据抽屉原理这n+1个数中一定有两个数i和j使得ri=rj，所以ai/aj=2的si-sj次幂，是一个整数，命题得证。

5、 利用余数相同来构造抽屉

这种构造法多用于证明整数的整除性问题。

例6：证明任意五个整数中，必有三个整数的和是3的倍数．

证明：任一整数被3除余数只可能是0，1，2．若给定的五个整数被3除所得的余数中O，l，2都出现。那么余数分别为0、l，2的三个数的和一定能被3整除，如果余数中至多只出现0，1，2中的两个，那么由抽屉原理，其中必有一个余数至少出现三次．而这余数相同的三个数的和一定能被3整除．

注：对于如何解决有关整除的存在性问题，通常情况下，我们对模n进行同余分类，继而造n个抽屉．即以n为模，可将整数集分为“余0类”、“余l类”，?，“余n-1类”共n只抽屉．然后应用抽屉原理，原问题便得以解决。 抽屉原理的应用非常广泛，本文从抽屉原理出发，介绍个常用的集中构造抽屉的方法。

参考文献：

（1）匡正.《组合数学习题精解》.哈尔滨工业大学出版社 (2) Richard A.Brualdi.《组合数学》.机械工业出版社 (3) 姜建国.《组合数学》第二版.西安电子科技大学出版社

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库抽屉原理的构造及其应用在线全文阅读。