nbhkdz.com冰点文库

高中奥数集合

时间:2012-09-17


第一讲

集合与容斥原理

主讲:

罗老师

摩根定律 1、设全集为U,其子集为A、B,则有
CU ( A ? B ) ? CU A ? CU B
CU ( A ? B ) ? CU A ? CU B

称为摩根定律,又叫反演律。 摩根定律用文字语言可以简单的叙述为:

两个集合的交集的补集等于它们各自补集的并集;

两个集合的并集的补集等于它们各自补集的交集。
2、摩根定律的一般形式设全集为U ,其子集为
Ai , i ? 1, 2, 3 ..., n

则:

C U ( Ai ? A j ? ...) ? C U Ai ? C U A j ? ...
C U ( Ai ? A j ? ...) ? C U Ai ? C U A j ? ...

称为摩根定律,又叫反演律。

摩根定律——交 集的补集韦恩图

摩根定律——并 集的补集韦恩图

3、应用举例
U ? ? x | x ? 3 n , x ? 3 0, n ? N
*

? , CU A ? B

? ? 6,1 5

?,

A ? C U B ? ? 3, 2 1? ,

C U A ? C U B ? ? 9,1 8, 2 4

?,

求集合

A? B

范例解答:如图
U ? ? 3, 6, 9,1 2,1 5,1 8, 2 1, 2 4, 2 7 ? ,
C U A ? C U B ? ? 9,18, 24 ? ,

由摩根定律
C U ( A ? B ) ? ? 9,18, 24 ? ,
? A ? B ? ? 3, 6,1 2,1 5, 2 1, 2 7 ? .

又 C U A ? B ? ? 6,1 5? , A ? C U B ? ? 3, 2 1? ,
? A ? B ? ?1 2, 2 7 ? .

有限集元素的数目

——容斥原理
按照集合的元素个数是否为有限集,集 合可分为有限集和无限集,若集合A是有限 集,用 | A | 表示它的元素个数或用 card ( A ) 表示 。

定理1

设A、B都是有限集,则

| A ? B |? | A | ? | B | ? | A ? B | .

定理2

设A、B、C都是有限集,则

| A ? B ? C |? | A | ? | B | ? | B | ? | A ? B | ? | B ? C |

? |C ? A | ? | A ? B ? C |.

例题精讲
例1、在1,2,…..,1000中,有多少个正整数 既不是2的倍数,又不是5的倍数?
解 设
S ? ?1, 2, ...1 0 0 0 ? , A2 ? ? a | a ? S , 2 | a ? ,

A5 ? ? a | a ? S , 5 | a ? .
| A5 | ? 1000 5



| A 2 |?

1000 2

? 5 0 0,

? 2 0 0, | A 2 ? A5 | ?

1000 10

? 1 0 0,

于是

| C S A2 ? C S A5 |? | S | ? (| A2 | ? | A5 |) ? | A2 ? A5 |

? 1000 ? (500 ? 200) ? 100 ? 400
例2 集合A的元素都是正整数,其中最小的 是1,最大的是100,除1以外,每一个元素都 等于集合A中的两个数(可以相同)的和,求 集合A的元素的个数的最小值。 解 设
A ? ?1, a1 , a 2 , ..., a n ,1 0 0 ? ,

其中

1 ? a1 ? a 2 ? .... ? a n ? 100.

则 a1 ? 1 ? 1 ? 2 .

若n=6,则

a 2 ? 2 ? 2 ? 4, a 3 ? 4 ? 4 ? 8, a 4 ? 8 ? 8 ? 16,

a 5 ? 16 ? 16 ? 32, a 6 ? 32 ? 32 ? 64.
a 5 ? a 6 ? 32 ? 64 ? 96 ? 100,

由于

所以

100 ? 2 a6 , a6 ? 50.

又 a 4 ? a 5 ? 1 6 ? 3 2 ? 4 8 ? 5 0, 所以
5 0 ? 2 a5 , a5 ? 2 5 .

而 矛盾

a 3 ? a 4 ? 8 ? 16 ? 24 ? 25,

所以

25 ? 2 a 4 ,

