nbhkdz.com冰点文库

2012江苏省数学竞赛《提优教程》教案:第05讲 子集


第 5 讲 子集
本讲内容有子集、子集的个数、集合的划分及子集的应用。 设 a 表示任意元素, A ,

B 表示两个集合。若 a ? A ? a ? B

,则 A ?

B

,即

集合 A 是集合 B 的子集。规定空集是任何集合的子集。 子集是由原集合中的部分元素

构成。对于由 n 个元素组成的集合,它的每一个子集中元 素的构成,都是对这 n 个元素进行选择的结果。由于对每一个元素的选择都有两种可能(选 上或不选) ,因此,对这 n 个元素共有 2 种不同选择结果,即由 n 个元素组成的集合共有 2 个不同子集。其中,不同的非空子集有 2

n

n

n

? 1个,不同的真子集有 2 n 个。

A 类例题
例1 分析 解 当a 当a 求集合 M

? {x ? R | x 2 ? ax ? a ? 3 ? 0} 的子集的个数。

欲求集合 M 的子集的个数,可先求出集合 M 的元素的个数。 由x

2

? ax ? a ? 3 ? 0 ,得 ? ? a 2 ? 4a ? 12 ? ( x ? 2)( x ? 6) 。
原方程的解集为空集; 原方程的解集为单元素集;

? ?2 或 a ? 6 时, ? ? 0 ? ? ?2 或 a ? 6 时, ? ? 0 ?
a ? 6 时, ? ? 0 ?

当? 2 ?

原方程有两个不等的实数解。

所以,当 a 当a

? ?2 或 a ? 6 时,集合 M ? ? ,有 1 个子集;

? ?2 或 a ? 6 时,集合 M ? {x0} ,有 2 个子集;
a ? 6 时,集合 M ? {x1 , x2},有 4 个子集‘

当? 2 ? 例2

求满足{a, b} ?

P ? {a, b, c, d , e}的集合 P 的个数。

分析 本题要求的是集合{a, b, c, d , e}中, 必定含有元素 a, b 的子集的个数, 只要求 出集合{c, d , e} 的子集数。 解 由集合{c, d , e} 的子集数为 2 例 3

3

? 8 ,得所求集合 P 的个数为 8。
? A ,定义 S ( X ) 为 X 中所有元素之

已知集合 A ? {2,3,4,5,6,7},对 X

和。求全体 S ( X ) 的总和 S 。 分析 要求出全体 S ( X ) 的总和 S ,只要求出每个元素出现的次数。 解 由集合元素的互异性, 得集合 A 中某个元素在总合 S 中出现的次数, 就是集合 A 中

含有该元素的子集数。所以, 全体 S ( X ) 的总和 S

? (2 ? 3 ? 4 ? 5 ? 6 ? 7) ? 25 ? 8640 。

情景再现
1.设集合 A ? {( x,

y ) | y ? x 2 ? 4 x ? 1} , B ? {( x, y) | y ? 2x ? 1} 。

求集合 A ? B 的子集的个数。 2.若数集{

a , 1} ? {1, 2 , a} ? {1, 2 , 4 , a 2 } ,则 a 的值是_____。 (1998 年第
九届“希望杯”高一)

3.设非空集合 A ? { 1,2,3,4,5,6,7},且当 a ? 的 A 共有多少个?

A 时,必有 8 ? a ? A ,问:这样

B 类例题
例 4 在某次竞选中,各个政党共作出

p 种不同的诺言 ( p ? 0 ) ,任何两个政党都
p ?1
个。

至少有一种公共诺言, 但没有两党作出完全相同的诺言。 试证明, 政党的数目不多于 2

(1972 年加拿大数学竞赛) 分析 这是一道有实际背景的问题。 首先应选择适当的数学模型刻画这一问题。 由题意, 将“诺言”作为元素,运用集合进行分析和研究。 证明 将

p 种不同的诺言构成集合 A ,则每一个政党所作的诺言构成的集合是集合 A

的子集。因而政党数应不大于集合 A 的子集数。 又任何两个政党都至少有一种公共诺言,所以任何两个政党所对应的子集不可能是一对

2p ? 2 p ?1 。 互补的子集。故政党数 ? 2
例 5 证明:任意一个有限集的全部子集可以这样排列顺序,使得任何两个相邻的子集

仅相差一个元素。 (1972 年波兰数学奥林匹克) 分析 本题可采用构造方法进行证明,即对任意一个有限集的全部子集给出一个排列方 法,满足题设的要求。为此,可从特殊情况入手进行探索。 若有限集元素的个数 n 当n 当n

?1

