APP下载

抽屉原理及其应用

2018-05-14鲍世杰

农村经济与科技 2018年24期

鲍世杰

[摘 要]抽屉原理是一个重要的组合数学原理,也是组合数学中最基本的原理,是研究如何将元素分类的一个原理。它能够用来解决各种有趣的问题,常常得出一些惊奇的结论。本文首先简要地介绍了抽屉原理的简单形式及其衍生形式,其次重点论述抽屉原理在数学领域以及生活领域方面中的运用。

[关键词]抽屉原理;简单形式;衍生形式

[中图分类号]O157 [文献标识码]A

1 抽屉原理

设t1,t2,…,tn是n(n≥2)个非负整数,如果t1+t2+…tn≥n+1,则必有正整数k(1≤k≤n),使得tk≥2.

可用通俗的语言表述成:如果不少于n+1只鸽子飞进n个笼子,则必有一个笼子,该笼子里至少有2只鸽子。

抽屉原理的定义非常简单,很容易理解,它在解决生活中或者是科研当中的数学问题时可以发挥很大的作用。使用抽屉原理首先需要考虑问题自身的特点,根据不同的问题的特点来使用抽屉原理。主要应该着重考虑一下问题是对哪一些元素进行分类,然后根据所要求解的题目做出分类标准,也就是所说的制作抽屉的一个过程。

2 抽屉原理在数学领域方面的应用

当一个问题可以使用抽屉原理来进行求解的时候,这个问题一般不需要经过非常多的计算,解决问题的关键就是依据不同问题的自身特点来构造出来一些抽屉,通过这样的方式来使用抽屉原理。

2.1 抽屉原理在几何中的形状分割方面的应用

如果所解决的问题是有关几何图形的一些位置的分布和研究它们的性质的问题,那么就可以采用抽屉原理来进行计算.在我们进行使用的时候最常用的一种做法就是把题目当中所给出来的图形形状分解成为几个部分,然后把这几个划分出来的部分各自当成同一个集合,最后根据相对应的法则把要求的元素放到集合里面。在进行图形的分割时,最简单明了的方法就是把这些几何图形等分成比较常见的图形,例如划分成为圆形、正方形。

例1  把13个点以任意方式散落在一个边长为2m的正方形当中证明:在13个点里面一定会有4个点围城一个面积小于或者等于1平方米的四边形。

证明:首先将题目中所给的大正方形平均分成面积是1平方米的小正方形。由13=3×4+1,那么根据前面的抽屉原理,一定会有4个点落在面积是1平方米的小正方形内部或者是它的边上。

在上面问题进行求解的时候,我们是把这个大的正方形分解成为了四个面积相同的正方形,然后把问题证明了出来。我们也一样可以把这个大的正方形分成其他的形状来求解。

2.2 抽屉原理在整数的性质方面的应用

如果需要解决的问题是有关整除的存在性的问题,那么就可以对模n进行同余分类,然后进行构造n个抽屉,也就是把n当做模,那么就可以把整数集分为“余0类”、“余1类”,……,“余n—1类”一共n只抽屉,然后应用抽屉原理。

例2  证明在自然数当中随便取5个整数,那么不管怎么取,总会存在三个整数的和能够被3所整除。

证明: 无论整数除以3,剩下的只能是0或1。如果选中的5个整数3除剩余的0,1,2,其余都是0,数字1和2的总和是零的余数。如果有一个余数没有出现,根据5=2×2+1,这样的话,按照抽屉原理的定义,有一个余数一定会出现3次或者是3次以上。所以根据以上的说明,例题就能够证明出来。

2.3 抽屉原理在染色问题方面的应用

染色问题通常利用颜色来进行抽屉的构造。

例3  如果在空间当中的任意位置有6个点,但是这些点里面随便3个点都不在一条直线上,把这些点两两用一条红色或者是蓝色的线连起来,试证明:一定可以找到三个点,以它们为顶点的三角形的三条边都有相同的颜色。

证明:假如这个点分别为A、B、C、D、E、F,如果存在的任意三个点都不在一条线上,那么对边选取三个点就可以组成一个三角形。随便把一个点A和其他的五个点相连接,那么就可以得到五条线段,AB、AC、AD、AE、AF,因为这里的五条线段都涂有红色或者是蓝色,也就是5=2×2+1,根据抽屉原理可以发现,这里的五条线段最少会有三条的颜色是一样的(如果把颜色表示成为抽屉,线段表示成元素),不如把AB、AC、AD都当成是红色,那么研究三角形ABC三条边的颜色,一共会有以下两种情况。

