抽屉原理及其应用

LUOYANG NORMAL UNIVERSITY

2013届本科毕业论文

抽屉原理及其应用

院（系）名称 专 业 名 称 学 生 姓 名 学 号 指 导 教 师 完 成 时 间 数学科学学院 信息与计算科学 宋岭红 090424018 朱军明 副教授 2013.5

洛阳师范学院本科毕业论文

抽屉原理及其应用

宋岭红

数学科学学院 信息与计算科学 学号：090424018

指导老师：朱军明

摘要：本文简述了抽屉原理普遍使用的简单形式和各种推广形式.我们通过对某些解得存在性的讨论，着重阐述了其在数论和代数中的应用,巧妙地解决了一些复杂的问题.从而有效地展示了抽屉原理实用性和灵活性.

关键词：抽屉原理；存在性；构造抽屉；应用

1 引言：

鸽巣原理又名抽屉原理或狄利克雷原理, 它由德国数学家狄利克雷(Divichlet，1805—1855)首先发现. 在组合数学中占据着非常重要的地位, 并且在数论和密码学中也有着广泛的应用. 使用鸽巣原理解题的关键是巧妙构造鸽巣, 即如何找出合乎问题条件的分类原则.

(参见[1])那么什么是鸽巢原理？先从一个小例子来看，“桌上有3个小球，要把这3个小球放到两个柜子里”，

无论哪一种放法, 都可以说“必有一个柜子放了两个或两个以上的小球”. 这个结论是在“任意放法”的情况下, 得出的一个“必然结果”.

2

洛阳师范学院本科毕业论文

以此来推，如果有4个苹果放入3个盒子里，一定有一个盒子至少有两个苹果；

如果有5封信，投入4个信箱，一定有一个信箱至少有两封信； 如果有10只鸽子，飞入9个笼子，则一定有一个笼子至少有两只鸽子. 我们把小球，苹果，信件，鸽子看做物体，把柜子，盒子，信箱，笼子看做抽屉，这些就是抽屉原理（鸽巢原理）的最简单的表达形式. 2 抽屉原理

2.1 抽屉原理的简单形式

对抽屉原理具体的定义，主要有下面几种形式:

原理Ⅰ 把多于n个的元素按任一确定的方式分成n个集合，则一定有一个集合中含有两个或两个以上的元素.

证明：（反证法）假设每个盒子里至多含有一个物体，则n个盒子里的物体总数小于等于n，与物体总数是n?1矛盾.

原理Ⅱ 假如，有m个元素，把它们放入n?m?n?个集合里，则必有一个抽

?m?1?屉里至少有???1个元素. n???m?1?证明（反证法）如果一个集合里面至多放?个元素，则n个集合里面??n??m?1?的元素数不超过n????m?1. n???m?1?与已知的m个元素矛盾.即必有一个集合里面至少有???1个元素. n??若把m看作是有限集合A的元素个数，n看作是集合A的n个子集，则我们又可以把上述原理表示为：设A是m?m?2?元集，Ai?A?i?1,2,...,n?且?Ai=A，

i=1n?m?1?则必有正整数k?1?k?n?，使得Ak????1. n??原理Ⅲ 把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集

3

洛阳师范学院本科毕业论文

合中仍含无穷个元素.

反证法同理可证.

原理Ⅱ、Ⅲ是对原理Ⅰ的深入阐述，把抽屉原理推入了更深的层次.且容易证明，甚至这样一些简单的原则，在初等乃至高等数学中，也都有着广泛地应用.恰当巧妙地运用这些原则，可以顺利解决一些看上去很复杂，让人无法下手的数学问题. 2.2 抽屉的构造

通过了解抽屉原理的形式，我们可以利用它的特殊形式来解决不同的问题，在利用抽屉原理解题时，需要明确哪些是“物体”，哪些是“抽屉”，这些往往都需要我们用一些巧妙的方法构造. 2.2.1整数分组构造抽屉

