数学奥赛辅导第七讲抽屉原则容斥原理

1、数学奥赛辅导 第七讲 抽屉原则、容斥原理知识、方法、技能i抽屉原则10个苹果放入9个抽屉中，无论怎么放，一定有一个抽屉里放了2个或更多个苹果.这个简单的事实就是抽屉原则.由德国数学家狄利克雷首先提出来的.因此，又称为狄利克雷原则.将苹果换成信、鸽子或鞋，把抽屉换成信筒、鸽笼或鞋盒，这个原则又叫做信筒原则、鸽笼原则或鞋盒原则.抽屉原则是离散数学中的一个重要原则，把它推广到一般情形就得到下面几种形式：原则一：把m个元素分成n类（m>n），不论怎么分，至少有一类中有两个元素.原则二：把m个元素分成n类（m>n）（1）当n|m时，至少有一类中含有至少个元素；（2）当n|m时，至少有一类中含

2、有至少+1个元素.其中n m表示n是m的约数，n m表示n不是m的约数，表示不超过的最大整数.原则三：把个元素分成n类，则存在一个k，使得第k类至少有个元素.原则四：把无穷多个元素分成有限类，则至少有一类包含无穷多个元素.以上这些命题用反证法极易得到证明，这里从略.一般来说，适合应用抽屉原则解决的数学问题具有如下特征：新给的元素具有任意性.如10个苹果放入9个抽屉，可以随意地一个抽屉放几个，也可以让抽屉空着. 问题的结论是存在性命题，题目中常含有“至少有”、“一定有”、“不少于”、“存在”、“必然有”等词语，其结论只要存在，不必确定，即不需要知道第几个抽屉放多少个苹果.对一个具体的可以应用抽屉

3、原则解决的数学问题还应搞清三个问题：（1）什么是“苹果”？（2）什么是“抽屉”？（3）苹果、抽屉各多少？用抽屉原则解题的本质是把所要讨论的问题利用抽屉原则缩小范围，使之在一个特定的小范围内考虑问题，从而使问题变得简单明确.用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.用抽屉原则解题的基本思想是根据问题的自身特点和本质，弄清对哪些元素进行分类，找出分类的规律.用抽屉原则解题的关键是利用题目中的条件构造出与题设相关的“抽屉”. 容斥原则当我们试图对某些对象的数目从整体上计数碰到困难时，考虑将整体分解为部分，通过对每个部分的计数来实现对整体的计数是一种明

4、智的选择.将整体分解为部分也就是将有限集x表示成它的一组两两互异的非空真子集a1，a2，an的并集，即叫做集合x的一个覆盖.一个特殊情况是，集族中的任意两个集合都不相交，这时我们称集族为集合x的一个（完全）划分.如为集合x的划分，则对集合x的计数可通过熟知的加法公式 进行，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事. 我们可以考虑通过对任意的集族中的子集的计数来计算|x|，当集族中至少存在两个集合的交非空时，我们称这个覆盖为集合x的不完全划分. 对于集合x的不完全划分，显然有有 因为在计算|ai|时出现了对某些元素的重复计数，为了计算|x|，就得将式右边重复计算的部分减去，如果

5、减得超出了，还得再加上，也就是说我们要做“多退少补”的工作.完成这项工作的准则就是容斥原理. 是十九世纪英国数学家西尔维斯提出的. 容斥原理有两个公式.1容斥公式定理1 设 证明：当由加法公式有 结论成立.若n=k时结论成立，则由 知，时结论成立.由归纳原理知，对任意自然数n，公式成立.公式称为容斥公式，显然它是公式的推广.如果将看成具有性质的元素的集合，那么就是至少具有n个性质之一的元素的集合. 因此，容斥公式常用来计算至少具有某几个性质之一的元素的数目.2筛法公式与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，即. 为此，我们先引入下面的引理.引理1

6、 设a关于全集i的补集为，则引理2 引理简单证略. 利用二引理改写公式便是定理2 设为有限集i的子集，则 赛题精讲例1设abc为一等边三角形，e是三边上点的全体. 对于每一个把e分成两个不相交子集的划分，问这两个子集中是否至少有一个子集包含着一个直角三角形的三个顶点？（第24届imo第4题）【证明】如图i321，在边bc、ca、ab上分别取三点p、q、r，使显然arq，bpr，cqp都是直角三角形. 它们的锐角是30°及60°. 设e1，e2是e的两个非空子集，且 由抽屉原则p、q、r中至少有两点属于同一子集，不妨设p、qe1. 如果bc边上除p之外还有属于e1的点，那么结

7、论已明.设bc的点除p之外全属于e2，那么只要ab上有异于b的点s属于e2，设s在bc上的投影点为，则ssb为直角三角形.再设ab内的每一点均不属于e2，即除b之外全属于e1，特别，r、ae1，于是a、q、re1，且aqr为一直角三角形. 从而命题得证.【评述】此例通过分割图形构造抽屉. 在一个几何图形内有若干已知点，我们可以根据问题的要求把图形进行适当的分割，用这些分割成的图形作为抽屉，再对已知点进行分类，集中对某一个或几个抽屉进行讨论，使问题得到解决. 例2：在1，4，7，10，13，100中任选出20个数，其中至少有不同的两组数，其和都等于104，试证明之. （第39届美国普特南数学竞赛

