2容斥原理和抽屉原理

1、抽屉原理. 基础知识回顾一、抽屉原理把八个苹果任意地放进七个抽屉里，不论怎样放，至少有一个抽屉放有两个或两个以上的苹果，这就是抽屉原理最简单的例子.抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。1. 若有个元素放进个集合，则必存在一个集合至少放2个元素；2. 若把个元素放进个集合，则必存在一个集合至少放有个元素；3.把个物体，按照任意方式全部放入个抽屉中，有两种情况：当能整除时，一定存在一个抽屉中至少放入了个物体；当不能整除时，一定存在一个抽屉中至少放

2、入了个物体.二、容斥原理当我们对某些对象的数目从整体上计数碰到困难时，可以考虑将整体分解为几个部分，通过对每个部分的计数来实现对整体的计数. 这一方法就是容斥原理.将整体分解为部分，也就是将集合表示成它的一组两两互异的非空真子集的并集，即，其中，,则集合叫做集合的一个覆盖. 当集合中的任意两个集合都不相交时，称为集合的一个（完全）划分.即是集合的一个覆盖，且.如为集合的划分，则(为了方便，我们用来表示集合的元素个数，即)，但是，要找到一个划分并且其中所有子集易于计数的有时并非易事. 我们可以考虑通过对任意的集族中的子集的计数来计算，当集族只是的覆盖，而不是划分时，显然有. 因为在计算时出现了对

3、某些元素的重复计数，为了计算，就得将式右边重复计算的部分减去，如果减得多了，还得再加上，也就是说我们要做“多退少补”的工作.完成上述工作的准则就是容斥原理，是十九世纪英国数学家西尔维斯提出的，容斥原理有两个公式.1. 容斥公式定理1设为有限集，则.容斥公式常用来计算至少具有某几个性质之一的元素的数目.2. 筛法公式与容斥公式讨论的计数问题相反，有时需要计算不具有某几个性质中的任何一个性质的元素的个数，即.定理2设为有限集的子集，则.II. 典型例题精讲例题：任意400人中至少有两个人的生日相同.分析：生日从1月1日排到12月31日，共有366个不相同的生日，我们把366个不同的生日看作366个

4、抽屉，400人视为400个苹果，由表现形式1可知，至少有两人在同一个抽屉里，所以这400人中有两人的生日相同.解：将一年中的366天视为366个抽屉，400个人看作400个苹果，由抽屉原理可以得知至少有两人的生日相同.例题：边长为1的正方形中，任意放入9个点，求证这9个点中任取3个点组成的三角形中，至少有一个的面积不超过.解：将边长为1的正方形等分成边长为的四个小正方形，视这四个正方形为抽屉，9个点任意放入这四个正方形中，根据抽屉原理，必有三点落入同一个正方形内.现取出这个正方形来加以讨论.把落在这个正方形中的三点记为通过这三点中的任意一点（如）作平行线，如图可知：CEGFDMISSING I

5、MAGEMISSING IMAGEMISSING IMAGEMISSING IMAGEMISSING IMAGE例题：任取5个整数，必然能够从中选出三个，使它们的和能够被3整除.证明：任意给一个整数，它被3除，余数可能为0，1，2，我们把被3除余数为0，1，2的整数各归入类.至少有一类包含所给个数中的至少两个.因此可能出现两种情况： . 某一类至少包含三个数；. 某两类各含两个数，第三类包含一个数.若是第一种情况，就在至少包含三个数的那一类中任取三数，其和一定能被3整除；若是第二种情况，在三类中各取一个数，其和也能被3整除.综上所述，原命题正确.例题：九条直线中的每一条直线都将正方形分成面积比

6、为23的梯形，证明：这九条直线中至少有三条经过同一点.证明：如图，设是一条这样的直线，作这两个梯形的中位线因为这两个梯形的高相等，所以它们的面积之比等于中位线长的比，即，从而点有确定的位置（它在正方形一对对边中点的连线上，并且）.由几何上的对称性，这种点共有四个，即图中的已知的九条适合条件的分割直线中的每一条必须经过这四点中的一点.把看成四个抽屉，九条直线当成个苹果，即可得出必定有条分割线经过同一点.例题：某校派出学生204人上山植树15301株，其中最少一人植树50株，最多一人植树100株，则至少有5人植树的株数相同.证明：按植树的多少，从50到100株可以构造51个抽屉，则个问题就转化为至