利用这种构造法解题, 确定分组的“对象”很关键. 确定了“对象”之后, 其个数相对于“球”的个数而言, 又往往显得太多. 只有把这些“对象”分成适当数量的组（即鸽巣）后才能应用鸽巣原理.

例1（参见[2]）一个泼妇在60天内每天至少与他人吵架一次，但60天内至多吵架90次.证明一定存在连续的若干天这个泼妇恰好与他人吵架29次.

证明 令aj是在这60天内的第1天到第j天（含第 j天）时泼妇的累计吵架次数，则a1,a2,?,a60是不同正整数的一个递增序列，其中1?aj?90.从而

a1?29,a2?29,?,a60?29 也是不同正整数的一个递增序列,其中30?aj?29?119.

显然 120 个正整数a1,a2,?,a60,a1?29,a2?29,?,a60?29全都小于或等119.也就是说120个正整数只能在119个正整数中取，则把 120 个正整数作为鸽子，1到 119个不同的数作为鸽巢，由鸽巢原理至少有两个正整数相同.因为a1,a2,?,a60各不相同，a1?29,a2?29,?,a60?29也各不相同。 所以一定存在 i和 j满足

ai?aj?29即aj?ai?29.这意味着从第j?1天到第i天泼妇恰好与他人吵架29次.

例2 任意给定7个不同的整数,求证:其中必有两数之和或差是10的倍数。 证明 设这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除余数

4

洛阳师范学院本科毕业论文

为6、7、8、9四个数中的一个.

将余数为6的数与余数为4的数划为一组,余数为7的数与余数为3的数 为一组,余数为8的数与余数为2的数划为一组,余数为9的数与余数为1的数划为一组.于是便有,这7个不同的余数,除0,5外,其余的必有一组数它们做和是10的倍数.

2.2.2 分割图形构造抽屉

在涉及到一个几何图形内有若干点时, 常常是把图形巧妙的分割成适当的部分, 用分割所得的小图形做鸽巣. 这种分割一般符合一个“分化”的定义, 即鸽巣间的元素既互不重复, 也不遗漏；但有时根据解题需要, 分割也可使鸽巣之间含有公共元素.

例3 在边长为1米的正方形内，任意放入9个点．求证：这9个点中任取3个点组成的三角形中，至少有一个的面积不超过1/8.

解 将边长为1的正方形分割成边长为1/2的4个小正方形，视这4个正方形为抽屉，9个点任意放入这4个正方形中，，由抽屉原理必有3个点落入同一个小正方形。现取出这个正方形加以讨论.

把落在这个正方形中的3点记为D,E,F如图1，通过这三点的任意一点（如E），作正方形边平行线

S△DEF?S△DEG?S△EFG

EDGF11111??h???(?h) 22222h1h ???

4841 ?.

8 ?

5

洛阳师范学院本科毕业论文

所以，结论成立.

例4 ( 参见[3])在直径为5的圆中放入9个点，求证:其中必有某两点的距离小于2.

分析：设想将圆周分成8等分，连接圆心O与各分点形成8个相等的扇形.显然每个区域都不能保证任二点的距离小于2，这种分法不行，问题在于沿半径方向最长可达2.5.所以我们必须减少沿半径的方向，另法构造抽屉.

以O为圆心，9为半径做圆，再把圆环等分为7个扇形，如图得到8个抽屉.

这时

AC?OA2?OC2?2?OA?OC?cos?6.25?0.81-2.5?0.9?0.61?7.06?1.37?5.69?2.360°7

这种分法也不行。为此，必须将圆周等分为8份.连结分点及圆心得到8个扇形，然后再以为圆心，0.9为半径做圆，以此小圆为一抽屉，8个扇形被切下的部分为8个抽屉，如图由

AB?5?3.2?2. 故AB?2. 8 6

洛阳师范学院本科毕业论文

AC?OA2?OC2?2?OA?OC?cos45°?3.18?2.

