浅谈抽屉原理中抽屉的几种构造方法

摘 要：抽屉原理（鸽巢原理）是组合数学中一个重要的初等原理，在解决一某类存在性问题中具有广泛应用。考虑到应用抽屉原理证明时构造抽屉的重要性，该文在简单地介绍抽屉原理（鸽巢原理）的基础上，分别从等分区间，通过几何图形，利用余数，分组构造等几个方面对如何构造抽屉，进行了总结与概括，进而应用抽屉原理来解决某类存在性问题。

关键词：组合数学 抽屉原理 存在性问题 构造

中图分类号：O29 文献标识码：A 文章编号：1674-098X（2012）12（a）-000-02

1 抽屉原理

抽屉原理又称鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个重要的原理。是一个及其初等而有应用广泛的数学原理。

定理1.1 抽屉原理（基本形式）：将n+1个物体放入到n个抽屉中，则至少有一个抽屉中的物品数不少于两个。

以上定理不难推广为：

定理1.2 第二抽屉原理（推广形式）：把个物体放入标号为的个抽屉中，则至少有一个标号为i的抽屉中物品数不少于，。

根据以上定理结果，可得到以下结论。

推论1.1 将m个的元素按任一确定的方式分成个集合，则至少有一个集合中含有两个或两个以上的元素。

推论1.2 将个的元素按任一确定的方式分成n个集合，则至少有一个集合中元素个数不少于r个。

推论1.3 将m个的元素按任一确定的方式分成n个集合，则至少有一个集合中元素个数不少于个。其中为取整函数，下同。

推论1.4 将m个的元素按任一确定的方式分成n个集合，则至少有一个集合中元素个数不多于个。

以上结果均为有限形式的抽屉原理的有关结论，对于无限形式，有以下定理：

定理1.3 抽屉原理（无限形式）：无穷多个物体放到有限多只抽屉中，至少有一只抽屉放进了无穷多个球。

以上诸定理及其推论在大部分组合数学教材中均有论及，限于篇幅有限，证明从略。

2 抽屉的构造

抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。而在利用抽屉原理证明数学问题或者解决实际问题时，最关键是要确定哪些是“球”，哪些是“抽屉”。很多时候需要我们选取、制造“合适、恰当”的抽屉。“合适”― 要求每个抽屉的“规格”是一样的，因为是按任意方式放进元素的，每个抽屉放人元素的可能性是一样的；“恰当”― 抽屉的数目要少于元素的数目，且满足所求的结论。以下通过实例，对如何构造抽屉进行简要分析说明。

2.1 等分区间构造抽屉

所谓等分区间简单的说即是：如果在长度为1的区间内有多于n个的点，可考虑把区间n等分成n个子区间，这样由抽屉原理可知，一定有两点落在同一子区间，它们之间的距离不大于。这种构造法常用于处理一些不等式的证明。对于给定了一定的长度或区间并要证明不等式的问题，可以采用等分区间的构造方法来构造

抽屉。

例1 设x1，x2，…，xn全为实数，满足，求证：对于任意的整数，存在不全为零的整数，使得，并且：

分析：由条件以及柯西不等式显然有：

从而可以进一步把区间等分成个小区间，构造抽屉。

证明：由柯西不等式有：

所以：

因此，当时，有

把区间分成个小区间，每个区间长度为。而因为每个能取k个整数，所以一共有个整数。

根据抽屉原理，必存在某个小区间，其中至少有两个整数，设它们分别为和，则有：

其中使得为整数，且。

证毕。

从上面例题不难发现，在等分区间的基础上便很方便的构造了抽屉，从而寻找到了证明不等式的一种非常特殊而又简易的方法，与通常的不等式的证明方法（构造函数法，移位相减法）相比，等分区间构造抽屉更简易，更容易被人接受。

2.2 通过几何图形构造抽屉

很多实际问题或数学问题，通过转化均可转化为相关的几何问题。而对于其中一类存在性问题，涉及到一个几何图形内有若干点时，常常可以把图形巧妙地分割成适当的部分，然后用分割所得的小图形作抽屉。这种分割一般符合一个“分划”的定义，即抽屉间的元素既互不重复，也无遗漏；但有时根据解题需要，分割也可使得抽屉之间含有公共元素。

例2 设ABC为一等边三角形，E是三边上点的全体。对于每一个把E分成两个不相交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点？

证明：如下图，在边BC、CA、AB上分别取三点P，Q，R，使

显然，，都是直角三角形。它们的锐角是30°及60°。

设，是的两个非空子集，且

由抽屉原理可知，中至少有两点属于同一子集，不妨设。

