抽屉原理及其在数学与生活中的应用

戴蒋千易

摘要：本文首先讲述了抽屉原理的概念和几种形式和推广，然后列举了其在数学及格分支中的应用以及在生活中的应用，使我们意识到，利用抽屉原理确实可以帮我们解决一些实际问题。

关键词：抽屉原理；图论

中图分类号：G633.6 文献标识码：B 文章编号：1672-1578（2017）09-0172-01

抽屉原理是德国数学家狄利克雷发现的，其形式简单易懂，却包含了深奥的道理，在应用中，对一些命题的证明时，往往起到令人惊奇的效果。它从构造法角度证明了存在性的问题。

陈景林在他的《组合数学与图论》中讲了抽屉原理的三种形式：

形式一、也是最简单的形式，就是将n+1个以上的物品放到n个抽屉中，则至少有一个抽屉里放两个以上的物品。

形式二、把多于m×n个物品放到n个抽屉中，无论怎样放，一定能找到一个抽屉，它里面至少有（m+1）个物品。

形式三、把无穷个物品放到有限个抽屉中，无论怎样放，一定能找到一个抽屉，它里面至少有无穷个物品。

在数学问题中有一类与"存在性"有关的问题，如367个人中至少有两个人是同一天过生日等这类问题在生活中非常常见，它所依据的理论 ，就是"抽屉原理"。"抽屉原理"的理论本身并不复杂，但"抽屉原理"的应用是千变万化的。

以下是抽屉原理在数学中的几个典型应用。

例1：证明任取8个自然数，必有两个数的差是7的倍数。

证明：任一个整数被7除后的余数只有可能是0到6这7个自然数中一个。把这7个自然数看成是7个抽屉，则8个整数中必有两个整数被7除后的余数落在同一个抽屉里面，即必有至少两个整数除以7的余数相等。则这两个数的差必然是7的倍数。

例2.木箱里装有红色球3个、黄色球5个、蓝色球7个，若蒙眼去摸，为保证取出的球中有两个球的颜色相同，则最少要取出多少个球？

解：把3种颜色看作3个抽屉，若要符合题意，则小球的数目必须大于3，故至少取出4个小球才能符合要求。

例3.任意5个整数中，有其中3个整数的和为3的倍数。

证：将整数分为形如3k、3k+1及3k+2这3类形式，则我们可以将这3类整数看作是3个抽屉，将这5个整数看作元素放入这3个抽屉中。

由抽屉原理可知，至少存在2个整数在同一抽屉中，即它们都是形如（3k+m）的整数，m=0，1或2。

如果有3个以上的数在同一个抽屉中，则取其中的任意三个数，它们的和是形如3（3k+m）的整数，即三者的和为3的倍数。

如果有2个整数在同一个抽屉中，则由抽屉原理知，在余下的3个数中有2个数在同一个抽屉中，余下的1个数在另一个抽屉中.在3个抽屉中各取一个数，这3个数的形式分别为3k1，3k2+1，3k3+2，则三者的和为3（k1+k2+k3）+3，即为3的倍数。

例4.三维空间中9个坐标为整数的点，试证在两两相连的线段内，至少存在一个坐标为整数的内点。

解：三维空间中，任意两坐标为整数的点，若这两点相连的线段内不存在坐标为整数的内点，则对于x，y，z这三个坐标轴，这两点至少在一个坐标上的差值正好是1.

那么，在这9个坐标为整数的点中，任意取出一点，与这个点的三个坐标中，存在的差值正好是1的共有7类，即与x轴差值正好是1，与y轴差值正好是1，与z轴差值正好是1，与x，y轴差值都是1，与x，z轴差值都是1，与y，z轴差值都是1，与x，y，z轴差值都是1。

对于剩下的8个点，若存在一点a不满足这7种情况，那么a点与这个点相连的线段内必有一个坐标为整数的内点。

若剩下的8个点都属于这7种情况之一，那么，运用鸽巢原理，则至少存在两个点属于这7种情况中的同一个情况，那么，这两点中必存在一个坐标为整数的内点。

例5.任意6個人中，要么有三个人互相认识，要么有三个人互不认识。

证：先选定一人，叫A先生，则他要么至少跟其他5人中3人以上认识，要么跟3人以上不认识。不妨设第一种情况。那么再看这三人之间，如果他们有两人认识，则与A先生3人之间互相认识，如果两两不认识，则也满足本题结论。

例6.有11名学生到老师家借书，假设老师的书房中有A、B、C、D四类书，每名学生最多可借两本不同类的书，最少借一本。试证明：必有两个学生所借的书的类型相同。

证：若学生只借一本书，则不同的类型有A、B、C、D四种，若学生借两本不同类型的书，则不同的类型有AB、AC、AD、BC、BD、CD六种。共有10种类型，把这10种类型看作10个"抽屉"，把11个学生看作11个"苹果"。如果谁借哪种类型的书，就进入哪个抽屉，由抽屉原理，至少有两个学生，他们所借的书的类型相同。

参考文献：

[1] 巧用抽屉原理 冯跃峰 中国科学技术大学出版社 2005

[2] 抽屉原理及其他 常庚哲 上海教育出版社 1986年endprint