抽屉原理及其应用

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

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

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

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