《高中竞赛教程》教案:第05讲 子集(教师) 下载本文

第5讲 子集

本讲内容有子集、子集的个数、集合的划分及子集的应用。 设a表示任意元素,A,B表示两个集合。若a?A?a?B ,则A?B ,即集合A是集合B的子集。规定空集是任何集合的子集。

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

类例题 例1 求集合M?{x?R|x2?ax?a?3?0}的子集的个数。

分析 欲求集合M的子集的个数,可先求出集合M的元素的个数。 解 由x当a当a2?ax?a?3?0,得??a2?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}的子集数为23?8,得所求集合P的个数为8。

- 1 -

例3 已知集合A?{2,3,4,5,6,7},对X全体S(X)的总和S。

?A,定义S(X)为X中所有元素之和。求

分析 要求出全体S(X)的总和S,只要求出每个元素出现的次数。

解 由集合元素的互异性,得集合A中某个元素在总合S中出现的次数,就是集合A中含有该元素的子集数。所以,

全体S(X)的总和S来源:www.shulihua.netwww.shulihua.net]?(2?3?4?5?6?7)?25?8640。

情景再现

1.设集合A?{(x,y)|y?x2?4x?1},B?{(x,y)|y?2x?1}。

求集合A?B的子集的个数。

2.若数集{a,1}?{1,2,a}?{1,2,4,a2},则a的值是_____。(1998年第九届“希

望杯”高一)

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

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

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

p种不同的诺言(p?0),任何两个政党都至少有一

p?1个。 (1972

种公共诺言,但没有两党作出完全相同的诺言。试证明,政党的数目不多于2年加拿大数学竞赛)

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

证明 将

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

因而政党数应不大于集合A的子集数。

又任何两个政党都至少有一种公共诺言,所以任何两个政党所对应的子集不可能是一对互补的

- 2 -

2p?2p?1。 子集。故政党数?2例5 证明:任意一个有限集的全部子集可以这样排列顺序,使得任何两个相邻的子集仅相差一个元素。 (1972年波兰数学奥林匹克)

分析 本题可采用构造方法进行证明,即对任意一个有限集的全部子集给出一个排列方法,满足题设的要求。为此,可从特殊情况入手进行探索。

来源:www.shulihua.net]若有限集元素的个数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,?,A2k,且任何两个相邻的子集仅相差一个

元素。

当n?k?1 即增加一个元素ak?1 时,按下面的方法可得由k?1个元素组成的有限集的A1,A2,?,A2k,ak?1?A2k,ak?1?A2k?1,?,ak?1?A1。

全部子集的一个排列,

因为

A1,A2,?,A2k共

2k

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

- 3 -

ak?1?A2k,ak?1?A2k?1,?,ak?1?A1共2k

个元素。又Ak与ak?12个子集中任何两个相邻的子集也仅相差一

?A2k也相差一个元素,因此,上述由k?1个元素组成的有限集的全部

子集的一个排列是符合条件的排列。

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

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

的最大值。 (1995年全国高中数学联赛)

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

解 由

1995[]?13315,又

x与

15x不能同属于集合

A,得

A1?{n|13?4n?199,n5?N}?A。

133由[]?8, 得集合A2?{n|9?n?133,n?N}已不可能与集合A1同为集合A15的子集。故|设

A|?1995?125?1870。

,经检验,

A3?{n|1?n?8,n?N} A1?A3是满足条件的集合,且

来源:www.shulihua.net]|A1?A3|?1870。所以,|A|的最大值为1870。

情景再现

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

5.已知A?B?2n?1

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

- 4 -

的(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}及其每一个非空子集,定义一个唯一确定的“交替和”按照递减的次序重新排列,然后从最大的数开始交替的减或加后继的数(例如,{1,“交替和”是9?6?4?2?1?62,4,6,9}的

。对n?7,求所有这些“交替;{5}的“交替和”是5)

和”的总和。 (第1届美国数学邀请赛)

分析 求所有这些“交替和”的总和的关键,在于每一个数字在“交替和”中出现的次数及符号。

解 对集合{1,2,?,n}的全部子集分为两类:含元素n的子集共有2子集也有2n?1个,不含元素n的

n?1个。

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

所以,所有这些“交替和”的总和为2n?16当n?7时,“交替和”的总和为7?2?448。 ?n。

例8 已知集合S中有10个元素,每个元素都是两位数。求证:一定可以从S中取出两个无公共元素的子集,使两个子集的元素和相等。

(1972年14届IMO)

分析 本题要求的是从集合S的子集中,找到两个元素和相等的子集。这两个子集即使有公共元素,只要同时除去公共元素就可以满足题意。

证明 由集合S中每个元素都是两位数,故它们的总和不超过

1000。而集合S共有

210?1024个子集。由抽屉原理,得集合S的子集中至少有两个子集的和相等。若这两个子集有

公共元素,只要同时从这两个子集中同时除去公共元素,得到两个无公共元素的子集,且使两个子集的元素和相等。即命题得证。

- 5 -