Beihang College of Software 北航软件学院

A0,A1,A2,...,An,An?1的个数大于秩，从而，由抽屉原理知在A0,A1,A2,...,An,An?1中，存在k,l满足

1?k?l?n使

秩（Ak）=秩（Al）

但秩（Ak）?秩（Ak?1）???秩（Al）

所以秩（Ak）=秩（Ak?1），得证

4.1.2解决数论问题

在初等数论中，很多问题都可以看作存在性问题，所以可以考虑利用抽屉原理进行解决。

例3：令m 和n 为两个互素的正整数，并令a 和b 为整数，且

0?a?m?1 以及0?b?n?1，则存在一个正整数x，使得x 除以m 的余数．．

是a，并且x 除以n的余数为b，即x可以写成x ? pm ?a的同时又可以写成

x ? qn ? b的形式，这里p 和q 是整数。

证明：为了证明这个结论考虑n个整数a，m?a,2m?a,...,?n?1?m?a，这些整数中的每一个除以m都余a．设其中的两个除以n有相同的余数r．令这两个数为im?a和jm?a，其中0?i?j?n?1．因此，存在两整数qi和qj，使得

im?a?qin?r及jm?a?qjn?r，这两个方程相减可得(j?i)m?(qj?qi)n。

于是n是(j?i)m的一个因子．由于n和m没有除1之外的公因子，因此n是

j?i的因子．然而，0?i?j?n?1意味着0?j?i?n?1，也就是说n不可能是j?i的因子．该矛盾产生于我们的假设：n个整数

a，m?a,2m?a,...,?n?1?m?a

中的两个除以n有相同的余数．因此这n个数中的每一个数除以n都有不同的余

1...，，n?1中的每一个作为余数都要出现，特别地，数．根据抽屉原理，n个数0，10

Beihang College of Software 北航软件学院

数b也是如此．令p为整数，满足0?p?n?1，且使数x?pm?a，除以n余数为b．则对于某个适当的q，有x?qn?b。

因此x?pm?a且x?qn?b，从而x具有所要求的性质。

4.1.3解决几何问题

抽屉原理在几何问题中可以变形如下：如果长度为a的线段上放置若干条长度大于之和大于a的线段，则放置的线段中必有公共点。

例4 在边长为1的正方形内部，放置若干个圆，这些圆的周长之和等于10．证明：可以作出一条直线，至少与其中四个圆有交点。 ．．

证明：将所有的已知圆投影到正方形的一条边AB上．注意，周长为l的圆周，其投影长为

10l?的线段．因此所有已知圆的投影长度之和等于

10，由于???3?3AB，所以由抽屉原理知，线段AB上必有一点X，至少被四条投影线段

所覆盖．即至少有四条投影线段有公共点．因此，过点X且垂直于AB的直线，至少与四个已知圆有交点。

4.2抽屉原理在生活中的应用

抽屉原理在日常生活中的应用其实也非常广泛，比如前面提到的例5，再如一组多余366个人中一定有2个人的生日相同，80个人中至少有7个人生在同一个月等等，这样的例子很多，下面介绍几个有意思的例子。

4.2.1手指纹和头发

据说世界上没有两个人的手指纹是一样的，因此警方在处理犯罪问题时很重视手指纹，希望通过手指纹来破案或检定犯人．可是在13亿中国人当中，最少有两个人头发是一样多的。

这是因为，人的头发数目是不会超过13亿这么大的数目，假定人最多有N

i根头发．现在我们编上号码A1,A2,A3,A4,...,An．其中Ai表示由根头发的那些

11

Beihang College of Software 北航软件学院

人．现在假定每个Ai都有一个人，那么还剩下“13亿减N”个人，这数目不会等于零，我们现在随便挑一个放进和他头发相同的小组就行，他就会在里面遇到和他有相同头发数目的人了。

4.2.2电脑算命

“电脑算命”看起来挺玄乎，只要你报出自己出生的年、月、日和性别．一按按键，屏幕上就会出现所谓性格、命运的句子，据说这就是你的“命”．这是科学的吗？

如果以70年算，按出生的年、月、日、性别的不同组合数应为

70?365?2?51100，我们把它作为抽屉数．我国现有人口13亿，我们把它作为

?1.3?109?1?物体．由于??1?25441，由抽屉原理，存在25441个以上的人，尽??51100?管他们的出身、经历、天资、机遇各不相同，但他们却有完全相同的“命”，这真是荒谬绝伦。

所谓“电脑算命”不过是把人为编好的算命语句像中药柜那样事先分别一一存放在各自的柜子里，谁要算命，即根据出生的年、月、日、性别的不同的组合按不同的编码机械地到电脑上的各个“柜子”里取出所谓命运的句子．其实这充其量不过是一种电脑游戏而已。

抽屉原理应用其实非常广泛，除了之前介绍的几个例子之外，抽屉原理在计算机上也有一定的应用，由于涉及一些计算机专业问题，本文不再详细介绍。

4.2.3招生录取

其实，抽屉原理不仅在数学中有用，在现实生活中也到处在起作用，如招生录取、就业安排、资源分配、职称评定等等，都不难看到抽屉原理的作用。下面简单的举几个例子：370个同学中必有至少2个人的生日是同一天；4双不同颜色的筷子中必须取出5枝筷子才能保证其中至少有一双筷子是同颜色的；13个人中必有两个人的生肖是一样的等等。

12

Beihang College of Software 北航软件学院

5.总结

抽屉原理叙述起来比较简单，因此本文将重点放在了抽屉原理的应用，尤其是构造抽屉的几种方法，这是灵活应用抽屉原理的关键．

从上面的例子中，我们可以看到应用抽屉原理时一般分为三个步骤： （1） 构成分类的对象有m个元素；

（2） 找出分类的规则，将m个元素分成n个抽屉，并证明每个抽屉中的

元素符合题意；

（3） 应用抽屉原理证明结论成立． 应用抽屉原理解题要注意以下几点：

(1)题目中给出的元素(物品)具有任意性，分类也是任意的，所以不能用元素的一种特殊布局来代替元素的任意放置．

(2)题目中给出的元素可能是实物，也可能是数、图形、符号、方式或方法等，构造抽屉，就是对这些元素有目的地进行分类、分组、分割等．

(3)用抽屉原理解决的只是存在性问题，至于存在地点、存在多少，这都无关紧要．

(4)应用抽屉原理解题的关键在于构造抽屉．因为只有把抽屉确定了，才能明确元素的放置情况，从而才能进行应有的讨论．构造抽屉主要依赖于自身的经验和技巧，充分体现了个人解题思维的灵活性。

参考文献

[1] 曹汝成著.组合数学[M].华南理工大学出版社,2003:175

[2] 陈传理，张同君.竞赛数学教程（第二版）[M].高等教育出版社,2004 [3] 许胤龙，孙淑玲著.组合数学引论[M].第二版北京:中国科技大学出版

社,2010:9

[4] 吕松涛．抽屉原理在数学解题中的应用[J].商丘职业技术学院报.2010.25 [5] 卢开澄,卢华明.组合数学(第三版)[M].北京:清华大学出版社,2002 [6] 王向东,周士藩等.高等代数常用方法[M].1989(11) [7] 陈景林.抽屉原理及其应用[J].唐山师专学报,1999(9) [8] 潘可为.抽屉原理及其应用[J].湖州师专学报,1993(5)

13