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