BD?2，即每个抽屉中任两点的距离都小于2.但是，现在却出现了这样一个问题:9个点，9个抽屉，元素个数与抽屉的个数一样多，不能直接使用抽屉原理，怎么办?将圆绕O点旋转，所给9个点总在圆内，则 ① 必有某扇形区域的直边通过其中一点.不妨设为A，，相邻的两扇形记为甲乙.

若其余8个l从全少有一点在甲、乙两扇形内，则问题得证.

若其余8个点均不在甲、乙两扇形内.则它们应在其余的7个抽屉内，8个点个抽屉，问题得证.

②无论如何旋转，扇形的直边均不通过此9点，这时9点必全在小圆内，间题显然.

2.2.3 等分区间构造抽屉

如果在长度为1的区间内有多于n个的点, 可考虑把区间等分成n个子区间, 由鸽巣原理知, 一定有两点落在同一子区间, 它们之间的距离不大于1/n. 这种构造法常用于处理一些不等式的证明.

,i＝1,　2　?　,11,证例5 （参见[4]）已知11个数x1,x2,?,x11,全满足0?xi?1　明必有两个xi,xj(i?j)满足xi?xj?1. 10证明 如图1，将实数轴上介于0与1那段(连同端点)等分为10小段(这10个小段也

就是10个等分区间，即10个抽屉)，每一小段长为

1.由抽屉原理，11个点(数)10?11?中至少有??+1=2个点落在同一条小线段上，这两点相应的数之差的绝对值

?10??1. 10

7

洛阳师范学院本科毕业论文

0 1

图1

例6 求证：对于任给的正无理数?及任意大的自然数n，存在一个有理数．．

k1k，使得???．

mmnm证明 把区间（0，1）进行n等分，得n个小区间

?1??12??23??n?1?0,,,,,,...,,1?． ???????nnnnnn????????由抽屉原理知，这些区间内的n?1个数中，必有两个数落在某一个区间，从而这两个数的差的绝对值小于

1． n设pi?N(i?1,2,...,n?1)，则由?是正无理数得

0?pi???pi???1.

所以这n?1个数pi???pi??(i?1,2,...,n?1)中，必有2个数，不妨设为p1???p1??和p2???p2??，它们的差的绝对值小于

1，即 n1. n(p1?p2)??(?p1????p2??)?设p1?p2?m,?p1????p2???k，则

m??k?k11，即???.

mmnn上述例子涉及区间问题，把区间（0，1）进行n等分，得n个小区间，自然就得到了n个抽屉，而n?1个数可以作为n?1个物体，此处可以利用抽屉原理解决问题.

2.2.4按整数对模p的剩余类分类构造抽屉

涉及自然数的问题, 有时常用对模同余分类法, 构造n个鸽巣, 以n为模, 可以将全体自然数分为｛余数为0的自然数｝,｛余数为1的自然数｝,?,｛余数为n?1的自然数｝, 共n个鸽巣.

例7 设a1,a2,?,a2013是2013个任意正整数的序列，则至少存在正整数k和l，

8

洛阳师范学院本科毕业论文

1?k?l?2013，使得和ak?1?ak?2???al是2013的倍数.

证明 构造一个序列：

s1?a1,s2?a1?a2，s3?a1?a2?a3?，s2013?a1?a2???a2013， 由于每一个ai均为正整数，所以，s1?s2???s2013，有两种可能： （1）存在某一个sn是2013的倍数，则定理已得证.

（2）假设在上面的序列中没有任何一个元素是2013的倍数，用模2013的剩余类k0,k1,k2,?,k2012做成2013个抽屉。由假设，s1,s2,?,s2013均不属于k0中，从而s1,s2,?,s2013这2013个数应属于k1,k2,?,k2012这2012个抽屉，于是根据抽屉原理，有一个ki至少被放入了两个数，不妨设为sk,sl. sk?a1?a2???ak,sl?a1?a2???al，

这样2013|(sl?sk),即 2013|(ak?1?ak?2???al),也就是和ak?1?ak?2???al是2013的倍数.

2.2.5用转化的方法构造抽屉

