第 16 讲 组合原理解决集合与命题
1. 容斥原理基本公式
(1) card ( A ∪B)=card ( A)+card (B)−card ( A ∩B) ;
(2) card
( A ∪B∪C)=card ( A)+card (B)+card (C)−card ( A ∩B)−card ( A ∩C)−card (B∩C)+card ( A ∩B∩C
2. 抽屉原理基本形式
如果把 n+1 个元素分成 n 个集合,那么不管怎么分,都存在一个集合,其中
至少有两个元素.
热点课堂
【例 1】一群学生参加学科夏令营, 每名同学参加至少一个学科考试. 已知
有 100 名学生参加了数学考试, 50 名学生参加了物理考试, 48 名学生参加了化
学考试. 学生总数是只参加一门考试学生人数的 2 倍, 也是参加三门考试学生
人数的 3 倍, 则学生总数为( )
A. 108 名 B. 120 名
C. 125 名 D. 前三个答案都不对
【分析】本质上是容斥原理的使用,设只参加数学、物理、化学考试的学生
人数分别为 x , y , z ; 参加物理和化学考试的学生人数为 a ; 参加化学和数学
考试的学生人数为 b ; 参加数学和物理考试的学生人数为 c ; 同时参加三门学
科考试的学生人数为 m .
如图,根据题意,有 {
x +b+c +m=100,
y +c +a+m=50,
z +a+b+m= 48,
x + y + z +a+b+c +m=2(x + y + z)=3m,)
前三式相加得 (x + y + z)+2(a+b+c)+3m=198 ,
将 x + y + z = 3
2 m,a+b+c = m
2 代入上式可得 3
2 m+m+3m=198 ,解得 m=36
.
故学生总数为 36×3=108 .
【解答】A
【例 2】定义 f M (x)={
−1, x∈M ,
1, x∉M , ) 且 M Δ N ={x∣f M (x)⋅f N (x)=−1) ,集
合 A ={x∣x =k ,k ∈N ,1≤k ≤2016} ,集合 B ={x∣x =2k ,k ∈N ,1≤k ≤2016} .
(1) 求 f A (2016),f B(2016) ；
(2) 已知非整数集 X ,求 m=card (X Δ A)+card (X Δ B) 的最小值.
【分析】(1)要求 f A (2016),f B(2016) 的值,首先分析集合 A ,B ,由已知可得
集合 A 中为 1 至 2016 的所有正数,集合 B 中为 2 至 4032 的所有正偶数,
所以可得 f A (2016),f B(2016) . (2) 要求 m=card (X Δ A)+card (X Δ B) ,需要求集
合 M Δ N ，可以借助韦恩图表示 M Δ N ={x∣f M (x)⋅f N (x)=−1) .
图 1
【解答】 (1)f A (2016)=−1,f B(2016)=−1 ;
(3) 分析 M Δ N ={x∣f M (x)⋅f N (x)=−1) 表示 ∁M ∪N M ∩N ，
图 2
用韦恩图表示如图 1: card (M Δ N )= x1+ x3 ,
如图 2,设集合 A ,B , X 各个区域内元素个数为 x1, x2,⋯, x7 ,
由韦恩图可得 m=card (X Δ A)+card (X Δ B)
= x1+ x2+ x6+ x7+ x2+ x3+ x4+ x7
=(x1+ x2+ x3+ x4+ x5+ x6)−x5+2 x7+ x2
=(x1+ x2+ x3+ x4+ x5+ x6)−(x5+ x2)+2 x7+2 x2
=2016+1008−(x2+ x5)+2(x2+ x7)
=2016+2(x2+ x7)≥2016,
所以 m 的最小值为 2016,当 X ={2,4 ,6,8,⋯,2016} ,可取得最小值.
【例 3】已知在边长为 1 的等边三角形内 (包括边界) 有任意五个点. 证
明: 至少有两个点之间的距离不大于 1
2 .
【分析】假设任意两个点之间的距离都大于 1
2 ,构造出 4 个抽屉是关键.
【解答】5 个点的分布是任意的. 如果要证明 “在边长为 1 的等边三角形
内 (包括边界) 有 5 个点，那么这 5 个点中一定有距离不大于 1
2 的两点”，
则顺次连结三角形三边中点，即三角形的三条中位线可以将等边三角形分为 4
个全等的边长为 1
2 的小等边三角形,则 5 个点中必有 2 个点位于同一个小等
边三角形中 (包括边界),其距离便不大于 1
2 .
【例 4】设集合 A ⊆{1,2,3,⋯,14 } ,若 A 中的任意 3 个元素均不构成
等差数列,则 A 中元素最多有( )
A. 7 个 B. 8 个 C. 9 个 D. 10 个
【分析】首先根据限制条件确定集合元素个数的上限, 其次构造出符合要
求的集合.
设 A ={a1,a2,⋯,ak) ,不妨设 a1<a2<⋯<ak ,
由题意得 a3−a1≥3,a5−a3≥3 ,且 a3−a1≠a5−a3 ,
所以 a5−a1≥7 ,同理 a9−a5≥7 ,所以 a9−a1≥14 ,所以 a9≥15 ,
所以 k <9 ,即 k ≤8 .
下面证明 k =8 可能取到,取 A ={1,2,4 ,5,10,11,13,14} 满足题意,
所以 A 中元素最多有 8 个.
【解答】B
【例 5】将正整数集合分成两个不相交的子集的并集, 使得每个子集都不
包含无穷等差数列的不同方式种数为( )
A. 0 B. 1 种
C. 无穷多种 D. 前三个答案都不对
【分析】这是一个集合的分划问题, 主要是集合的构造: 令集合
A1={1}, A2={2,3}, A3={4 ,5,6}, A4={7,8,9,10},⋯, An={
n(n−1)
2
+1, n(n−1)
2
+2,⋯, n(n+1)
2 ),⋯,
取 P = A1∪A3∪A5∪⋯,Q =C N ⋅P 满足题意;
取 P = A3∪A5∪A7∪⋯,Q =C N
∗P 满足题意;
取 P = A5∪A7∪A9∪⋯,Q =C N
∗P 满足题意; ⋯ ;
故满足题意的分划有无穷多种.
【解答】C
【例 6】已知 x1, x2, x3, x4, x5 是正整数,任取四个其和组成的集合为
{44 ,45,46,47} , 则这五个数为_____.
【分析】五个数任取四个应该可以得到 C5
4=5 个不同的和,现条件中只有 4
个不同的和,故必有两个和值相同. 而这五个和值之和为 4(x1+ x2+ x3+ x4+ x5) ,
是 4 的倍数,
所
以
这
个
相
同
的
和
值
只
可
能
是
46,
即
x1+ x2+ x3+ x4+ x5= 44 + 45+ 46+ 46+ 47
4
=57 ,
故
这
五
个
数
分
别
为
57−44 =13,57−45=12,57−46=11,57−47 =10,57−46=11 ,
即10,11,11,12,13.