如果边上除之外还有属于的点，那么结论已明。

设的点除之外全属于，那么只要上有异于的点属于，设在上的投影点为，则为直角三角形。

再设内的每一点均不属于，即除之外全属于，特别，，于是，且为一直角三角形。从而命题得证。

图1

上例通过分割图形构造抽屉。首先根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决。

2.3 利用余数构造抽屉

在处理一类涉及自然数的存在性问题时，可以将自然数按照模n同余进行分类，根据模n的值的不同，可以构造n个抽屉（模n剩余类）。举例来说，如果n=3，则可以将全体自然数N分为“余0类”、“余1类”、“余2类”3个抽屉。然再进一步对问题进行处理。

例3：求证对于平面上任意的不共线的9个整点，其中一定存在3个点，使得这三个点组成的三角形的重心也为整点。

分析：如果点，，满足条件，即由此三点组成的三角形的重心

此处涉及到余数问题，所以可以按模3的剩余类进行分类。

证明：设平面上的9个整点为，，令

则取值共有9种情况，即：

从而构成了9个抽屉，每个点（也就是物品）根据的值放入相应的抽屉中。

以下分两种情况讨论：（1）如果同一行或同一列的3个抽屉不空时，从每个抽屉中各选一个点，选出来的3个点即满足要求。不妨以行为例，对于某一行抽屉中的3个类型的点，每个点的的分量除以3的余数是一样的，而其的分量除以3的余数分别是0，1，2。所以不过是分量还是分量，3个余数之和都能被3整除，从而相应的3个坐标值之和能被3整除，即此3点组成的三角形的重心是整点。同理，从同一列的3个抽屉中各选一个点，选出来的3个点也满足组成的三角形的重心是整点。（2）如果从不同行，不同列的3个抽屉中各选一个点时，选出的三个点组成的三角形的重心是整点。因为这是的3点的的分量除以3的余数分别是0，1，2，y的分量除以3的余数也为0，1，2，根据上面说明，显然此三点组成的三角形的重心是整点。对于九个点，，如果某个抽屉中至少含有3个点，则此三个点组成的三角形的重心是整点。否则，每个抽屉中至多有两个点。这样此时至少某一行，或某一列，或不同行不同列的3个抽屉其中不空，那么，按照前面分析，从此3个抽屉中各选一点，则此三点组成的三角形的重心是整点。综上，对于平面上任意的不共线的9个整点，一定可以选出其中3个点，使得这三个点组成的三角形的重心也为整点。

证毕。

另外，特别地，作为按照余数分组的特例，可以按照奇数与偶数（除以2余数分别为1和0）来进行分组构造抽屉。

2.4 利用分组构造抽屉

利用这种构造法解题，确定分组的“对象”很关键。确定了“对象”之后，其个数相对于“球”的个数而言，又往往显得太多。只有把这些“对象”分成适当数量的组（即抽屉）后，才能应用抽屉原理。例4：求证：在1，4，7，10，13，…，100中任选出20个数，其中至少有不同的两对数，其和都等于104。证明：给定的数共有34个，相邻两数之差为3，可以将这些数分成18个不相交的集合：{1}，{52}，{4，100}，{7，97}，{10，94}，…，{49，55}。并且将他们分成18个抽屉，从已知的34个数中任意取出20个数，即使将前两个抽屉中的数1和52均取出，剩下的18个在其余的16个抽屉中取到，则至少有不同的两个抽屉中的书全部取出，这两个抽屉中数互不相同，每个抽屉中两个数的和都是104。即可以在1，4，7，10，13，…，100中任选出20个数，使其中至少有不同的两对数的和都等于104。

证毕。

参考文献

[1] 柯召，魏万迪.组合论[M].北京科学出版社，1981.

[2] 李宇交.组合数学[M].北京师范大学出版社，1988.

[3] 朱欢.抽屉原理在中学数学竞赛解题中的应用[J].高等函授学报（自然科学版），2010（6）.

[4] 兰社云，高喜梅.浅谈抽屉原理及抽屉构造[J].河南教育学院学报（自然科学版），2003（2）.

[5] 孙玉芹.鸽笼原理及其简单应用[J].新乡师范高等专科学校学报，2001（1）.

[6] 庞国萍.抽屉原理的抽屉构造法[J].玉林师范高等专科学校学报，2000（3）.

[7] 杨忠.抽屉原理应用若干例[J].中学生数学，2010（8）.

[8] 石立叶，于娜，刘文菡.抽屉原理及其应用[J].今日科苑，2009（17）.

[9] 蒋洪.关于鸽巢原理和Ramsey定理的几个结论[J].科教文汇（中旬刊），2008（11）.