8、题）【证明】给定的数共有34个，其相邻两数的差均为3，我们把这些数分成如下18个不相交的集合.1，52，4，100，7，97，49，55.且把它们分作是18个抽屉，从已知的34个数中任取20个数，即把前面两个抽屉中的数1和52都取出，则剩下的18个数在后面的16个抽屉中至少有不同的两个抽屉中的数全被取出，这两个抽屉中的数互不相同，每个抽屉中的两个数的和都是104.【评述】此例是根据某两个数的和为104来构造抽屉. 一般地，与整数集有关的存在性问题也可根据不同的需要利用整数间的倍数关系、同余关系来适当分组而构成抽屉.例3 设是严格上升的自然数列：，求证：在这个数列中有无穷多个可以表示为，这里是两

9、个正整数，而是两个适当的整数. （第17届imo第2题）【证明】对严格上升的自然数列，取以为模的剩余类，则可分为类 0，1，2，.考虑无穷数列由抽屉原则，其中有无穷多项属于同一类，不妨设这一剩余类是r，且记其中数值最小的那一项为，显然，于是其中的u是某个正整数，其他的属于这一剩余类的任一项可表示为由于所以有令，这是一个正整数，再令，则上式成为显然，这里的.例4：设为实数，满足，求证：对于每一整数，存在不全为零的整数并且【证明】由柯西不等式得即.所以，当 把区间等分成个小区间，每个小区间的长度为，由于每个能取k个整数，因此个正数，由抽屉原则知必有二数会落在同一个小区间之内，设它们分别是，因此有

10、很明显，我们有现在取这里i=1,2,n，于是可表示为这里为整数，适合【评述】如上例所示，在证明存在某些有界量使相关的不等式成立时，可类似地把某区间划分为若干小区间作为抽屉，借用抽屉原则来证明.例5：一个国际社团的成员来自六个国家共有1978人，用1，2，1977，1978来编号，试证明：该社团至少有一个成员的编号或者与他的两个同胞的编号之和相等，或者是其中一个同胞的编号的两倍. （第20届imo第6题）【证明】可用反证法来证明与本题完全相当的下列问题：把整列1，2，1978按任一方式分成六组，则至少有一组具有这样的性质：其中有一个数或等于四组中其他两数之和，或等于其中某一个数的两倍.假设这六组

11、中的每一组数都不具备上述性质，也就是说每一组数都具备下列性质，记作性质（p）：同组中任何两数之差必不在此组中.因为如果有连同都在同一组中，那么由可知，这组已具备题目所要求的性质.因1978÷6>329，所以由抽屉原则可以肯定有一个组a，其中至少有380个正整数，现在从a中任意取出330个数业，记其中最大的那个数为，把分别减去其余329个数而得到329个差，它们互不相等且均小于1978. 由性质（p），它们不会再在组a中，即应属于其余五组. 又因329÷5÷>65.再由抽屉原则可以肯定有一组b，其中至少含有上述329个数中的66个数，从b中任取66个数且

12、记其中最大的那个数为b1，再把b1减去其余65个数，得出的差显然不再属于b，当然也不会属于a.假如其中的某一个数属于a，由于与b分别可以写为 其中都属于a，于是 这就同a具备性质（p）的假设相违背，这就是说上述65个数必属其余四个数组.由于65÷4>16，所以至少有一组，称为c，至少会有上述65个整数中的17个，反复进行上述推理，最后可得一数组f，其中至少会有两个数，大数与小数之差是一个小于1978的正整数，可是它不在a、b、c、d、e、f的任一组中，这显然是一个矛盾，这矛盾说明至少有一组数不具备性质（p）.即题目的结论是正确的.【评述】我们容易发现，如果把此题中1978改为任

13、何一个不小于1957的正整数后其结论仍是成立的. 上例的解答过程说明了对有些数学问题需要我们连续运用抽屉原则，而且每构造一次抽屉都把范围缩小一些.例6：已知1与90之间的19个（不同的）正整数，两两的差中是否一定有三个相等？（匈牙利数学竞赛题，1990年）【证明】设这19个数为 由于， 若右边的18个差中无三个相等，而只有两个相等，且取最小的，则 这与矛盾. 所以两两的差中定有三个相等. 抽屉原则实际上都是重叠原则，这里再介绍抽屉原则的几种变形：平均量重叠原则：把一个量s任意分成n份，则其中至少有一份不大于，也至少有一份不少于.面积的重叠原则：在平面上有n个面积分别是a1，a2，an的图形，把

14、这n个图形按任何方式一一搬到某一个面积为a的固定图形上去，（1）如果a1+a2+an>a，则至少有两个图形有公共点；（2）如果a1+a2+an<a，则固定图形中至少有一个点未被盖住.例7：在一个面积为20×25的长方形内任意放进120个面积为1×1的正方形，证明：在这个长方形内一定还可以放下一个直径为1的圆，它和这120个正方形的任何一个都不相重叠. （第1届全俄数学奥林匹克试题）【证明】要使直径为1的圆完全放在一个矩形里，它的圆心应与矩形任何一条边的距离不小于，这可从20×25的长方形abcd的每一边剪去一个宽为的长条，则余下的长方形abcd的面积为19×24=456如图i322（a）.这样，任意放进长方形abcd内的直径为1的圆心都在长方形abcd中，此外，圆心应与任何一个正方形的边界的距离也大于，即在任何一个小正方形以外加上的框如图i322（b）所得图形的面积是 . 用这样的120个图形互不相交地去覆盖长方形abcd，它们的总面积等于 但是 这说明用这样的120图形不能覆盖一个面积为456的长方形，从而可以在长方形abcd内放置一个直径为1的圆，它不与所有的小正方形中的任何一个重叠.例8：设n与k是正整数，平面上有n个