容斥原理与抽屉原理.doc

我们让学习更有效400-686-5000 容斥原理与抽屉原理包含排除法： 若已知A、B、C三部分的数量（如图），其中C为重复部分，则图中的数量等于A+B-C.即：AB=A+B- AB，其中AB=C. 若已知A、B、C三部分的数量（如图）， 则图中的数量等于A+B+C-（A与B重叠部分+ B与C重叠部分+ C与A重叠部分）+A、B、C三者重叠的部分.即：ABC=A+B+C-（AB+BC+CA）+ ABC.以上概念中符号解释：“”表示并集，“AB”表示A并B，通俗的讲表示所有或属于A、或属于B的元素的数量（集合），“ABC” 通俗的讲表示所有或属于A、或属于B、或属于C的元素数量.“”表示交集，“AB”表示A交B，通俗的讲表示所有即属于A、又属于B的元素的数量（集合），“ABC”通俗的讲表示所有即属于A，又属于B，还属于C的元素数量【例1】 在一个炎热的夏日，10个小学生去冷饮店每人都买了冷饮。其中6人买了汽水，6人买了可乐，4人买了果汁，有 3人既买了汽水又买了可乐，1人既买了汽水又买了果汁，2人既买了可乐又买了果汁。问：（1）三样都买的有几人？（2）只买一样的有几人？分析：(1)直接运用公式，设三样都买的学生有X人，那么6+6+4-3-1-2+X=10，解得X=0，所以没有人三种东西都买了.(2)去冷饮店的学生中除了买一样的外，只有买两样东西的，买两样东西的有3+1+2=6人，所以买一样东西的学生有10-6=4人.典型抽屉原理一般有以下两种表现形式1：将多于n件的物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件。例：有5只鸽子飞进4个鸽笼里，那么一定有一个鸽笼至少飞进了2只鸽子。2：将多于mn件的物品任意放到n个抽屉中，那么至少有一个抽屉中的物品的件数不少于m+1。例：如果将13只鸽子放进6只鸽笼里，那么至少有一只笼子要放3只或更多的鸽子。道理很简单。如果每只鸽笼里只放2只鸽子，6只鸽笼共放12只鸽子。剩下的一只鸽子无论放入哪只鸽笼里，总有一只鸽笼放了3只鸽子。通常情况下，题目已知抽屉的数目n，和物体最多抽屉内的需要保证的最少数目m+1，求物体总数目的最小值，根据抽屉原理2，该值多于mn，所以至少应该有mn+1个.有时候，题目中抽屉数目不明，或已知条件为物体最多抽屉内的需要保证的最少数目和和物体总数目，这个时候可以通过构造取物体（或分配物体）的最不利的情况来考虑问题.解出答案后可代入题目条件中检验，以保证答案的正确性.【例2】 两个布袋各有12个大小一样的小球，且都是红、白、蓝各4个。从第一袋中拿出尽可能少的球，但至少有两种颜色一样的放入第二袋中；再从第二袋中拿出尽可能少的球放入第一袋中，使第一袋中每种颜色的球不少于3个。这时，两袋中各有多少个球？分析：第一次取完后，只需知道第一袋中有某种颜色的球不足3个即可（取了多少个球，怎样取的都可以不考虑）。第二次取后，要保证第一袋中每种颜色的球不少于3个，最不利的情况是两种颜色的球各有8个，另一种颜色的球有3个。所以，第一袋中有球88319（个），第二袋中有球432195（个）。 3 佳士学人大