a 若 n ? 5, 则由上可知, n

? 3 2, 2 a n ? 6 4 ? 1 0 0,

不可能。

综上可知,| A |? 9 又当 A ? ?1, 2, 3, 5,1 0, 2 0, 2 5, 5 0,1 0 0 ? 时,集合A满足题述性质,且
| A |? 9 .

故集合A的元素个数的最小值为9。 例3 设 S
? ?1, 2, 3, 4 ? ,

n 项的数列 a1 , a 2 , ...a n

有下列的性质:对于S的任一非空子集B(B的 元素个数记为 | B | ),在该数列中有相邻的| B |

项恰好组成集合B,求 n 的最小值。 解 首先,S中的每个数在数列
a1 , a 2 , ...a n

中至少出现2次,事实上,若S中的某个数在 这个数列中只出现1次,由于含这个数的二元 子集共有3个,但在数列中含这个数的相邻两 项至多只有两种取法,因而不可能3个含这个 数的二元子集都在数列相邻两项中出现。 由于S中的每个数在数列 a1 , a 2 , ...a n

中至少出现2次,所以, n ? 8.

下面,我们构造一个n=8且满足题设条件的例子, 8项数列:3,1,2,3,4,1,2,4 就是满足条件的一个数列。 综上所述,n的最小值为8。 例4 设 A ? ?1, 2, 3, ..., 2 n , 2 n ? 1? , B是A的一个子 集,且B中的任意三个不同元素 x , y , z , 都有 x ? y ? z . 求 | B | 的最大值。

解 设 则

O ? ?1, 3, ..., 2 n ? 1? , E ? ? 2, 4, ..., 2 n ? .

A ? O ? E.



B ? ? b1 , ...b s , c1 , ...c t ? ,

其中

b1 , ..., b s ? O , c1 , ...c t ? E



b1 ? b 2 ? ... ? b s

由题设知
b s ? bi ? c j ,

其中

i ? 1, 2, ..., s ? 1, j ? 1, 2, ...., t (否则集B中就
bi , c j , b s ,

有三个元素

使得

bi ? c j ? b s ),



2 ? b s ? bi ? 2 n ,

即 所以

b s ? bi ? E , i ? 1, 2, ..., s ? 1 .

b s ? b1 , b s ? b 2 , ..., b s ? b s ?1 , c1 , ..., c t

是E中互不相同的元素,故
( s ? 1) ? t ? | E |? n ,
| B |? s ? t ? n ? 1 .

又当

B ? ? n ? 1, n ? 2, ..., 2 n ? 1?

时,B中任意两 从而

个不同元素 x , y , 都有 x ? y ? 2 n ? 3, B满足题意。 综上所述,|B| 的最大值为n+1.

说明:例2,例3,例4,我们都是先求出
一个上界或下界,然后再构造一个具体的 例子来说明这个上界是可以达到的,这是

处理这种最值问题的常用手法,在实际解题时, 我们往往先通过具体的例子猜出这个上界,然 后再设法证明。 例5 设 X ? ?1, 2, ...,1 0 0? , 对X的任一非空 子集M, M中的最大数与最小数的和称为M的特征,记 m (M ) 为 ,求X的所有非空子集的特 征的平均数。 解 设 A? X
?



f :A? A,
'

A ? ?1 0 1 ? a | a ? A ?
'

? ?

X,