用转化的方法构造鸽巣就是通过某种对应方法或变换手段, 把原问题转化为更易求解的新问题, 一旦新为题解决, 原问题随之得解.

例8(参见[5])设空间有六个点,任意三点不共线,四点不共面,如果把这六个点两两用直线联系起来,并把这些直线涂以红色或白色.证明不论如何涂色,必存在一个是同种颜色所围成的三角形.

证明 六个点中任取一点与其它五点相联可以得到五条联线,但所涂的颜色

只有两种.

9

洛阳师范学院本科毕业论文

5故设A={五条联线}B={红色、白色}.因为P?()?3，所以对于任意

2f:A?B有ai、aj、ak?A(i、j、k都不同)使f(ai)?f(aj)?f(ak)?B即五条联线

中,至少有三条是同色的,不妨设P1P2、P1P3、P1P4为同色(如图)若P2、P3、P4三点连线是同色那么问题得证,若P2、P3、P4三点联线不同色那么至少有一条是红色的,不妨设P2P3是红色的,那么△P1P2P3的三边涂有相同的颜色,得证. 例9在1,2,?,2n中任取n?1个不同的数, 证明至少有一个数是另一个数的倍数.

证明 任何的正整数n都可以表成n?2???的形式, 其中?是自然数（包括0）, ?为奇数.

设选出的n?1个数为a1,a2,?,an?1，把它们依次表为2?1??1,2?2??2,?,2?n?1??n?1,其中?1,?2,?,?n?1,是n?1个奇数, 它们的取值只有n种可能, 即1,3,?,2n?1. 由鸽巣原理, 必存在i和j使得?i??j. 我们考虑ai=2?i??和aj=2j??, 不妨设ai＜aj则有

?ajai?2j??j2??i?i??2?j??i. 这就证明了aj是ai的倍数.

3. 抽屉原理的一些应用 3.1 抽屉原理应用于几何图形

在上节中主要介绍了抽屉原理在整除中的应用，然而抽屉原理的应用并不仅仅局限于此。在某些与几何图形相关命题的证明中，也可以根据题目的特点构造抽屉，应用抽屉原理解题.

例10九条直线中的每一条直线都把正方形分成面积比为2：3的两个四边形．证明:这九条直线中至少有三条经过同一点． ．．． 证明 如图，设CD是一条这样的这样的直线．我们再画出这两个梯形的中位线AB，因这两个梯形有相等的高，所以他们的面积比应等于对应的中位线长的比，即等于AP:PB(或者BP:PA)因

10

洛阳师范学院本科毕业论文

3，为点P有确定的位置，它在正方形一对对边中点的连线上，并且AP:PB?2：由几何上的对称性，这种点共有4个，即图中的P,Q,R,S．已知的九条适合条件的分割直线中的每一条必须过P,Q,R,S这4点中的一点．把P,Q,R,S当成4个抽屉，9条直线当成9个物体，即可看出必有3条分割直线经过同一个点．

“对称性”是数学中常用的处理问题的一种方法．同样，在构造抽屉的过程中也可以利用“对称性”来解决问题，这种方法不易观察，需要不断的训练．正方形是个比较规则的图形，在正方形中有很多对称关系，对解题减小了一点难度.

例11（参见[6]）在直径为5的圆内任意给定10个点，证明存在两个点，它们之间的距离小于2.

证明 根据题意，我们最先考虑到把圆等分成9个扇形而构造出9个抽屉，但是虽然必有两个点在某一扇形内，但不能确定它们之间的距离小于2.于是我们考虑先用一个与已知圆同心，半径为1的不包含边界的小圆作为一个抽屉，然后再把圆环部分等分成八个部分（如图）这样就构成9个从抽屉.根据抽屉原理可知，一个抽屉（包括边界）中，若这两个点在小圆（不包含边界）中，显然它们之间的距离小于2.若这两个点在圆环部分的八个等分中的某一图形里，不妨设在图形ABCD.由于

CD?2?2R?2?2?5＜1.92＜2，

11

洛阳师范学院本科毕业论文

