


全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
我们让学习更有效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 佳士学人大
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
评论
0/150
提交评论