于是 f : A ? A 是X的非空子集的全体(子集 组成的集)Y到Y自身的满射,记X的非空子集 100 n ? 2 ? 1 ),则特 为 A1 , A2 , ... An (其中 征的平均数为
'

1

? n

n

m ( Ai ) ?

i ?1

? 2n

1

n

( m ( Ai ) ? m ( Ai )).
'

i ?1

由于 A 中的最大数与 A 中的最小数的和为101, ' A A 中最小数与 中的最大数的和也为101

'



m ( Ai ) ? m ( Ai ) ? 2 0 2, 从而特征的平均数为
'

1 2n

? 202 ? n ? 101.

例6 某班语文、数学、外语三门课程其中考试 成绩统计结果:至少有一门课程得满分的学生 只有18人,语文得满分的有9人,数学得满分 的有11人,外语得满分的有8人,语文、数学 都得满分的有5人,数学、外语都得满分的有3 人,语文、外语都得满分的有4人。问:

(1)语文、数学两门课程至少有一门得满分 的学生有多少人? (2)语文、数学、外语三门课程都得满分的 学生有多少人? 解 设该班期中考试语文、数学、外语得满 分的学生的集合分别为A、B、C,由题意知
| A |? 9, | B | ? 1 1, | C | ? 8 . | A ? B | ? 5, | B ? C | ? 3, | C ? A | ? 4,

| A ? B ? C |? 18.

(1)语文、数学两门课程至少有一门得满分 的学生有
| A ? B |? | A | ? | B | ? | A ? B |? 9 ? 11 ? 5 ? 15

(人)

(2)语文、数学、外语都得满分的学生有
| A ? B ? C |? | A ? B ? C | ? | A | ? | B | ? | C | ? | A ? B | ?

| B ? C | ? | C ? A |? 18 ? 9 ? 11 ? 8 ? 5 ? 3 ? 4 ? 2 (人)

例7 考虑集合 S ? ?1, 2, ...,1 0 ? 的所有非空子集, 若一个非空子集中的偶数的数目不少于奇数的数 目,称这个子集是“好子集”,则求“好子集” 的数目。 解 方法一: 设一个“好子集”中有( i ? 1, 2, 3, 4, 5) 个偶数, i 则奇数的数目可以有 j ? 0,1, ..., i 个,因此

“好子集”的数目为

?
3

5

i ?1

(C 5 ? C 5 ) ? C 5 (C 5 ? C 5 ) ? C 5 (C 5 ? C 5 ? C 5 ) ?
i j 1 0 1 2 0 1 2 j?0

i

C 5 (C 5 ? C 5 ? C 5 ? C 5 ) ? C 5 (C 5 ? C 5 ? C 5 ? C 5 ? C 5 ) ?
0 1 2 3 4 0 1 2 3 4

? C 5 ( C 5 ? C 5 ? C 5 ? C 5 ? C 5 ? C 5 ) ? 637
5 0 1 2 3 4 5

方法二: S的非空子集共有 ? 1 ? 1023(个),根据子集中 偶数与奇数个数的多少可分为三类:
2
10

(1)偶数多于奇数;(2)奇数多于偶数;

(3)奇数与偶数个数相等。由于S中的10个元素 偶数与奇数的个数相等,所以(1)、(2)的子 集数相等,现考虑第三类,分别考虑含有2、4、

6、8、10个元素子集的数目,则共有子集数为
C 5 C 5 ? C 5 C 5 ? C 5 C 5 ? C 5 C 5 ? 1 ? 251
1 1 2 2 3 3 4 4

所以,第一类子集数为

1 2

(1 0 2 3 ? 2 5 1) ? 3 8 6

因此,“好子集”的数目为386+251=637(个)

例8 将集合 S ? ?1, 2, ..., 3 6? 分拆为k个互不相交的非空 子集 A , A , ..., A 的并,并且对于每一个 A ( i ? 1, 2, ..., k ), 其中任意两个不同的元素的和都不是完全平方数, 求k的最小值。
1 2 K
i

解 首先,考虑数6、19、30,因为 6 ? 1 9 ? 5 2 ,
6 ? 3 0 ? 6 ,1 9 ? 3 0 ? 7 ,
2 2

所以,这3个数必须属于3个不

同的子集,于是

k ? 3.

另一方面,集合 S ? ?1, 2, ..., 3 6? 可以分拆为3个 互不相交的非空子集 满
A1 , A2 , A3

的并,使得它们

足题设条件,令
A1 ? ? 4 k ? 3 | 0 ? k ? 8? ? ? 4, 8,16, 24, 36 ? ,
A2 ? ? 4 k ? 1 | 0 ? k ? 8? ? ? 6,1 4,1 8, 2 6, 3 4 ? ,
A3 ? ? 2,10,12, 20, 22, 28, 30, 32 ? ,

由于完全平方数除以4的余数只能是0或者1,所以, A1 , A2 , A3 容易证 满足题设条件。 综上所述,k的最小值为3。 例9 将与105互质的所有正整数从小到大排成数 列,求这个数列的第1000项。

解 设 S ? ?1, 2, ...,1 0 5? , A

3

? ?a | a ? S ,

且 3 | a? , A

5

? ?a | a ? S ,



5 | a ? , A7 ? ? a | a ? S , 且 7 | a ? ,
| A3 | ? 105 3 ? 3 5, | A5 |?
105 3? 5


105 7
105 7?3 ? 5.

105 5

? 2 1, | A7 | ?
105 5?7

? 15.

| A3 ? A5 | ?

? 7 . | A5 ? A 7 | ?
105 3? 5? 7

? 3 . | A 7 ? A3 | ?

| A3 ? A5 ? A 7 | ?

? 1, | S |? 1 0 5 .

在1到105中,与105互质的数有
| C S A3 ? C S A 5 ? C S A 7 | ? | S | ? | A 3 ? A 5 ? A 7 |

? | S | ? (| A3 | ? | A5 | ? | A 7 |) ? (| A3 ? A5 | ? | A5 ? A 7 | ? | A 7 ? A 3 |) ? | A3 ? A5 ? A 7 | ? 1 0 5 ? (3 5 ? 2 1 ? 1 5) ? (7 ? 3 ? 5) ? 1 ? 48.

设与105互质的正整数按从小到大的顺序排列为
a1 , a 2 , ..., a n , ...,



a 1 ? 1, a 2 ? 2, a 3 ? 4, ..., a 4 8 ? 1 0 4, a 4 9 ? 1 0 5 ? 1, a 5 0 ? 1 0 5 ? 2, a 5 1 ? 1 0 5 ? 4, ...., a 9 6 ? 1 0 5 ? 1 0 4, ....

因为 1 0 0 0 ? 4 8 ? 2 0 ? 4 0, 所以 由于
a 4 2 ? 8 9, a 4 1 ? 8 8, a 4 0 ? 8 6,

a1 0 0 0 ? 1 0 5 ? 2 0 ? a 4 0 .

a 4 8 ? 1 0 4, a 4 7 ? 1 0 3, a 4 6 ? 1 0 1, a 4 5 ? 9 7 , a 4 4 ? 9 4, a 4 3 ? 9 2,

所以

a1000 ? 105 ? 20 ? 86 ? 2186


赞助商链接

【精选】冀教版数学一上《比较》(一)学案-数学

【精选】冀教版数学一上《比较》(一)学案-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不等式、解...

【精选】冀教版数学一上《1-5各数的认识》教学设计1-数学

【精选】冀教版数学一上《1-5各数的认识》教学设计1-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、...

【精选】六年级数学知识竞赛试题-数学_数学_高中教育_教育专区

【精选】六年级数学知识竞赛试题-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不等式、解三角形 六...

【精选】六年级数学总复习题库(相当全面)-数学

【精选】六年级数学总复习题库(相当全面)-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不等式、解...

【精选】湖北鄂州高中素质班自主招生数学试题-数学

【精选】湖北鄂州高中素质班自主招生数学试题-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不等式、解...

【精选】沪教版数学二年级上册总复习题-数学

【精选】沪教版数学二年级上册总复习题-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不等式、解三角...

【精选】春北师大版数学二下《分草莓》word拔高练习-数学

【精选】春北师大版数学二下《分草莓》word拔高练习-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不...

【精选】冀教版小学数学四年级上册全册教案-数学

【精选】冀教版小学数学四年级上册全册教案-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不等式、解...

【精选】北师大版必修5高中数学第三章《基本不等式》wo...

【精选】北师大版必修5高中数学第三章《基本不等式》word典型例题素材-数学知识点总结 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数...

【精选】沪教版三年下《整体与部分》word教案-数学

【精选】沪教版三年下《整体与部分》word教案-数学 - 数学、高中数学、数学课件、数学教案、数学试题、试卷数学、数学考试、奥数、集合、有理数、函数、不等式、...