AC?R2?r2?2Rrcos?4?2.52?12?2?2.5?1?2＜1.93＜2. 2由此可知，这时两点之间的距离也小于2，从而命题得证. 3.2 应用鸽巣原理证明不等式

我们知道n个苹果放入n?1个鸽巣里, 必然有一个鸽巣里至少有2个苹果. 这是一个鸽巣原理的简单应用. 妙用鸽巣原理, 证明某些不等式, 能起到神奇的效果. 下面给出几个例子.

3 . 2? 证明 在?ABC中, 一定有两个角同时不小于或同时不大于, 不妨设为

3例12 （参见[7]）在?ABC中, 求证:cosA?cosB?cosC?1??1?111?A,B, 则有?cosA???cosB???0, 即cosAcosB??cosA?cosA, 所

2??2?422?以

cosA?cosB?cosC?2cosAcosB?cosC??cos?A?B??cos?A?B??cosC??cos?A?B??13?．221212

故有cosA?cosB?cosC?3. 2b2c2a2?abc? 例13 （参见[8]）若a,b,c为正数，求证：2?2?2?3?2????.

abc?bca?证明 设则有不等式

abc?x,?y,?z,则原不等式等价于，若正数x,y,z满足xyz?1, bca111???3?2(x?y?z)，即 222xyzx2y2?y2z2?z2x2?3?2?x?y?z?.①

注意到x2y2z2?1,于是一定在x2,y2,z2中有两个同时不小于1，或者不大于1, 不妨设x2和y2, 则有?x2-1??y2-1??0．

12

洛阳师范学院本科毕业论文

下面, 我们采用作差法证明不等式①. 事实上,

x2y2?y2z2?z2x2?3?2?x?y?z???y2z2?z2x2?2yz?zx???x2y2?x2?y2?1???x2?2x?1???y2?2y?1? ??yz?zx???x2?1??y2?1???x?1???y?1??0．222这说明不等式①成立, 故原不等式得证. 3.3 抽屉原理在高等代数中的应用

高等代数中一些问题抽象、复杂,解答比较困难,如一些问题巧妙地运用抽屉原理会收到很好的效果.

例14（参见[9]）设A为n阶方阵,证明:存在l?i?n，使秩(Ai)=秩(Ai?1)=秩(Ai?2)=?.

证明 因为n阶方阵的秩只能是0,1,2,3,?,n这n+1个数之一,令

E?A0,A1,A2,?,An,An?1

E的个数多于秩的个数,利用抽屉原理可知,存在k,l满足1?k?l?n使

秩(Ak)=秩(Al).