7、少有5人植树的株数在同一个抽屉里.(用反证法)假设无人或人以上植树的株数在同一个抽屉里，那只有人以下植树的株数在同一个抽屉里，而参加植树的人数为204人，所以，每个抽屉最多有4人，故植树的总株数最多有：4(5051100)1530015301得出矛盾.因此，至少有人植树的株数相同.例题6（2016北京文科高考试题）某网店统计了连续三天售出商品的种类情况：第一天售出19种商品，第二天售出13种商品，第三天售出18种商品；前两天都售出的商品有3种，后两天都售出的商品有4种，则该网店三天售出的商品至少有种.解析：设三天销售商品种类的集合分别是，由题已知.由容斥原理可得要求的最小值，只需求即的最大值.

8、而，当这个元素均在中时，最大值为.所以的最小值为.例题7设集合，是的子集，并且的元素或是的倍数，或是的倍数，或是的倍数，试问的元素最多有几个？解析：设，则注意到，由容斥原理，可得所以的元素最多有个例题8给定正整数，某个协会中恰好有个人，他们属于6个委员会，每个委员会至少由个人组成，证明：必有两个委员会，他们的公共成员数不小于.证明：设表示6个委员会的成员集合，则, 所以.如果任意，均有，那么，矛盾. 所以必存在使得.练习题：1边长为1的等边三角形内有5个点，证明：这5个点中一定有距离小于0.5的两点.2边长为1的等边三角形内，若有个点，则至少存在2点距离小于.3求证：任意四个整数中，至少有两个

9、整数的差能够被3整除.4某校高一某班有50名新生，试说明其中一定有两个人的熟人一样多.5某个年级有202人参加考试，满分为100分，且得分都为整数，总得分为10101分，则至少有3人得分相同.6. 求1，2，3，100中不能被2，3，5整除的数的个数。解答：记，由容斥原理，所以不能被2，3，5整除的数有个。7.S是集合1，2，2004的子集，S中的任意两个数的差不等于4或7，问S中最多含有多少个元素？解答：将任意连续的11个整数排成一圈如右图所示。由题目条件可知每相邻两个数至多有一个属于S，将这11个数按连续两个为一组，分成6组，其中一组只有一个数，若S含有这11个数中至少6个，则必有两个数在

10、同一组，与已知矛盾，所以S至多含有其中5个数。又因为2004=18211+2，所以S一共至多含有1825+2=912个元素，另一方面，当时，恰有，且S满足题目条件，所以最少含有912个元素。8. 求所有自然数，使得存在实数满足：解答：当时，；当时，；当时，。接下来证当时，不存在满足条件。令，则所以必存在某两个下标，使得，所以或，即，所以或，。（）若，考虑，有或，即，设，则，导致矛盾，故只有考虑，有或，即，设，则，推出矛盾，设，则，又推出矛盾， 所以故当时，不存在满足条件的实数。（）若，考虑，有或，即，这时，推出矛盾，故。考虑，有或，即=3，于是，矛盾。因此，所以，这又矛盾，所以只有，所以。故当

11、时，不存在满足条件的实数。9. 设A=1，2，3，4，5，6，B=7，8，9，n，在A中取三个数，B中取两个数组成五个元素的集合，求的最小值。解答：设B中每个数在所有中最多重复出现次，则必有。若不然，数出现次（），则在出现的所有中，至少有一个A中的数出现3次，不妨设它是1，就有集合1，其中，为满足题意的集合。必各不相同，但只能是2，3，4，5，6这5个数，这不可能，所以20个中，B中的数有40个，因此至少是10个不同的，所以。当时，如下20个集合满足要求：1，2，3，7，8， 1，2，4，12，14， 1，2，5，15，16， 1，2，6，9，10，1，3，4，10，11， 1，3，5，13，14， 1，3，6，12，15， 1，4，5，7，9，1，4，6，13，16， 1，5，6，8，11， 2，3，4，13，15， 2，3，5，9，11，2，3，6，14，16， 2，4，5，8，10， 2，4，6，7，11， 2，5，6，12，13，3，4，5，