1、单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,第一讲集合与容斥原理,主讲：罗老师,1/30,摩根定律,1、设全集为U，其子集为A、B，则有,称为摩根定律，又叫反演律。,摩根定律用文字语言能够简单叙述为：,2/30,两个集合交集补集等于它们各自补集并集；,两个集合并集补集等于它们各自补集交集。,2、摩根定律普通形式设全集为 ，其子集为,则：,3/30,称为摩根定律，又叫反演律。,摩根定律交,集补集韦恩图,
2、摩根定律并,集补集韦恩图,4/30,3、应用举例,求集合,范例解答：如图,5/30,由摩根定律,又,6/30,有限集元素数目,容斥原理,按照集合元素个数是否为有限集，集合可分为有限集和无限集，若集合A是有限集，用 表示它元素个数或用,表示,。,7/30,定理1 设A、B都是有限集，则,定理2 设A、B、C都是有限集，则,8/30,例题精讲,例1、在1，2，.，1000中，有多少个正整数既不是2倍数，又不是5倍数？,解 设,则,于是,9/30,例2 集合A元素都是正整数，其中最小是1，最大是100，除1以外，每一个元素都等于集合A中两个数（能够相同）和，求集合A元素个数最小值。,解 设,其中,则
3、若n=6,则,10/30,因为,所以,又,所以,而,所以,矛盾,若,则由上可知，,不可能。,11/30,综上可知，,又当,时，集合A满足题述性质，且,故集合A元素个数最小值为9。,例3 设,项数列,有以下性质：对于S任一非空子集B（B,元素个数记为 ），在该数列中有相邻,12/30,项恰好组成集合B，求 最小值。,解 首先，S中每个数在数列,中最少出现2次，实际上，若S中某个数在这个数列中只出现1次，因为含这个数二元子集共有3个，但在数列中含这个数相邻两项至多只有两种取法，因而不可能3个含这个数二元子集都在数列相邻两项中出现。,因为S中每个数在数列,中最少出现2次，所以，,13/30,下面，
4、我们结构一个n=8且满足题设条件例子，8项数列：3，1，2，3，4，1，2，4,就是满足条件一个数列。,总而言之，n最小值为8。,例4 设,B是A一个子,集，且B中任意三个不一样元素,都有,求 最大值。,14/30,解 设,则,设,其中,且,由题设知,其中,（不然集B中就,有三个元素,使得,且,15/30,即,所以,是E中互不相同元素，故,16/30,又当,时，B中任意两,个不一样元素,都有,从而,B满足题意。,总而言之，|B|最大值为n+1.,说明：,例2，例3，例4，我们都是先求出一个上界或下界，然后再结构一个详细例子来说明这个上界是能够到达，这是,17/30,处理这种最值问题惯用手法，在
5、实际解题时，我们往往先经过详细例子猜出这个上界，然后再设法证实。,例5 设 对X任一非空 子集M，M中最大数与最小数和称为M特征，记为 ，求X全部非空子集特,征平均数。,解 设,令,18/30,于是 是X非空子集全体（子集组成集）Y到Y本身满射，记X非空子集为 （其中 ），则特征平均数为,因为 中最大数与 中最小数和为101，中最小数与 中最大数和也为101,19/30,故 从而特征平均数为,例6 某班语文、数学、外语三门课程其中考试成绩统计结果：最少有一门课程得满分学生只有18人，语文得满分有9人，数学得满分有11人，外语得满分有8人，语文、数学都得满分有5人，数学、外语都得满分有3人，语文
6、外语都得满分有4人。问：,20/30,（1）语文、数学两门课程最少有一门得满分学生有多少人？,（2）语文、数学、外语三门课程都得满分学生有多少人？,解 设该班期中考试语文、数学、外语得满分学生集合分别为A、B、C，由题意知,21/30,（1）语文、数学两门课程最少有一门得满分学生有,（人）,（2）语文、数学、外语都得满分学生有,（人）,22/30,例7 考虑集合 全部非空子集，若一个非空子集中偶数数目不少于奇数数目，称这个子集是“好子集”，则求“好子集”数目。,解 方法一：,设一个“好子集”中有,个偶数，,则奇数数目能够有,个，所以,23/30,“好子集”数目为,方法二：,S非空子集共有 （
7、个），依据子集中偶数与奇数个数多少可分为三类：,（1）偶数多于奇数；（2）奇数多于偶数；,24/30,（3）奇数与偶数个数相等。因为S中10个元素,偶数与奇数个数相等，所以（1）、（2）子,集数相等，现考虑第三类，分别考虑含有2、4、,6、8、10个元素子集数目，则共有子集数为,所以，第一类子集数为,所以，“好子集”数目为386+251=637（个）,25/30,例8 将集合 分拆为k个互不相交非空子集 并，而且对于每一个,其中任意两个不一样元素和都不是完全平方数，求k最小值。,解 首先，考虑数6、19、30，因为,所以，这3个数必须属于3个不,同子集，于是,另首先，集合 能够分拆为3个,互不相交非空子集 并，使得它们满,26/30,足题设条件，令,因为完全平方数除以4余数只能是0或者1，所以，轻易证 满足题设条件。,总而言之，k最小值为3。,例9 将与105互质全部正整数从小到大排成数,列，求这个数列第1000项。,27/30,解 设,且,且,且,则,在1到105中，与105互质数有,28/30,设与105互质正整数按从小到大次序排列为,则,因为 所以,因为,所以,29/30,30/30,
浙ICP备2021020529号-1 | 浙B2-20240490 
