1、内容综述内容综述：本讲先介绍了以下一些重要的概念：集合、子集、两集合相等、真子集、并集、交集、相对补集，然后介绍了著名的容斥原理，接着介绍了以下几个定律：零律、分配律、排中律、吸收律、补交转换律、德摩根律。然后通过 6 道例题分析了一部分集合题目的解题方法与技巧，同学们应在熟悉以上定义、定理、定律的基础上仔细分析例题材解法，争取可以独立解决训练题。要点讲解要点讲解：1 1基本理论基本理论除了课内知识外，我们补充以下知识相对补集：称属于 A 而不属于 B 的全体元素，组成的集合为 B 对 A 的相对补集或差集，记作 A-B。容斥原理：以表示集合 A 中元素的数目，我们有，其中为 n 个集合称为
2、A 的阶。n 阶集合的全部子集数目为。A，B，C 为三个集合，就有下面的定律。（1）分配律（2）零律学科：奥数学科：奥数教学内容：集合（一）教学内容：集合（一）（3）排中律（4）吸收律（5）补交转换律（6）德摩根律的相对形式例题分析：例题分析：例例 1 1：对集合1，2，n及其每一个非空了集，定义一个唯一确定的“交替和”如下：按照递减的次序重新排列该子集，然后交替地减或加后继的数所得的结果，例如，集合的“交替和”是 9-6+4-2+1=6.的“交替和”是 6-5=1，的交替和是 2。那么，对于 n=7。求所有子集的“交替和”的总和。分析分析；n=7 时，集合7，6，5，4，3，2，1的非空子集
3、有个，虽然子集数目有限，但是逐一计算各自的“交替和”再相加，计算量仍然巨大，但是，根据“交替和”的定义，容易看到集合1，2，3，4，5，6，7与1，2，3，4，5，6的“交替和”是 7；可以想到把一个不含 7 的集和 A 与的“交替和”之和应为 7。那么，我们也就很容易解决这个问题了。解解：集合1，2，3，4，5，6，7的子集中，除去7外还有个非空子集合，把这个非空子集两两结组后分别计算每一组中“交替和”之和，结组原则是设这是把结合为一组，显然，每组中，“交替和”之和应为 7，共有组.所以,所有“交替和”之和应该为。说明说明：我们在这道题的证明过程中用了这类题目最典型的解法。就是“对应”的方法
4、，“对应”的方法在解决相等的问题中应用得更多。例例 2 2：设 A=1，2，2n.，证明：A 的任意 n+1 阶子集中，存在两个数，一个可被另一个整除。分析分析：对于 2n 个数中取 n+1 个数，我们应该有一个直觉就是把这 2n 个数分成 n 组，每组都必然满足题目条件，那么由抽屉原则命题就解决了。证明：证明：前2n个自然数中，共有n个奇数。根据自然数的一种有用的表达形式；n=(2k-1)2(,L 为非负整数)考查 A 的下列 n 个子集，容易看到：考虑 A 中任意 n+1 个元素，根据抽屉原则知，至少有两个元素是上述 n 个集合中同一个集合中的元素，这两个数中，必有一个可被另一个整除。说明
5、说明：把一个集合分成若干个两两不交的子集的并，也则分拆，这种分拆的方法在解决集合的问题时为常用方法之一。例例 3 3 3 3：某班对数学、物理、化学三科总评成绩统计如下：优秀的人数：数学 21 个，物理 19 个，化学 20 个，数学物理都优秀 9 人，物理化学都优秀 7 人。化学数学都优秀 8人。这个班有 5 人任何一科都不优秀。那么确定这个班人数以及仅有一科优秀的三科分别有多少个人。分析：分析：自然地设 A=数学总评优秀的人B=物理总评优秀的人C=化学总评优秀的人则已知|A|=21|B|=19|C|=20这表明全班人数在 41 至 48 人之间。仅数学优秀的人数是可见仅数学优秀的人数在 4
6、 至 11 人之间。同理仅物理优秀的人数在 3 至 10 人之间。同理仅化学优秀的人数在 5 至 12 人之间。解解：（略）。说明说明：先将具体的实际生活中的问题数学化，然后根据数学理论来解决这个问题不仅是竞赛中常见情况，也是在未来学习中数学真正有用的地方。例例 4 4 4 4：n 元集合具有多少个不同的不交子集对？分析：分析：我们一般想法是对于一个子集，求出与它不交的子集个数，然后就可以求出总的子集对来了。解解：如果子集对是有序的，即在子集对中可以区分第一个子集与第二个子集，则第一个子集若是 k 个元素，第二个子集就由其余 n-k 个元素组成，可能的情况是种，而这时第一个集合的选取的可能情况
7、应为种，那么 k 从 o 变到 n，总的情况可能就是。如果子集对是无序的，即两个子集相同但次序不同的子集对不认为不同，则对有序子集对中有一对是由两个空集组成，而对其它个有序对，每一对中交换两个子集的次序，得到的是同一个无序子集对，因此有个无序子集对，其中至少有一个子集非空，于是无序子集对的总数为分析二：分析二：我们可以从元素的角度来思考问题。对一个元素来说，它有三种不同的选择，在第一个集合中，在第二个集合中，或者不在两个集合中。解法二解法二：在计算有序对的数目时，对每一个元素来说有三种可能：它或在第一个子集，或在第二个子集，或不在其中任意一个子集，因此不同的不交有序子集对的总数，以下同解法一。
8、说明：说明：本题为 1973 年捷克的竞赛题，对题目的不同分析使我们得到了差异很大的两个解法，解法一从题目要求想起，很容易想到，但解出最后解却不见得那么简单，而解法二的想法是类似于集合分析的想法，很难想到，但想出后比较容易求解，两个解法对比一下正体现了数学思维的两方面，一个是纯代数想法，以计算的方法替代对题目更深层次的研究，另一个则是控掘题目本身的内在关系，找出最合适的解答，我们当然推荐第二种做法。例例 5 5 5 5：1992 位科学家，每人至少与 1329 人合作过，那么，其中一定有四位数学家两两合作过。分析：分析：在与一个人 A 合作的人中我们找到 B。再说明一定有人与 A 和 B 都合
9、作过为 C。最后再说明有人与 A、B、C 都合作过为 D，那么 A、B、C、D 就是找的人了。证 明证 明：一个人A。不妨设B与 之合作。那么。即C 与 A和 B 均 合 作 过，分 别 表 示 与 A、B 合 作 过 的 人 的 集 合。同 样 地，。所以存在。则 A、B、C、D 就是所求，证毕。说明说明：把一个普通的叙述性问题转化为集合的语言描述的问题通常为解题的关键之处，也是同学们需加强的。例例 6 6 6 6：集合 X 由 n 个元素构成，对两个子集，求得集合的元素个数，证明：所有求得个数之和为。分 析分 析：我 们 先 考 虑 一 个 简 单 情 况，n=2.这 时 有 四 个 集
10、合，记 为。交集情况就是。那么对于 n 很大时，我们有的不只是 4 个集合却可以以此形式分组。证明：证明：因为 集合 X 总共 有个不 同子集，所以不同 的有序子 集对共 有，将所有子集对分为个 4 元组：其中表示子集的补集 X-A。交换子集对的 4 元组中子集对的次序，得到的是同一个四元组，事实上，由子集对得到的 4 元组与由得到的完全相同，且。说明：说明：复杂的问题先考虑简单的特殊的情况是一种最常用的方法，从中找到共性后就很容易得到原题目有答案了。1一个集合含有 10 个互不相同的十进制两位数，证明：这个集合必有两个无公共元素的子集合，这两个子集元素和相等。2是否存在两个以非页整数为元素的
11、集合 A、B，使得任一个非负整数都可以被 A、B之中各取一数之和唯一表出。3对每个使得在 n 元集合中，可以取出 k 个子集，其中任意两个的交非合。4能否把分成两个积相等的不交集合。参考答案参考答案110 个元素的集合共有个非空子集，每一个这个集合的非空子集中数字之和小于，由抽屉原则知，必有两个子集，它们有相同的元素和，设为满足题目要求条件。2十进制为第 1 位。为第 i 位，考虑如下的 A、B：A 为奇位为 o 的那些非负整数组成。B 为偶位为 o 的那些非负整数组成。不难验证这样的AB 是符合题目要求的。3在集合中取定一个元素，并只考虑含的子集，这类子集的个数为集合的子集的个数，即为。因此
12、。另一方面，设从集合 X 至少取出个子集，将集合 X 的所有子集分成对。每一对由一个子集与它的补集组成，由抽屉原则，所取子集至少有两个组成一对，因此它们不交，于是。4对 7 取模，由于均不能为 7 的位数，所以(mod7).所以 n（n+1）(n+2)(n+3)(n+4)(n+5)(mod7)，而若能拆分应为0、1、4、2（mod7），所以集合不能拆成满足要求的集合。【经验谈】【经验谈】集合是数学中的重要基础知识，不论是高考还是数学竞赛中都少不了它的一席之地。本文将帮助你彻底掌握集合知识。【内容综述】【内容综述】集合是组合数学的基础，也是高中数学竞赛中的重要组成部分。希望大家通过本讲学习开拓思
13、路，灵活解题，另外，要想解好集合题目，相关知识也很重要。【例题分析】【例题分析】例例 1 1 1 1：设，是有限集合的 50 个子集，每个子集都含有的半数以上的元素，证明：存在子集，它至多含 5 个元素，并且和集合，中每一个集合至少有一个公共元。分析：我们知道，这种题目并没有什么特别好的办法，只能一个一个把这 5 个元素找出来，我们还是可以先将题目简化成简单形式，看是否方便理解一些，但这里我们就不这么做了。证明：设集合中元素个数为 n，子集，中每一个都含以上的元素，即所有这些子集的元素个数大于由抽屉原理，必有集合的元素，它至少属于 26 个子集，同理可证，对每个，在子集，中至少有个子集，它们具
14、有公共元素，在集合中取出一个元素，它至少属于 26 个子集，并作为集学科：奥数学科：奥数教学内容：集合教学内容：集合(二二)合中五个元素之一，去掉包含这个元素的 26 个子集，在余下 24 个子集中取一个元素，它至少属于 13 个子集，去掉这 13 个子集，在余下的 11 个子集中取一个元素，它至少属于6个子集，在余下 5 个子集中取一个元素，它属于 3 个子集，剩下两个子集再取一个公共元素就可以了，于是，求得集合的至多 5 个元素（在上述过程中所取的元素可能重复，所以可能小于 5），它们构成集合，而子集，中每一个都至少含有它的一个元素。说明：说明：这道题目当和均较小时也就可以作为小学生竞赛题
15、，而数目增大以后却成为了英国高中竞赛题目，假设我们在分析较小的数时可以把规律找出，而这是很简单的，那么整道题目也就迎刃而解了，这就告诉我们，做这类整数问题时，应该时时刻刻想到先将数目变小看看规律，然后再做题目本身。例例 2 2 2 2：有 11 人管理一个保险柜，可以在柜上加若干把锁，每把锁可以有若干把钥匙，问：如何加锁和如何分配各锁的钥匙，才能使任何 6 个人可以把保险柜打开，但任意 5 个人却不能。分析：我们反过来想一下，假设，是 11 个人打不开的锁的集合，从11个人中任意找 5 个人的可能性有种情况。要想把它们都区别开，也就是说至少要有 462 把锁。那么再对 462 把锁进行构造就可
16、以了。解：设加把锁，又设，是这 11 个人各自打不开的锁的集合，从 11 个集合中任选 5 个并集都不相同，故至少应有锁把，为分配好各锁的钥匙，设锁号依次为 1 号，2 号，462 号，同时把 11 个人任取 5 个的组合也编上 1 至 462 号，然后把锁和组合一一对应起来，给每个人发钥匙时，他所在的组的号的钥匙不给他，其他钥匙都给他，这时就满足题设了。说明说明：这个构造难度很大，这主要原因还是因数目太大了，也应该先从小的数目做起，最后回到原题。例例 3 3 3 3：把个元素的集合分为若干个两两不交的子集，按照下述规则将某一个子集中某些元素挪到另一个子集：从前一子集挪到后一子集的元素个数等于后一子集的元素个数（前一子集的元素个数应不小于后一子集的元素个数），证明：可以经过有限次挪动，使得到的子集与原集合相重合。分析：首先考虑到是一个很特殊的数，其次我们发现若两个集合的元素个数除以 2的若干次幂后若为奇数，那么，它们之间挪后就应为偶数这一事实，若还不能想到解答就试一下，时的情况，相信解答就不会难找到了。证明：考虑含奇数个元素的子集（如果有这样的子集），因为所有子集所含元素的个数总和是偶