时,子集数为 2,可排列为 ? , {a1} ;

? 2 时,子集数为 22,可排列为 ? ,{a1},{a1, a2},{a2};
? 3 时,子集数为 23,可排列为

? , {a1}, {a1, a2 }, {a2 }, {a2 , a3}, {a1, a2 , a3}, {a1, a3}, {a3};
??
每增加 1 个元素,子集数增加 1 倍。将原来已排列好的所有子集分别增加一个新元素, 得到又一列排列好的子集。再将排列好的子集倒序后,接排在原来已排好的子集列后面,得 到符合条件的新的子集列。 证明 设有限集的元素个数为 n 。 当n 当n 当n

? 1 时,子集数为 2,全部子集可排列为:? ,{a1} ; ? 2 时,子集数为 22,全部子集可排列为:? ,{a1},{a1, a2},{a2};
? 3 时,子集数为 23,全部子集可排列为:

? , {a1}, {a1, a2 }, {a2 }, {a2 , a3}, {a1, a2 , a3}, {a1, a3}, {a3};
??
若n

? k 时,子集数为 2k,全部子集可排列为: A1 , A2 , ? , A2 k ,且任何两个相邻的子集仅
当n

相差一个元素。

? k ?1

即增加一个元素 ak ?1 时,按下面的方法可得由 k

? 1 个元素组成的有

限集的全部子集的一个排列,

A1 , A2 , ? , A2 k , ak ?1 ? A2 k , ak ?1 ? A2 k ?1 , ?, ak ?1 ? A1 。
因为 A 1,

A2 , ? , A2 k 共 2k

个子集中任何两个相邻的子集仅相差一个元素,所以,

ak ?1 ? A2 k , ak ?1 ? A2 k ?1 , ?, ak ?1 ? A1 共 2k 个子集中任何两个相邻的子集也仅
相差一个元素。又 A k 与 ak ?1 2

? A2 k

也相差一个元素,因此,上述由 k

? 1 个元素组成的

有限集的全部子集的一个排列是符合条件的排列。 由此,我们得到对任意一个有限集的全部子集的符合条件的排列方法,即原命题得证。 例6设 M

15 x ? A 。 且当 x ? A 时, ? {n | 1 ? n ? 1995 , n ? N} , A ? M ,

求|

A | 的最大值。

(1995 年全国高中数学联赛)

分析 由题意, x 与15 x 不能同属于集合 A 。按照集合 A 的这一本质特征,构造具有 最多元素的集合 A 。 解 由

1995 [ ] ? 133 15

, 又

x



15 x

不 能 同 属 于 集 合

A

, 得

A1 ? {n | 1 3 4 ? n ? 1 9 9, 5 n ? N} ? A 。
由[

133 ] ? 8 , 得集合 A2 ? {n | 9 ? n ? 133 , n ? N} 已不可能与集合 A1 同为 15

集合 A 的子集。故 | 设

A | ? 1995 ? 125 ? 1870 。
, 经 检 验,

A3 ? {n | 1 ? n ? 8 , n ? N}

A1 ? A3 是 满 足 条件 的 集 合 ,且

| A1 ? A3 | ? 1870。所以, | A | 的最大值为 1870。

情景再现
4.在一次 IMO 竞赛中,k 个领队共使用 n 种不同语言。如果任何两个领队至少使用一 种共同语言,但没有任何两个领队使用的语言完全相同。求证: k

? 2n ?1



5.已知 A ? B

? {a1, a2 , a3} ,当 A ? B 时, ( A , B) 与 ( B , A) 视为不同的对,

则这样的 ( A , B) 对的个数有____________个。 (1993 年全国高中数学联赛) 6. 设集合 A 是整数集 Z 的子集, 其中的元素有正整数, 也有负整数, 且若 a , b ? A (允 许

a?b

) ,



a ? b? A











a,b? A





a ? b? A。

C 类例题
例7 对{ :对每一 1,2,?, n} 及其每一个非空子集,定义一个唯一确定的“交替和”

个子集按照递减的次序重新排列,然后从最大的数开始交替的减或加后继的数(例如, “交替和” 是 9 ? 6 ? 4 ? 2 ? 1 ? 6 ; {5} 的 “交替和” 是 5) 。 对n ? 7, {1, 2, 4, 6, 9} 的 求所有这些“交替和”的总和。 (第 1 届美国数学邀请赛) 分析 求所有这些“交替和”的总和的关键,在于每一个数字在“交替和”中出现的次 数及符号。 解 对集合{ 1,2,?, n} 的全部子集分为两类:含元素 n 的子集共有 2

n ?1

个,不含元

