第十二讲 容斥与抽屉

第十二讲 容斥与抽屉

一、基础知识 ㈠ 容斥原理：

在计数时，必须做到既不重复，也不遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既不重复，也不遗漏，这种计数的方法称为容斥原理。

1、两个集合的容斥： A∪B = A＋B－A∩B (∩:重合的部分）

2、三个集合的容斥：A∪B∪C = A＋B＋C－ A∩B－ B∩C－ A∩C＋ A∩B∩C

㈡ 抽屉原理

原理1： 把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。

原理2： 把多于mn+1(m乘以n加一)个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。

二、补充练习

练习1：学而思的一场竞赛选拔考试，试卷一共有5道题，规定答对3道及3道以上的人能通过考试。发卷子时张老师说：“这次考试一共有5个班的100位同学参加，答对第1题到笫5题的依次有80、92、86、78、74人。在公布每位同学的成绩之前，我想问大家一个问题：这次考试最少有多少位同学能通过呢?最多有多少位同学通过呢?” 分析：⑴ 这100人共答对了80＋92＋86＋78＋74＝410（道）题。

为使通过考试的人数尽可能少，应该让答对2题的人尽量多，且答对5题的尽量多。

410－2×100＝210（道）题， 210÷（5－2）＝70（人），70＜74， 70符合要求。 这次考试最少有70位同学能通过。

⑵ 这100人共答对了80＋92＋86＋78＋74＝410（道）题。

为了使通过考试的人尽可能多，应该让答对3题题的人尽量多。410＝3×100＋110，显然，可以让每人答对3道题。因此，最多有100人通过考试。

练习2 一次数学竞赛出了10道选择题，评分标准为：基础分10分，每道题答对得3分，答错扣1分，不答不得分。问：要保证至少有4人得分相同，至少需要多少人参加竞赛? 分析：⑴ 最不利原则的运用。

这次数学竞赛的得分最低是10－1×10＝0分，最高是10＋3×10＝40分，从0分到

1

40分共有41个整数。但是39、38、35这3个分数是不可能得到的，其它的分数都可能得到，所以共有41－3＝38种不同的分值。

要保证至少有4人得分相同，根据最不利原则至少需要3×38十l＝115人。 ?

答：至少需要115人参加竞赛。

练习⒊ (2009年清华附中入学测试题)

如图，在时钟的表盘上任意做9个120°的扇形，使得每一个扇形都恰好覆盖4个数，且每两个扇形覆盖的数不全相同，求证：一定可以找到3个扇形，恰好覆盖整个表盘上的数。并举一个反例说明，做8个扇形将不能保证上述结论成立。

证明：⑴ 在表盘上共可做出12个不同的扇形，并且l～12中的每个数恰好被4个不同的扇形覆盖。

将这12个扇形分为四组，使得每一组的3个扇形恰好盖住整个表盘（如图）。 从中选择9个扇形，根据抽屉原理，必有[9÷4]＋1＝3个扇形属于同一组，属于同

一组的3个扇形可以覆盖整个表盘。

⑵ 另一方面，作8个扇形相当于从全部的12个扇形中去掉4个，则可以去掉盖住

同一个数的4个扇形，这样这个数就没有被剩下的8个扇形盖住，那么这8个扇形不能盖住整个表盘。

练习⒋ 学而思学校组织大家去看电影，电影院共有24排座椅，每排有30个座位，共有650人去看电影，至少有多少排座位上的人数是一样多? 分析： 最不利原则的运用。

⑴ 每排人数都不一样，坐的最多人数是：

7＋8＋9＋……＋29＋30＝444＜650，所以每排人数不一样是不可能的。 ⑵ 至多有两排人数一样，坐的最多人数是：

（19＋20＋21＋……＋29＋30）×2＝588＜650，所以两排人数一样是不可能的。 ⑶ 至多有三排人数一样，坐的最多人数是：

（23＋24＋25＋……＋29＋30）×3＝636＜650，所以三排人数一样是不可能的。 ⑷ 至多有四排人数一样，坐的最多人数是（25＋26＋27＋……＋29＋30）×4＝660，660＞650，所以四排人数一样是可能的。 所以，至少有4排座位上人数一样多。

三、补充练习

1、 一次数学考试满分是100分，有6位同学在这次考试中的平均分是91分，这6位同学的得分各不相同，其中有一位同学仅得了65分，那么得分排在第三名的同学至少得多少分？

⑴ 求“排在第三名的同学至少得多少分？”，也就是要让第三名得分尽可能低，而其他同学得分尽可能高。

⑵ 这6名同学的总分是91×6＝546分，而6名同学的得分各不相同，有一名同学得了65分，而第一名和第二名的得分最多是100分和99分，所以剩下的三名同学的得分之和最少是546－65－100－99＝282分。

2

现在问题转化为：有3个人的总分是282分，其中的第一名最低得多少分？（6名同学中的第三名其实就是剩下这3人的第一名）

282÷3＝94分，剩下三个人的平均分是94分，三人中的第一名至少得95分。当三人的分数分别为95分、94分、93分时符合要求。

答：原来6名同学中排在第三名的同学至少得95分。（分析推理，确定最值） 2、 俱乐部全体会员选举俱乐部主任，候选人是王燕和张翔。每个会员只能选一名候选人，不得弃权。结果王燕以高出张翔20%的票数当选。事后，张翔一算，“如果当时有4人改投我的票，我就会以1票的优势当选了。”这次选举张翔得了 票。

⑴这次选举，王燕比张翔多得了4＋4－1＝7张票，因此如果当时有4人改投张翔的票，张翔就会以1票的优势当选。

⑵王燕比张翔多得了7张票，而王燕比张翔多得的票数正好是张翔票数的20%，所以张翔得了7÷20%＝35（张）票。

答：这次选举张翔得了35票。

3、 请问从1、2、3、4、??、2008这2008个数中至多可以取出多少个数，使得取出的数中任意两数之和不能被这两数之差整除。

⑴ 首先可以取1、4、7、11、14、??、2008等670个数，其中任意两数之和不能被3整除，而任意两数之差都是3的倍数，所以这670个数任意两数之和不能被这两数之差整除。

⑵ 证明：

将1、2、3、4、??、2008这2008个数从小到大每3个数一组，共可分为670组

（2008这个数单独一组）：（1，2，3）、（4，5，6）、（7，8，9）、??、（2005，2006，2007）、（2008）。

如果从1、2、3、4、??、2008中任意取671个数，根据抽屉原理，必有2个数

出自同一组，出自同一组的两个数的差是1或2，出自同一组的两个数的和是奇数或偶数，和如果是奇数就是1的倍数，和如果是偶数就是2的倍数。所以，取671个数不符合题目要求，因此最多取670个数。（运用抽屉原理，估计并构造）

4、如图，将1、2、3、??、8分别放在正方体的八个顶点上，使得每一个面上的任意3个数的和都不大于17，这时每个面上的4个数的和最大是多少？并写出一种符合要求的方法。

⑴ 设某一个面上的4个数分别为A1、A2、A3、A4，且A1＜A2＜A3＜A4。

A2＋A3＋A4≤17 （每一个面上的任意3个数的和都不大于17） 而 5＋6＋7＝18＞17

所以A2必须比5小，A2≤4，A1≤3 。 ⑵ 因为A1≤3；A2＋A3＋A4≤17

所以A1＋A2＋A3＋A4≤3＋17＝20，即每一个面上的四个数的和都不大于20。 如上图的填法，4个数的和的最大值是20。

3

5、有四袋糖块，其中任意三袋的总和都超过60块，那么这四袋糖块的总和至少有多少块？ 分析：任意三袋的总和都超过60块，最少是61块。最多的一袋糖的块数不会少于另外三袋的平均数，最少是61÷3＝20

23块，而20不是整数，所以最多的一袋糖的块数最少是

3221块。从而四袋糖的总和至少有21＋61＝82块。

比如四袋糖的数量分别是21、21、20、20即可。

4

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第十二讲 容斥与抽屉在线全文阅读。