1
高中数学·竞赛一试·第2 讲
在数学竞赛中,集合常常与组合问题同时出现.一方面,组合问题用集合语言叙述会比较简洁;另
一方面,某些集合问题的处理方法渐渐演变成了组合数学中的经典问题.本讲选择了一些有代表性的问
题进行讲解.
一、集合的阶
有限集A 的元素数目也叫做这个集合的阶,记作|A|.
若M 为由一些给定的集合构成的集合,则称集合M 为集族.设A 为有限集,由A 的若干子集构成
的集合称为集合A 的一个子集族.求满足一定条件的集族的阶也是一类常见的问题.
显然,若|A|=n,则由A 的所有子集构成的子集族的阶为2n.
二、集合的划分与覆盖
集合的划分对我们来说并不陌生,所谓划分就是把一类事物分成若干小类,同时要求每两个小类
中没有公共的元素,而它们并在一起即是原来的事物的全体.用集合的语言可表述为:
覆盖设D={A1,A2,…,An}是集合A 的非空子集族,如果A=A1∪A2∪…∪An,那么称D 为集合A 的一
个n–覆盖.
划分若D={A1,A2,…,An}是集合A 的一个n–覆盖且满足Ai⋂Aj=∅(1≤i<j≤n),则称D 为集合A 的
一个n–划分,其中n 叫做划分的长度.
本讲概述
第2 讲
集合中的经典问题
2
高中数学·竞赛一试·第2 讲
三、容斥原理
(2 元)|𝐴∪𝐵| = |𝐴| + |𝐵| −|𝐴∩𝐵|
(3 元)|𝐴∪𝐵∪𝐶| = |𝐴| + |𝐵| + |𝐶| −|𝐴∩𝐵| −|𝐵∩𝐶| −|𝐶∩𝐴| + |𝐴∩𝐵∩𝐶|
(一般地,n 元)
|𝐴1 ∪𝐴2 ∪⋯∪𝐴𝑛| = ∑|𝐴𝑖|
𝑛
𝑖=1
−
∑
|𝐴𝑖∩𝐴𝑗|
1≤𝑖<𝑗≤𝑛
+
∑
|𝐴𝑖∩𝐴𝑗∩𝐴𝑘|
1≤𝑖<𝑗<𝑘≤𝑛
−⋯
+(−1)𝑛−1|𝐴1 ∩𝐴2 ∩⋯∩𝐴𝑛|
3
高中数学·竞赛一试·第2 讲
【例1】 (1)已知a 为给定的实数,那么集合M={x|x
2-3x-a
2+2=0,x∈R}的子集的个数为_________.
(2)定义集合A–B={x|x∈A,x∉B}.若M={1,2,…,120},A,B⊆M,且(A–B)∪(B–A)=M,则
满足条件的不同的集合对(A,B)共有个_________.
(3)定义集合运算:A×B={xy|x∈A,y∈B},设A={1,2,3,4},B={5,6,7,8},则集合A×B 的
所有非空子集元素之和的总和为_________.
【例2】 对于任何集合S,用|S|表示集合S 中的元素个数,用n(S)表示集合S 的子集个数.若A,B,C
是三个有限集,且满足条件:①|A|=|B|=1000;②n(A)+n(B)+n(C)=n(A∪B∪C).求|A∩B∩
C|的最大值.
例题精讲
4
高中数学·竞赛一试·第2 讲
【例3】 设集合Sn={1,2,…,n}.若X 是Sn 的子集,把X 中所有数的和称为X 的“容量”(规定空集的
容量为0),若X 的容量为奇(偶)数,则称X 为Sn 的奇(偶)子集.
(1)证明:Sn 的奇子集与偶子集个数相等;
(2)证明:当n>2 时,Sn 的所有奇子集的容量之和等于所有偶子集的容量之和;
(3)当n>2 时,求Sn 的所有奇子集的容量之和.
【例4】 已知集合B 是集合{1,2,…,100}的子集,且对任意x∈B,都有3x∉B,则集合B 中的元素最
多有_________个.
5
高中数学·竞赛一试·第2 讲
【例5】 已知n 是正整数,设集合S={1,2,…,n}.记f(n)为同时满足下列条件的集合A 的个数:
①A⊆S;②若x∈A,则2x∉A;③若x∈CSA,则2x∉CSA.
(1)求f(4)的值;(2)求f(n)的解析式(用n 表示).
【例6】 求所有的正整数n,使得集合M={1,2,…,4n}可以分拆成n 个四元子集M1,M2,…,Mn,对于
每个子集Mk={ak,bk,ck,dk}(k=1,2,…,n)中的ak,bk,ck,dk 四个元素而言,其中的一个元素等于
另外三个元素的算术平均.
6
高中数学·竞赛一试·第2 讲
【例7】 给定集合A={1,2,3,⋯,2n+1}.试求一个包含元素最多的集合A 的子集B,使B 中任意三个元
素x,y,z(可以相同)都有x+y≠z.
【例8】 已知集合A 中的元素都是正整数,元素的最小值为1,最大值为100,且除1 之外的每个元素
都等于A 中的两个数(可以相同)之和.试求集合A 的元素个数的最小值.