素 n 的子集也有 2

n ?1

个。

将含元素 n 的子集 {n, a1, a2 , ?, ak } 与不含元素 n 的子集 {a1, a2 ,?, ak } 相对 应,得这两个子集的“交替和”恒为 n 。 所以,所有这些“交替和”的总和为 2

n ?1

“交替和”的总和为 ? n 。当 n ? 7 时,

7 ? 26 ? 448 。
例 8 已知集合 S 中有 10 个元素,每个元素都是两位数。求证:一定可以从 S 中取出两 个无公共元素的子集,使两个子集的元素和相等。 (1972 年 14 届 IMO) 分析 本题要求的是从集合 S 的子集中,找到两个元素和相等的子集。这两个子集即使

有公共元素,只要同时除去公共元素就可以满足题意。 证明 由集合 S 中每个元素都是两位数,故它们的总和不超过 1000。而集合 S 共有

210 ? 1024个子集。由抽屉原理,得集合 S 的子集中至少有两个子集的和相等。若这两个
子集有公共元素,只要同时从这两个子集中同时除去公共元素,得到两个无公共元素的子集, 且使两个子集的元素和相等。即命题得证。

情景再现
7. 设集合 M 现对 M ? {n | 1 ? n ? 10 , n ? N}。 的任意一个非空子集 X , 令 aX

表示 X 中最大数与最小数之和,那么,所有这样的 a X 的算术平均值为___________。 8.由前 2 n 个正整数组成的集合 M

? {m ? N | 1 ? m ? 2n , n ? N ?} ,从中任取

n ? 1个元素组成 M
或者 a j

的子集 A , 求证: 集合 A 中必有两个数 ai

, a j , 使得 ai ? a j ? A ,

? 2ai 。

习题 5
1. 若{2, | a ? 1 |} ? {2,3, a

2

? 2a ? 1} ,试确定 a 的值。

2. 已知集合 A ? {n | 1 ? n ? 10 , 且 B ?C

n ? N},B ? {1,2,3,4,5},若 C 是 A 的子集,

? ? ,则子集 C 有多少个?
A ? {n ? N | 1 ? n ? 2m ? 1 , m ? N}
, 且

3 . 若

a? A

时 , 必 有

2m ? a ? A ,求证:这样的子集共有 2m ? 1个。
4.已知集合 X 的和记为

? {n | 1 ? n ? k ,

k , n ? N} ,对 A ? X ,

将 A 中所有元素 ,若

S ( A) , 将 X

分为互不相交的两个子集

A, B 且 A ? B ? X

S ( A) ? 2S ( B) ,求 k 的所有值。
5.矩形城市的道路非常规则,恰好东西向、南北向的道路分别有 m ,

n 条。一位妇女住