但秩(Ak)?秩(Ak?1)???秩(A')，所以，秩(Ak)=秩Ak?1.

利用此式与秩的性质得:秩(ABC)?秩(AB)+秩(BC)-秩(B),这里的A,B,C是任意三个可乘矩阵,用数学归纳法可证:

秩(Ak?m)=秩(Ak?m?1),m为非负整数,故命题的结论成立. 例15证明:有限群中的每个元素的阶均有限． ．

证明设G为n阶有限群，任取a∈G，则由抽屉原理可知a,a,a,......,a,ast中必有相等的．不妨设a?a,1?t?s?n?1于是有a23nn?1s?t?e，从而a的阶有限．

4 趣味抽屉原理

脑算命电[参见[10]]“电脑算命”看起来挺玄乎，只要你报出自己出生的年、月、日和性别，一按按键，屏幕上就会出现所谓性格、命运的句子，据说这就是你的“命”.其实这充其量不过是一种电脑游戏而已。我们用数学上的抽屉

13

洛阳师范学院本科毕业论文

原理很容易说明它的荒谬.根据一般的算命原理，假定不同年分不同天数出生的人命运都不同，那么如果以70年计算，按出生的年、月、日、性别的不同组合数应为70?365?2?51100,我们把它作为“抽屉”数.我国现有人口11亿，我们把它作为“物体”数。由于11亿约为51100的22526倍，也即存在21526个以上的人，尽管他们的出身、经历、天资、机遇各不相同，但他们却具有完全相同的“命”，这真是荒谬绝伦!所谓“电脑算命”不过是把人为编好的算命语句像中药柜那样事先分别一一存放在各自的柜子里，谁要算命，即根据出生的年、月、日、性别的不同的组合按不同的编码机械地到电脑的各个“柜子”里取出所谓命运的句子而已.这种在古代迷信的亡灵上罩上现代科学光环的勾当，是对科学的亵渎.

二桃杀三士（参见[11]） 《晏子春秋》里记载了一个“二桃杀三士”的故事：齐景公门下有 3 名武功超群的勇士，他们虽为齐国立过不少功劳，但都居功自傲，目中无人，横行霸道。齐国的宰相晏婴就想除掉他们.晏婴知道，用武力绝对制服不了 3 人，只能用计谋.于是，他请齐景公赏赐 3 名勇士两个桃子，并且吩咐说：“你们自己按各人功劳的大小去分配桃子吧！”3 名勇士都要求自己单独吃一个桃子，否则，就意味着自己的功劳不大，岂不有失勇士的面子，这是绝对不能让步的。有两个勇士先吃了桃子.这样一来有一个勇士吃不到桃子，他觉得受到羞辱便拔剑自刎.两位吃了桃子的勇士看到这样情况感到羞愧也拔剑自刎了.晏子不费吹灰之力便达到了预期的目的.有趣的是，他却运用了数学中的一个重要的原理——抽屉原理.抽屉原理是这样的：把(n?1)个物体，放进n个抽屉里去，不论怎样放法，至少有一个抽屉内的物体不少于2个.巧妙灵活地运用抽屉原理，可以很顺利地解决一些看上去相当复杂的数学问题.

14

洛阳师范学院本科毕业论文

5 总结

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

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

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

（4） 应用抽屉原理证明结论成立．

应用的关键在于构造抽屉的方法，构造抽屉主要依赖于自身的经验和技巧，充分体现了个人解题思维的灵活性． 6 参考文献

[1]兰社云,高喜梅.浅谈抽屉原理及抽屉构造[J].河南教育学院学报.2003.12 (3).

[2]储一民.鸽巢原理的妙用[J].常州信息职业技术学院基础部.2008,(33):213164. [3]牛保才. 抽屉原理几点注记[J]. 长治医学院学报,1995,(02):183-186. [4]庞国萍，抽屉原理的抽屉构造法[J].玉林师范高等专科学校学报,2000,(03):12-13+20.

[5]朱莉莉.从集合论的原理来讨论抽屉原理[J].贵州商业高等专科学校学报

,1994,(02):2.

[6]何春.鸽巢原理及其应用[J]计算机与数字工程,637002:(35):28.

[7]安振平.巧用抽屉原理妙证三角形不等式[J]数字通讯，2010，（11,12）：110-111.

[8]安振平.巧用抽屉原理证明代数不等式.陕西省咸阳师范学院基础教育课程研究中心[J],2012,(04):4-28.

[9]濮安山.高等代数中抽屉原理的应用.哈尔滨师范大学自然科学学报[J].2001(6):17.

[10]杜锦湖. 抽屉原理破译电脑算命[J]. 青年科学,2007,(03):23.

15

洛阳师范学院本科毕业论文

[11]林楚.有趣的抽屉原理[J]. 黑龙江教育(小学教学案例与研究),2009,(06):25.

16

洛阳师范学院本科毕业论文

The principle and application of the drawer

SONG Ling-hong

College of Mathematics Science No： 090424018

Tutor．ZHU Jun-ming

Abstract:We briefly describes the simple form of drawer principle and it’s generalization．By the discussion of existence of the solution，we illustrates its application in number theory and algebra，solving some complex problems．So as to effectively demonstrate the practicability and flexibility of drawer principle．

Keywords: drawer principle；existence；construct a drawer；application．

17

本文来源：https://www.bwwdw.com/article/0996.html