(1)这三条边里面不全部是蓝色,不管哪一条边是红色,那么这个三角形就是一个每一条边都是红色的三角形。

(2)如果在这个三角形当中没有红色的边线,那么非常的明显,这个三角形是一个每一条边都是蓝色的三角形。

从上面可以看出来无论是什么样的一种情况,一定会有三条边的颜色都一样的三角形存在。

2.4 抽屉原理在划分数组方面的应用

例4  从1到12里面随便选择7个数,那么不管怎样选取,这7 个数字里面一定会有一个相对比较大的数字是另外一个数字的整数倍。

分析:如果想要利用抽屉原理证明,那我就可以把这前面的12个数字分成6组,也就是把这12个元素分别放在6个抽屉里面,然后就可以利用前面所说的抽屉原理来进行证明了。

所以现在自然而然地就把问题转化为怎么样才(下转页)

(上接页)能够把这些数字进行有效合理的分组。经过观察我们可以看出来,不管是哪一个自然数,它都能够被一个奇数和一个2的幂次方的乘积表示出来.这样的话。我们将这种表示方法当中奇数部分相同的数分到一个组里面,当做一个抽屉。

证明:经过研究,12个数字可以划分成下面的几组:

从上面可以很明显的看出来,在上面的每一个抽屉里面都没有一样的元素,并且A1+A2+A3+…A12=1,2,3,…,12,于是,根据抽屉原理可以得到,对于前面的12个自然数不管用什么样的方式从他们里面拿出七个数,那么一定会存在两个数在上面六个抽屉当中的一个元素,所以,x,y不会存在这三个抽屉当中,所以想x,y一定是前面三个抽屉当中的一个,这样的话,x和y这两个数当中较大的数一定是较小的数字的整数倍。

2.5 抽屉原理在等分区间方面的应用

把这种方法往简单了说就是指:在一个长度是一的线段里面存在有N个点,如果我们把这个线段平均分配成为N个比较小的区间,那么这样的话根据前面所说的抽屉原理,不管怎么划分,一定会有两个点被划分在一个比较小的区间里面,这样的话这两个点之间的距离就会小于或者等于。在我们进行不等式的证明的时候经常会用到这样的划分方法。

例5  已知11个数x1,x2,…,x11,全满足0≤xi≤1,i=1,2…,11,证明必有两个xi,xj(i≠j)满足.

证明: 如图1,将实数轴上介于0与1那段(连同端点)等分为10小段(这10个小段也就是10个等分区间,即10个抽屉),每一小段长为。由抽屉原理,11个点(数)中至少有个点落在同一条小线段上,这两点相应的数之差的绝对值≤

例6任给7个实数,证明必存在两个实数a,b满足0≤(a-b)<1+ab。

证明: 设七个实数为a1,a2,a3,…,a7,作Qi=(i=1,2,…7),显然,把等分成六个区间:,由抽屉原理,Q1,Q2,…Q7必有两个属于同一区间,不妨设为Qi,Qj,而不论Qi,Qj属于哪个小区间都有,由正切函数的单调性可知,,不妨记a=tgQi,b=tgQj,则,而由(*)知,又因为有 a-b>0(Qi>Qj),1+ab>0, 从而有0≤(a-b)<1+ab.

如果遇到给定了取值范围要求证明不等式的问题,我们可以利用把取值范围拆开的方法来进行抽屉的构建,就像上面所举得例子一樣,我们在等分区间上面很方面地建立了一个抽屉,然后利用抽屉原理这种方式比较简单地证明出了不等式。和其他的不等式的证明方法例如创建一个函数的办法相比较,利用抽屉原理求解更加简单快捷方便。

[参考文献]

[1] 潘可为.抽屉原理及其应用[J].湖州师范学院学报,1993(05).

[2] 王连祥.联立丢番图逼近[J].中国科学A辑,1990(01).

[3] 蒋星耀.从鸽笼原理到拉姆齐定理[J].自然杂志,1991(12).