在城市的西南角,工作在东北角。她每天步行去工作。如果每个交叉路口不得经过两次,证 明她所能选取的路线数目 竞赛) 6.已知集合{n | 1 ? n ? 10 , 差的绝对值大于 1 的子集的个数。

f (m , n) 不大于 2mn 。

(第 9 届加拿大数学

n ? N} ,求满足至少含有两个元素且任意两个元素的

(1996 年上海爱朋思杯赛)
7. 设集合 A ? {x | 1 ?

x ? 100 , x ? N}且对任意的 x, y ? A ,必有 2 x ? y ,

则子集 A 所含元素个数的最大值为___________________. (1991 年河南省集训题) 8 .已知集合 S

? { n ? N | 1 ? n ? 1997 }. A ? { a1, a2 , ?, ak } 是 S 的子

集,且具有下述性质: “ A 中任意两个不同元素的和不能被 117 整除。 ”试确定 k 的最大值并

证明你的结论。 (1997 年全国高中数学联赛)

答案
情景再现
1. 解

? y ? x2 ? 4x ? 1 ? x2 ? 6x ? 2 ? 0 ? ? y ? 2x ? 1
? 36 ? 8 ? 28 ? 0 ,得 | A ? B |? 2 。

由?

所以,集合 A ? B 的子集的个数为 4。

2.

解 由题意,

a ? 2 ? a ? 4 或 a ? a ? a ? 0 或 a ? 1 。经检验,

a 的值是 0 或 4。
3. 解 由题意,1 与 7,2 与 6,3 与 5 中每一对数必须在同一个集合 A 内。因 此,所求集合 A 的个数等同于以 1 与 7, 2 与 6,3 与 5 及 4 为元素的集合的非 空子集的个数。所以,这样的 A 共有 2 4.

4

。 ? 1 ? 15 (个)

略证 设 n 种不同语言构成集合 P , 则任何一个领队对应于集合 P 中不互补的非

空子集。所以, 5. 解由集合

2n k? ? 2 n ?1 。 2

A , B 都是 A ? B 的子集, A ? B 且 A ? B ? {a1, a2 , a3} 。当

A ? ? 时, B 有 1 种取法;当 A 为一元集时, B 有 2 种取法;当 A 为二元集时,
B有 4
种取法;当

A 为三元集时, B 有 7

种取法。故不同的 ( A , B) 对有

1 ? 3 ? 2 ? 3 ? 4 ? 7 ? 26 (个) 。
6. 证明 设集合 A 中,最小的正整数为 x ,最大的负整数为 y 。 由 x? A,

y?A,

则x?

y ? A 。又 y ? x ? y ? x ,则 x ? y 不可能是非零

整数(否则,与

x , y 分别是集合 A 中最小的正整数和最大的负整数矛盾) ,即

x ? y ? 0 ? y ? ?x 。
由题意,易得 x ? A ? nx ? A (n ? N*) 。 综上, x ? A 若 a , b ? A, 则 得证。 7. 略 解 集 合

? A ? {a | a ? nx , n ? Z}。

a ? mx , b ? nx , ? a ? b ? (m ? n) x ? A 。即原命题
M
中 元 素

k

, 以 最 大 数 出 现 的 次 数 等 于 集 合

{n ? N | 1 ? n ? k ? 1 }的非空子集数 2k ?1 ,以最小数出现的次数等于集合 {n ? N | k ? 1 ? n ? 10 } 的非空子集数 210? k 。所以,所求的平均值为
1 2
10

?1

[1 ? (2 0 ? 29 ) ? 2 ? (2 ? 28 ) ? ? ? 10 ? (29 ? 2 0 )]

?
8.

1 2
10

?1

[(1 ? 10 )( 2 0 ? 2 ? ? ? 29 )] ? 11 。

略证 设子集 A ? {a1, a2 ,?, an ?1} ,且 a1 作差,得

? a2 ? ? ? an ?1 ? 2n 。

bi ? an ?1 ? ai , i ? 1,2, ?, n ,且 b1 ? b2 ? ? ? bn ? an ?1 ? 2n 。
于是

1 ? b1, b2 ,?, bn , a1, a2 ,?, an?1 ? 2n ,
bi ? a j ?i ? j ? ? an ?1 ? ai ? a j ? ai ? a j ? an ?1 ? A ;

由抽屉原理,必有



bi ? ai ? 2ai ? an ?1 (? a j ) 。即原命题得证。

习题 5
1. 略解

| a ? 1 | ? 3 ? a ? 2 或 a ? ?4 ;
| a ? 1 | ? a 2 ? 2a ? 1 ? a ? 1 或 a ? ?3 。

经检验, a 的值为 ? 4 或 2。 2. 解

1

由集合

A 的子集中除去不含集合 B 中元素的子集,得子集 C

共有

。 210 ? 25 ? 992 (个) 解2 子集 C 的元素是由集合{6,7,8,9,10}的任意一个子集中的元素, 与集合 B 的

任意一个非空子集中的元素组成。所求的子集 C 共有 2 3.

5

? (25 ? 1) ? 992 (个) 。

证明 由题意, 1 与 2m ? 1 , 2 与 2m ? 2 ,?中每一对数必须在同一个集合 A 内。 因此,所求集合 A 的个数等同于以 1 与 2m ? 1 ,2 与 2m ? 2 , ?及 m 为元素的集 合的非空子集的个数。所以,这样的 A 共有 2

m

。 ? 1(个)

4.

略解 由题意, S ( B) 因而, k 若k

1 1 ? S ( X ) ? k (k ? 1) 。 3 6

或 k ? 1是 3 的倍数。

? 3m ,集合 A 取集合 X 中形如 3m 或 3m ? 2 的元素构成,集合 B 取集合

X 中形如 3m ? 1的元素构成,则集合 A, B 满足题设要求;
若k

? 3m ? 1 ,集合 A 取集合 X 中形如 3m 或 3m ? 1的元素构成,集合 B 取

集合 X 中形如

3m ? 2 的元素构成,则集合 A, B 满足题设要求。

所以,所求 k 的值为 3m 或 3m ? 1 5.

(m ? N ) 。

略证 设 mn条道路构成集合 P 。这位妇女的每条路线对应于集合 P 的一个子集。所 以,他所能选取的路线数

f (m , n) 不大于集合 P 的子集数,即有 f (m , n) ? 2mn 。

6.

略解 设 ak 表示集合 Ak 集合 Ak ? 2

? {n | 1 ? n ? k , n ? N} 满足题设条件的子集数。考察

? {n | 1 ? n ? k ? 2 , n ? N}满足题设条件的子集构成。它的满足条件
? 2 ,即集合 Ak ?1 中满足条件的子集,应有 ak ?1

的子集可分为两类:一类不含元素 k 个;另一类含元素 k

? 2 ,此类子集或者是集合 Ak 中满足条件的子集有 ak 个,或者是

{1 , k ? 2} , {2 , k ? 2} ,? , {k , k ? 2}等有 k 个。因此,

ak ? 2 ? ak ?1 ? ak ? k
易知,

k ? N.

a3 ? 1 ,

({ 1,3}) ,

a4 ? 3 ,
由上式可依次推得,

({ 1,3},{1,4},{2,4}) ,

a5 ? 7, a6 ? 14, ? , a10 ? 133.
7. 略解 由 [

100 50 25 12 ] ? 50 , [ ] ? 25 , [ ] ? 12 , [ ] ? 6 , ? 2 2 2 2

构造满足条件且元素最多的子集:

{1} ? {4,5,6} ? {13,14,?,25} ? {51,52,?100}
共有元素 67 个。 8. 略解 将 1997 按除以 117 的不同余数分为 117 类: [0], [1], [2] , ? ,

[116]

([n]表示除以 117 的余数为 n).
由1997 个元素。 由题意,余数之和为 117 的两类不能同在一个子集内,从而构造含元素最多的子集: 取 [1] , [2] , ? , [58] 类的所有元素及[0]类的一个元素构成集合 A ,此时共有元素 995 个。即 k 的最大值为 995。 (证明略)

? 117 ? 17 ? 8 ,得 [1], [2], ?[8] 每类各 18

个元素,其余各类各

17


2012江苏省数学竞赛《提优教程》教案:第05讲 子集

2012江苏省数学竞赛《提优教程》教案:第05讲 子集_学科竞赛_高中教育_教育专区。第 5 讲 子集本讲内容有子集子集的个数、集合的划分及子集的应用。 设 ...

2012江苏省数学竞赛《提优教程》教案:第05讲 子集

2012江苏省数学竞赛《提优教程》教案:第05讲 子集 隐藏>> 第5 讲 子集本讲内容有子集子集的个数、集合的划分及子集的应用。 设 a 表示任意元素, A, ...

2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合

2012江苏省数学竞赛《提优教程》教案:第57讲 排列与组合_学科竞赛_高中教育_教育...126 个五位 “渐升数” ,若把这些数按从小到大的顺序排列,则第 100 个数...

2012江苏省数学竞赛《提优教程》教案:第59讲 概率1

2012江苏省数学竞赛《提优教程》教案:第59讲 概率1...随机事件:样本空间的子集称为随机事件,简称事件. 4...P(C) ? 0.05. 因为事件 A,B,C 相互独立,恰...

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖

2012江苏省数学竞赛《提优教程》教案:第66讲_覆盖_学科竞赛_高中教育_教育专区...剩下的圆心组成的点集的 直径≤2,易知一个边长为 2 的正方形可以覆盖这些...

2012江苏省数学竞赛《提优教程》教案:第62讲__多项式

2012江苏省数学竞赛《提优教程》教案:第62讲__多项式_学科竞赛_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 2012江苏省数学竞赛《提优教程》教案:第...

2012江苏省数学竞赛《提优教程》教案:第50讲 直线与区域

2012江苏省数学竞赛《提优教程》教案:第50讲 直线与区域_学科竞赛_高中教育_教育专区。第 10 讲 A 类例题 直线与区域 直线是平面上最简单、最常见的几何图形....

2012江苏省数学竞赛《提优教程》教案:第36讲__同_余

2012江苏省数学竞赛《提优教程》教案:第36讲__同_余_学科竞赛_高中教育_教育专区。第 17 讲 同 余 同余是数论中的重要概念,同余理论是研究整数问题的重要工具...

2012江苏省数学竞赛《提优教程》教案:第42讲 平均不等式

2012江苏省数学竞赛《提优教程》教案:第42讲 平均不等式_学科竞赛_高中教育_教育专区。平均不等式 本节主要内容是两个、三个或 n 个(n∈N+)正数的算术平均数...

2012江苏省数学竞赛《提优教程》教案:第52讲 圆锥曲线(一)

2012江苏省数学竞赛《提优教程》教案:第52讲 圆锥曲线(一)_学科竞赛_高中教育...(或 y1+y2、y1y2)的式 子; (2)由两条曲线(含直线)的方程消去一个未知...