浅谈抽屉原理的构造及应用

浅谈抽屉原理的构造及应用

作者：孟姗姗

来源：《科教导刊》2010年第33期

摘要抽屉原理是组合数学中研究存在性问题的一个基本原理之一,也是非常规解题方法的重要类型之一。本文着重研讨抽屉原理的几种常用的构造方法,及其应用抽屉原理解答数学问题。

中图分类号:O29文献标识码:A

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

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

例1将13个点任意的放在一个边长为2米的正方形内。求证:必存在这样的4个点,以它们为顶点的四边形的面积不超过1平方米。

分析与证明 将原正方形四等分为面积为1平方米的四个小正方形如图(1)所示。由13 = 3€?4+1,依据抽屉原理,则必存在4个点落在面积为1平方米的小正方形内(或边上),因此以这4个点为顶点的四边形的面积总不超过小正方形的面积,即以这样的4个点为顶点的四边形的面积不超过1平方米。

图(1) 图(2)

注:这里是将正方形等分为4个小的正方形来构造抽屉的,也可将此正方形等分为4个小的矩形来构造抽屉,如图(2)。

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

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

例2任意给定7个不同的整数,求证:其中必有两数之和或差是10的倍数。

龙源期刊网 http://www.qikan.com.cn

证明设这7个不同的整数分别为,t1,t2,…t7,它们分别除以10后,得到的余数是从0到9中的数。

(1)若这7个余数中有两个数相同:设ti =10p+k, tj =10q+k(p、q为整数),则ti - tj=10(p-q),即ti - tj是10的倍数,即存在两数之差是10的倍数。

(2)若这7个余数中任何两个都不同,由抽屉原理知,至少有一数被10除余数为6、7、8、9之一。

将余数为6的数与余数为4的数划为一组,余数为7的数与余数为3的数划为一组,余数为8的数与余数为2的数划为一组,余数为9的数与余数为1的数划为一组。于是便有,这7个不同的余数,除0,5外,其余的必有一组数它们做和是10的倍数。 3 利用物体所处的状态构造抽屉

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

例3设有这样的六点,任意两点间都用红色或蓝色线段连接,且任意三点均不共线,证明:一定可以找到这样的三点,以它们为顶点的三角形三边涂有相同的颜色。

分析假设已知六点为A1、A2、A3、A4、A5、A6,由于任三点不共线,所以任意的三点能够构成一个三角形。

证明任取一点为与其余五点相连得线段:A1A2,A1A3,A1A4,A1A5,A1A6,由于这五条线段涂有红色或蓝色,由抽屉原理知,这五条线段中至少有三条涂有同一种颜色。(设颜色表示抽屉,线段表示元素),我们不妨假设A1A2,A1A3,A1A4三边均为红色,接下来探讨△A2A3A4三边的颜色,以便找到三边相同颜色的三角形。

(1)若△A2A3A4中至少有一条红色边,则△A1A2A3就是三边均为红色的三角形;(2)若△A2A3A4中无红色边,则△A2A3A4就是三边均为蓝色的三角形。 综上所述,总可以找到这样的三点,由它们构成的三角形三边颜色相同。 4 利用间接转换的方法来构造抽屉

即通过间接转换的方式,把原问题转换为一类容易解决的新问题,继而通过对新问题的求解,间接的来解决原问题。

例4 从一个班中任意选定6个人,试证其中必存在这样的3个人,他们互相认识或都不认识。

龙源期刊网 http://www.qikan.com.cn

证明将这6个人分别用A,B,C,D,E,F表示,不妨先以A为中心进行分析。设两个人相互认识用红色线段连接,否则用蓝色线段连接,由此我们得到一个2色6阶完全图。于是原问题可以间接转化为:“证明:一个2色6阶图中必定存在一个单色三角形,即三角形的三边颜色相同。”因为点A与其它5点的连线只能是红色或蓝色,由抽屉原理知,其中至少有3条同色,不妨设AB,AC,AD皆为红色。如果BC,BD,CD中有某1条(比如CD)是红色的,则的三边都是红色;如果BC,BD,CD都是蓝色,则的三边都是蓝色。综上所述,一个2色6阶图中必定存在一个单色三角形,由此新问题得以解决,随之原问题也得以解决。 注: 3和4的方法都可以用于解决以上类型的问题。 5 按同余类制造抽屉

例5 证明任意五个整数中,必有三个整数的和是3的倍数。

证明任一整数被3除余数只可能是0,1,2。若给定的五个整数被3除所得的余数中0,1,2都出现,那么余数分别为0,1,2的三个数的和一定能被3整除,如果余(下转第105页)(上接第69页)数中至多只出现0,1,2中的两个,那么由抽屉原理,其中必有一个余数至少出现三次。而这余数相同的三个数的和一定能被3整除。

注:对于如何解决有关整除的存在性问题,通常情况下,我们对模n进行同余分类,继而造n个抽屉。即以n为模,可将整数集分为“余0类”、“余1类”,…,“余n-1类”共n只抽屉。然后应用抽屉原理,原问题便得以解决。

抽屉原理的应用非常广泛,本文从抽屉原理出发,介绍了抽屉原理几种常见的构造方法,在解决同一道抽屉原理的题时,并不是只有一种构造抽屉原理的方法,只有更多的接触不同形式的问题并加以解决才能学好抽屉原理。 参考文献

[1]吴顺唐.离散数学[M].上海:华东师范大学出版社,1997. [2]刘否南.华夏文集[M].太原:高校联合出版社,1995. [3]王向东,周士藩等.高等代数常用方法[M].19.11. [4]曹汝成.组合数学[M].华东理工大学出版社,2000. [5]严士健.抽屉原则及其它的一些应用[J].数学通报,1959.

龙源期刊网 http://www.qikan.com.cn

[6]卢开澄,卢华明.组合数学(第三版)[M].北京:清华大学出版社,2002. [7]陈景林.抽屉原理及其应用[J].唐山师专学报,1999.9. [8]潘可为.抽屉原理及其应用[J].湖州师专学报,1993.5. [9]庞晓丽.用“抽屉”原理解决逻辑问题[J].保定师专学报,2001.5.

[10]兰杜云,高喜梅.浅谈抽屉原理及抽屉构造[J].河南教育学院学报(自然科学版),2003.6. [11]屈婉玲.组合数学[J].北京:北京大学出版社,19.11.