抽屉原理及其应用毕业论文
中文摘要
抽屉原理又叫鸽笼原理、狄里克列原理、重叠原理、鞋盒原理，是组合数学中研究存在性问题的基本原理之一,也是非常规解题方法的重要类型之一，在数论和组合论中有着广泛的应用，主要用来解决几何、整除、染色、面积、数列等问题。本文首先简单介绍了抽屉原理的几种形式，便于了解抽屉原理的定义及其性质；然后着重对抽屉原理的运用及其构造等方面进行详细讨论，主要从解析几何、初等数论、不等式证明、高等代数以及概率论等方面进行研究。
关键词：抽屉原理，“抽屉”的构造，抽屉原理的应用
目录
1 引言.......................................... . (3)
2 抽屉原理的概述.......................................... (3)
2.1抽屉原理的简单形式.......................................... (3)
2.1抽屉原理的基本形式.......................................... . (4)
2.1抽屉原理的推广............................................ . (4)
3 抽屉原理的应用.......................................... (4)
3.1抽屉原理运用于解析几何............................................ (4)
3.1.2抽屉原理运用于处理几何图形内若干点问题 (4)
3.1.2抽屉原理运用于几何体的相交问题 (9)
3.1.3抽屉原理运用于点线问题............................................ ..10
3.1.4抽屉原理运用于染色问题.......................................... ..
3.2抽屉原理在初等数论的运用.......................................... ....
3.2.1抽屉原理在整除理论中的运用..........................................
3.2.2抽屉原理在同余理论中的运用..........................................
3.3抽屉原理运用于不等式的证明............................................ ..
3.3.1运用于代数不等式............................................
........
3.3.2运用于三角不等式............................................ ........
3.3.3抽屉原理运用于数列不等式............................................
3.4抽屉原理在高等代数中的运用.......................................... ..
3.4.1抽屉原理在线性方程组的运用..........................................
3.4.2抽屉原理在矩阵中的运用............................................ ..
3.5抽屉原理在概率中的运用............................................ ......
3.5.1概率为0或1的事件............................................ ......
3.5.2小概率事件..........................................
..............
4
总结................................ ................................
5
参考文献................................ ....................... ........
1引言
抽屉原理是离散数学中的一个重要原理，在数论和组合论中有着广泛的应用，是处理存在性问题的一个重要方法。抽屉原理又叫个鸽笼原理，它由德国数学家狄利克雷（Dirichlet，1805-1859）首先发现，因此又叫作狄利克雷原理。抽屉原理是组合数学中一个最基本的原理，在组合数学的发展中起到了至关重要的作用。狄利克雷在研究数论的问题时最早很巧妙的运用抽屉原理去解决问题。后来德国数学家闵可夫斯基（Minkowski，1864-1909）也运用这一原理得到一些结果。到了20世纪初期杜尔（A Thue，1863-1922）在不知道狄利克雷和闵夫斯基的工作情况下，很机巧的利用鸽笼原理来解决不定方程的有理数解的问题，有12篇论文用到这个原理。后来西根（C.L.Siegel，1896-？）利用杜尔
的结果发现了现在称为西根引理的东西，这个引理是研究超越数时最基本的必要工具。在数学的学习研究中，我们可以把抽屉原理看作是一种重要的非常规的解题方法，应用它能解决许多涉及存在性的数学问题。
2 抽屉原理的概述
2.1抽屉原理的简单形式
设为正整数，若有+1个苹果放进个抽屉里，则至少有一个抽屉里有=2个苹果。
证：如若不然，每个抽屉里至多有一个苹果，个抽屉里至多有个苹果，少了一个苹果，与假定矛盾。所以，命题正确。
令证：相当于等式左边加减多少，等式右边也要加减多少，即左边n+1个1代表n+1个苹果，右边至多n个1代表至多n个抽屉，要使等边左边与右边相等，则右边至少要有某个1加上1变为2，所以至少有1个抽屉有2个苹果。
例1. 边长为2的正三角形内任选5个点，必有两点的距离不超过1。
证：如下图所示。用它的三条中位线可将大三角形分割成4个边长为1的小正三角形，以这4个小的正三角形作为抽屉，将选的5个点作为5只苹果，由抽屉原理可
得知，有=2个点（苹果）落在某一个小正三角形内。而小正三角形内任意两点之间的距离小于或等于其边长，所以这两点间的距离不超过1。
2.2抽屉原理的基本形式
设，，为正整数，若有个苹果分到个抽屉里，则或者第一个抽屉里至少有个苹果，或者第二个抽屉里至少有个苹果，，或者第个抽屉里有个苹果，以上情况至少其中之一必然成立。
证：否则的话，这个抽屉中的苹果总数少于
，少了一个苹果，与假设矛盾。所以，命题成立。
当时，便是抽屉原理的简单形式。
2.3抽屉原理的推广
根据抽屉原理的基本形式，可以得到抽屉原理的许多推广形式：
（1）个苹果分到个抽屉里，至少有一个抽屉里有个苹果；
（2）个苹果分到个抽屉里，每个抽屉里至少有一个苹果，则必有一个抽屉里至多有个苹果；
（3）个苹果分到个抽屉里，至少有一个抽屉里有个苹果；
（4）若,则中至少有1个数大于等于。
（5）无穷个苹果放入有限个抽屉里中，则至少有1个抽屉中有无穷个苹果。
证：均可用反证法证明。
（1）设0。如若不然，每个抽屉里最多有个苹果，个抽屉里最多有=(个苹果，与假设矛盾。
（2）设0。如若不然，每个抽屉里至少有+1个苹果，个抽屉里至少有
=(个苹果，与假设矛盾。
（3）在抽屉原理的基本形式中，令即可。
（4）如若不然，诸均小于等于，，这时
，与假设矛盾。
（5）如若不然，这有限个抽屉中的每个抽屉中均为有限个苹果，这有限个抽屉中苹果的总数也为有限个，与假设矛盾。
例2. 在边长为4的正方形内任选9个点，一定有三点构成的三角形的面积小于或等于2。
证：如下图所示，用这个正方形两条对边对应的四等分点连线将它分成4个长为4，宽为1的矩形，由抽屉原理知9个点中有=3个点落入同一个矩形中。因为矩形
的内部三角形（包括内接三角形）面积小于或等于矩形面积一半，所以以这三点为顶点的三角形的面积小于或等于。
例3. 有6个大于1的正整数，它们之间两两互素，并且最大的素因子不超过30.证明：它们之中至少有一个是素数或素数幂。
证：不超过30的素数有2,3,5,7,11,13，17,19,23,29共10个。因为6个正整数两两之间互素并且均大于1，所以它们所含的素因子彼此之间不同并且至少含有1个素因子，那么问题就变为10个素数（苹果）分配给6个正整数（抽屉）并且每个抽屉都是非空的。由抽屉原理的推广形式（2）可知，至少有一个正整数仅含一
个素因子个数小于或等于。从题目可知这个数不能为1（因为这6个正整数都大于1），所以必有一个正整数只含有一个素因子，则这个正整数为素数或素数幂。
3.抽屉原理的应用
3.1 抽屉原理运用于解析几何
解析几何是在坐标系的基础上，用代数方法研究几何问题的一门数学学科，它将抽象的数学语言与直观的图像结合起来，形成代数问题与图形之间的相互转化，从而使代数问题几何化，几何问题代数化。本小节主要讨论抽屉原理在几何图形的若干点的问题、几何形体相交问题以及点线问题的运用。
3.1.1抽屉原理用于处理几何图形内若干点的问题
①分割法构造抽屉
在涉及到一个几何图形内有若干点时，常常是把图形巧妙地分割成适当的部分，用分割所得的小图形作抽屉。这种分割一般符合一个“分划”的定义，即抽屉间的元素既互不重复，也无遗漏；但有时根据解题需要，分割也可使得抽屉之间含有公共元素。例1：如果直径为5的圆内有10个点，求证其中有某两点的距离小于2。
证：先将圆分成八个全等的扇形，再在中间作一个直径d=1.8的圆（如右上图），这就把已知的圆分成了9个区域（抽屉）。由抽屉原理，圆内的10个点（苹果）必有两点落在同一区域内，只须证明每个区域中的两点的距离都小于2。
显然，小圆内任两点间的距离小于2，又曲边扇形ABCD中，AB<2,AD=BC<2,CD<2,而任两点距离最大者AC，有
AC==<2 。
A
D
O
C B
例2：边长为1的正方形内任选5个点，必有两点之间的距离不超过。
证：如下图所示，用正方形的对边中点连线将其分割为4个边长为的小正方形，
则5个点（苹果）放入这4个小正方形（抽屉）中必有=2个点落入同一小正方
形内。因为正方形内任两点间的距离小于等于倍的边长，故知此两点间的距离
小于等于。
小结：
在利用抽屉原理解决几何图形内若干点的问题时，通常采用上述的分割图形的方
法构造抽屉。利用这种构造法解题，关键在于分割的方法和分割得到的小图形（抽
屉）个数是否恰当，而与各小图形的面积是否相同无关（如例1）。在某些问题
中，对同一个图形甚至可用不止一种的方法分割，例如在一个边长为1的正三角
形内最多能找到几个点而使这些点彼此间距离大于1/2，这个问题可用两种方法
构造抽屉：一是以正三角形的三顶点为中心，分别作半径为1/2的圆弧，把正三
角形划分为四块,如下图3（1）所示；二是把边长为1的正三角形
划分为边长为1/2的四个小正三角形，如下图3（2）所示。如此分割后，问题
的答案就出来了，即最多能找到4个点，他们彼此间的距离大于1/2；而确实能
找到满足条件的4个点，如ABC的中心和顶点A,B,C。
并且在涉及到一个几何图形内有若干点的问题时，可得到这样的一个猜想：
猜想1：
运用抽屉原理解决一个几何图形内m个点的问题，若要求或要证的是n个点的关
系，则一般需构造个抽屉。（m,n均为正整数且都大于1）。
例3：在棱长为1的正方体内任选13个点，求证必有四点构成的四棱锥的面积小于等于。
可如此来证明：因为有13个点（苹果），要求的是四个点之间的问题，则可将正方体平均分成=4部分（抽屉），由抽屉原理知必有一部分（抽屉）分到4个点（苹果）（如下图所示），则这四点构成的四棱锥的最大体积为，则题目得证。
②覆盖法构造抽屉
在利用抽屉原理解决几何图形内若干点的问题时，有时仅凭分割是难以达到目的的，需巧妙地寻找几个图形（作为抽屉），它其中的一个覆盖若干点，这就是利用覆盖的方法构造抽屉。
例4：在边长为6的正三角形内任放21个点，证明可以用一个直径为的圆形纸片盖住其中三点。
证：要证“直径为的圆能盖住三点”，这样，在构造抽屉时应当把三角形与圆结合起来。三角形与圆有联系的有三角形的外接圆。又边长为3/2的正三角形的外接圆直径恰为，故用直径为的圆可以完全盖住一个边长为3/2的正三角形。
依此推出，边长为3的正三角形可被三个直径为的圆完全覆盖，边长为6的正
三角形也可被是个直径为的圆完全覆盖（如下图所示）。
证明：把边长为6的正ABC的每边四等分，由各等分点作平行于正三角形的直
线，把ABC分割成16个边长为3/2的小正三角形，顶点朝上的小正三角形共
有10个，做他们的外接圆，这10个外接圆正好把ABC完全盖住。把这10个直
径为的圆看作抽屉。由抽屉原理，存在一个小圆，至少盖住21个点中的=3
点。
小结：
利用覆盖法构造抽屉的性质与用分割法构造抽屉的性质基本相同，只是覆盖法倾
向于用图覆盖住若干点，而分割法则是若干点落入分割的图中。覆盖法不仅可用
于解决几何图形的若干点的问题，还可解决几何形体的相交问题，此时也称覆盖
法为重叠法。
3.1.2抽屉原理用于处理几何形体相交问题
利用抽屉原理解决几何形体相交问题时，通常采用重叠法构造抽屉，它的原理如下：
定理1：
空间有一个体积是V的几何体，若把n个体积分别是的几何体一一搬到其内部去，则当时，至少有两个几何体彼此相交，称为重叠原理。
证：若任意两个几何体都不相交，则这n个几何体搬进的那个几何体的体积V 大于等于，这与矛盾，所以假设不成立，因而至少有两个几何体彼此相交。
例5：一个凸多免面体，共有9个顶点是通过平移得到的多面体（i=2,3，，9），试证：中至少有两个多面体，它们最少有一个公共内点。
证：以为位似中心，将作位似变换（相似比为2:1）得多面体，显然。
下证（i=2,3，，9）。设x 是（i=2,3，，9）中任一点，y 是将进行平移时x 所生成的像，由于，是平行四边形，所以有同一个中点z。显然，y 在内，并且由于是凸的，也在内，故
，由于是位似中心，，故x ，因此得。又关于多面体的体积有（为的体积），，由重叠原理，中至少有两个多面体彼此相交，从而最少有一个公共内点。
z
x
y
小结：
几何形体的相交问题若用一般方法来解决可能难以入手，使用抽屉原理降低了它的难度，使问题变得简单。另外，解析几何中还时常出现点线问题可用抽屉原理解决。
3.1.3抽屉原理用于处理点线问题
除了几何体中若干点问题、几何体相交问题，点线问题也经常可运用抽屉原理来求证，有时还可根据几何体中若干点问题的猜想1直接构造抽屉，即将线看成点来处理，通常构造抽屉的方法是对称构造法。
①利用对称性的方法构造抽屉
“对称性”是数学中常用来处理问题的一种方法，在抽屉原理中构造抽屉也可利用“对称性”来解决。
例6：九条直线中的每一条直线都把正方形分成面积比为2:3的两个四边形。证明：这九
条直线中至少有三条经过同一点。
证：如下图所示，设CD是一条这样的直线。画出这两个梯形的中位线AB，因为这两个梯形有相等的高，所以他们的面积比等于对应的中位线长的比，即是等于
)。因为点P有确定的位置，它在正方形一对对边中点的连线上，并且=2:3。由几何上的对称性，这种点共有4个，即是图中的P,Q,R,S。
已知的九条适合条件的分割直线中的每一条必须经过这四点中的一点，把这四点
当成四个抽屉，9条直线当成9个物体，由抽屉原理知必有三条分割线经过同一个点。
令证：将九条线看作苹果，问题求证的三条线之间的关系，由猜想1可得抽屉的个数为
个，再根据题目来求解。
小结：
抽屉原理由于其本身存在性的特殊性质，在很多领域中都经常可运用，在解析几何中的运用则主要是集中在几何图形中，经常需要画图来解决，也是通过画图来构造抽屉，从而简化题目。另外，还有一种特殊的几何问题同样可运用抽屉原理来解决，即染色问题。
3.1.4抽屉原理用于染色问题
染色问题是属于几何问题中的一种特殊形式，即题目本身没有涉及到几何方面，但在解答过程可运用画几何图的方式求证结论，并且比其他方法更为简洁。染色问题在构造抽屉时常用到的方法是映射构造法。
①利用映射的方法构造抽屉
即是通过某种对应手段或方法，把原问题转化为更易于求解的新问题，一旦新问题解决，原问题随之解决。
例7：在任何六个人中，总可以找到三个相互认识的人或三个互不认识的人。
证：把六个人作六个顶点，互相认识的两个对应的顶点连红线，否则连蓝线。本
问题等价于，在6个点的每两点之间用红线或蓝线相连，则至少存在一个同色三
角形。取任一顶点A，则A与其余5点的连线中至少有三条同色（抽屉原理），不
妨设AB,AC,AD同是红色。考虑，若BC,CD,DB三线中至少有一是红线，则含一红色三角形，否则便是蓝色三角形，命题得证。
此题也可利用概率论与集合的知识进行解答。
令证：设事件A为六个人中至少有三个互相认识的人，事件B为至少有三个互不认识的人。
设结论为事件C，则则有={六个人中至多有2人互相认识}（六个人中至多有两人互相不认识）=，假设不成立，即任何六个人中总可以找到三个互相
认识或互不认识的人。
比较：
这两类方法看起来都差不多，都能比较快的求证结论，但当数字比较大时，抽屉原理的优势就显示出来了。因为在运用抽屉原理时，有着这样的规律：一般讨论的是n个对象以及这n个对象之间的若干种关系的问题，可把这n个对象用点来表示，对象之间的关系用某种边来表示，并且有6个对象要染2种颜色，有一个3边同色的三角形；17个对象要染3种颜色，有一个三边同色的三角形；66个对象要染4种颜色，有一个同色的三角形；；
个对象要染n种颜色，有一个同色的三角形，其中=
种颜色时的对象个数。这样就当原始数字较大时，可通过不断往前推，得出结论，而利用概率论与集合的方法就复杂多了，以为要讨论的事件、集合多。如下例题所示：
例8： 17名科学家中每一名和其余科学家通信，在他们的通信中仅讨论三个题目，而任两名科学家之间仅仅讨论一个题目。证明：其中至少有3名科个心中讨论同一个题目学家，他们互相通信中讨论同一个题目。
证：仿例19，作有17个顶点，边染3色的图，与顶点A相连的边至少有6条同色（抽屉原理），考察此6线的6个端点（除A外），以其中一点B为顶点，与其余5个点互相通信中讨论同一个题目的连红线，不同题目的连蓝线，由抽屉原理知至少有三条同色，考虑此3线的3个端点，由例19知至少存在一个同色三角形，即至少有3名科学家，他们互相通信中讨论同一个题目。
除了此类染色问题之外，还有另外一种染色问题。这类问题更多的是直接要求证明图中格子等之类的涂色问题，这种情况一般要分步骤，逐渐靠近结论来解答，如下例题所示：
例9：设4国际象棋板的每一个正方形块如下图所示，随便涂上黑色或白色，证明：任何一种涂法，这块板必定包含一个矩形（它由铅垂直线和水平线所画出的小正方形构成）如图所画的一块那样，它的四角所在的四个方块都是同一种颜色的。
证：任取一行，由抽屉原理，7个方块中至少有4个方格同色。不妨设有4格白色。把4格所在的列取出，除去第一行外还有3行，可分成下列3种情况：
（1）白方格数<3，这时白方格数为0,1,2，至多只能分别两列，至少有两列全是黑方格，在此两列中任取行组成的矩形必合题意；
（2）白方格数>3，由抽屉原理，这4个或4个以上的白方格分布在三行，至少有一行有2个白格，则白格和第一行中与它同列的两个白格形成矩形符合题意；
（3）白方格=3，这时有9个黑格，由抽屉原理，9个黑格分布在4列中，至少有一列有3个黑格，即此列全黑，除去3个黑格还有6个黑格，它们分布在3列中，至少有一列有两个黑格，则此2个黑格和全是黑格的列中与它们同行的两个黑格所成的矩形符合题意。
映射法构造抽屉是运用抽屉原理中构造抽屉的一大方法，不仅在染色问题上经常运用，在初等数论的整除运用中也经常碰到。
3.2抽屉原理在初等数论中的应用
初等数论是研究数的规律，为数论的一个最古老的分支，由毕达哥拉斯首先提出。初等数论以算术方法为主要研究方法，主要内容有整数的整除理论、同余理论、连分数理论和某些特殊不定方程。本节主要讨论抽屉原理在整除理论、同余理论这两方面的运用。
3.2.1抽屉原理在整除理论中的运用
整除理论是初等数论的一个重要研究方向，包含数的整除性、带余除法、算术的基本定理、函数[x]和{x}以及素数与合数等方面的内容，而抽屉原理一般运用于求证或求解存在性命题，因而抽屉原理在整除理论中主要用于求证存在性的命题。在运用抽屉原理时，
通常使用映射的方法构造抽屉，即题目不能直接构造抽屉，需要通过某种方法或手段将题目的量进行变换得到新变量才能作为抽屉。
①映射方法构造抽屉：
例1：由1的整数中任取n+1个不同的整数，必在其中有两个是互质的。
证：设所取的n+1个整数依序为,令,则这些间的关系为1。这些
共有2n+1个，但1只要2n个整数，故至少有=2个是相等的，而这种相等关系只能发生在某个=处，所以有=+1，因为相邻两个整数必互质，故与互质。
例2 ：从不大于2n的正整数中任取n+1个数，则其中必有一个数整除另一个数。
证：采用反证法证明，假设这n+1个数没有一个数整除另一个数，即是这n+1个
数两两互质，又因为“任一整数总可表示成2的幂与某一奇数之积”，可将n+1
个正整数写成的形式，其中,2,称
为的奇因数，由整除的性质可知，这n+1个互不相同，即含有n+1个互不相同的奇数，所以有n+1而不大于2n的正整数中只有n个奇数，即有n+1，这显然是不对的，所以假设错误，即原结论成立。
另证：因为“任一整数总可表示成2的幂与某一奇数之积”，可将n+1个正整数
写成的形式，其中,2,称为的奇因数。而奇因数显然，所以所取的n+1个数的奇因数都属于{1,3,5，},这n个正奇数的集（n个抽屉）。根据抽屉原理，这n+1个数中一定有两个数的奇因数相同，记这两个数是,,0,则
整除。
小结：
上述两个例子很好地说明了抽屉原理在整除理论中运用，例5如果不采用抽屉原理进行解答，可能所要求证的结论就难以证明，例6则是采用抽屉原理与采用反证法都能较快速地证出结论，而有些存在性命题采用抽屉原理则是更难证明，例如：对任意n,证明
存在n个不同正整数，使得)整除)(i，这
道题需要采用归纳方式才能较好地证出结论，而抽屉原理难以派用上场。因此，并不是所有的存在性命题都适合用抽屉原理解决，在求证过程中要视条件和结论而定。
3.2.2抽屉原理在同余理论中的运用
同余理论同样是初等数论中的一个重要研究方向，包括完全剩余系、简化剩余系与欧拉函数、欧拉定理与费马定理以及同余方程等方面的运用，抽屉原理作为一个存在性证明的原理，主要运用于同余理论中剩余系方面的相关内容。通常是根据题意将一个数的剩余系进行构造抽屉，从而求证整除或倍数问题。在这类情况中，一般是采用整数的余数、分组这两种方法构造抽屉，从而进行证明。
①利用整数的余数构造抽屉
此类情况主要是以题目中的某数的剩余系作为抽屉来求证题目，其有以下规律：
定理1：对于大于1的正整数m，有
（1）被m除余数相同的（简称“模m同余”）m个整数之和必是m的倍数（即“模m为0”）；
（2）当m是奇数时，被m除余数彼此不同的m个整数之和必是m的倍数；
（3）被m除余数相同的两个整数之差是m的倍数；
（4）被m除余数分别为k和m-k的两个整数之和是m的倍数（其中0）。证：一个整数被m除余数若为k(0),则此整数可写为rm+k的形式，其中r为整数。反之亦对。
（1）可设这个整数为诸皆为整数，k为已知的余数)，则它们的和为是m的倍数。
（2）可设这m个整数为，则它们的和为
为
整数，此式为m的倍数。
（3）设这两个整数分别为与(r,t,k均为整数，0),故它们的差为（,是m的倍数。
（4）设这两个整数为与，其中r,t,k均为整数且0
整数的和为m（r+t+1）,为m的倍数。
例3：正整数n的倍数中必有一个含有0,1,2,3,4,5,6,7,8,9全部数字。
证：令M=123456789，这是一个9位整数。今考察以下n+1个整数
M,MM,MMM,,,其中表示k个ML连写所得的9k位整数。因为
整数被n除的余数只要n种，所以上述诸整数中必有=2个是模同余的。由
定理1（3），此两者的差（形为M,且M与0的个数皆大于1）必为n的
倍数，并含有0,1,2，全部数字。
例4：任给17个整数，证明其中必有5个数之和能被5整除。
证：把整数被5除的余数0,1,2,3,4看作5个抽屉。若每个抽屉都有数，则各取一个，由0+1+2+3+4=10能被5整除知，这5个数之和也能被5整除；若不然，17
个数至多落入4个抽屉，由抽屉原理知，至少有一个抽屉落入=5个数，这5个
数同余，其和能被5整除。
例5：在平面直角坐标系中任取13个整点，必有某三点的重心仍为整点。
证：设所取13个整点的坐标为（。首先，因为整数模3所余的数（即除以3的余数）仅有0,1,2这三种，故13个整数中至少有=5