鸽巢原理和容斥原理

一、鸽巢原理

1.简单形式 ：如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。

例1：在13个人中存在至少两个人，他们的生日在同一月份里。

例2：设有n对已婚夫妇。为保证有一对夫妇被选出，至少要从这2n个人中选出多少人？（n+1）

2.加强形式 ：令q1,q2,...qn为正整数。如果将 q1+q2+...+qn+1个物体放入n个盒子内,那么或者第一个盒子至少含有q1+1个物体,或者第二个盒子 至少含有q2+1个物体,...,或者第n个盒子含有qn+1个物体.

例3：一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9 个橘子，则放入篮子中的水果的最小件数是多少？（21件）

二、容斥原理及应用

1.原理说明：正确了解容斥定理的概念：某班在短跑、投掷和跳远三项比赛中的人数分布如下。

单短跑	单投掷	单跳远	短跑+投掷	短跑+跳远	跳远+投掷	跑+跳+投	没参加的人数	参加的人数
19	21	20	10	9	6	3	4	88
U：全班的人 |U|：全班的人数92；

S：参加比赛的人 |S|：参加比赛的人数 88

A1：参加短跑的人 |A1|：参加短跑的人数19+9+3+10=41

A2：参加投掷的人 |A2|：参加投掷的人数21+6+3+10=40

A3：参加跳远的人 |A3|：参加跳远的人数20+9+6+3=38

S=A1∪A2∪A3 ∪是并在一起，而不是加！

所以|S|=|A1∪A2∪A3|=88

而不是|S|=|A1∪A2∪A3|=|A1|+|A2|+|A3|=41+40+38=119 这是错误的！

那么|S|=88怎么算呢？

|S|=|A1∪A2∪A3|=|A1|+|A2|+|A3| -（|A1∩A2|+|A1∩A3|+|A2∩A3|）+ |A1∩A2∩A3|

请大家填写|S|=|A1∪A2∪A3∪A4|=

例4：求从1到1000 不能 被5、或被6、或被8整除的整数的个数？

题解1：

|S|=|A1∪A2∪A3|=|A1|+|A2|+|A3| -（|A1∩A2|+|A1∩A3|+|A2∩A3|）+ |A1∩A2∩A3|=400

所以 |U| － |S| = 600

题解２：画大图，清晰明了。

疑问：那为什么还要学容斥定理，还要学公式呢？

因为：求从1到1000 不能 被5、或被6、或被8、或被18整除的整数的个数？请试试两种方法哪种好？哪种比较安全？ 安全第一！

练习

（2004提高和普及）75名儿童到游乐场去玩。他们可以骑旋转木马，坐滑行铁道，乘宇宙飞船。已知其中20人这三种东西都玩过，55人至少玩过其中的两种。若每样乘坐一次的费用是5元，游乐场总共收入700，可知有____名儿童没有玩过其中任何一种。