关键词不能为空

当前您在: 主页 > 数学 >

高中数学奥赛辅导 第六讲 集合与映射

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2020-09-14 20:20
tags:高中数学补习

高中数学总是计算总是粗心-高中数学知识点全总结下载



数学奥赛辅导 第六讲 集合与映射
知识、方法、技能
这一讲主 要介绍有限集的阶,有限集上的映射及其性质,这些在与计数有关的数学竞赛问题
中应用极广,是参赛者 必不可少的知识
Ⅰ.有限集元素的数目
1.有限集的阶
有限集A的元素数目叫做这个集合的阶,记作|A|[或n(A)].
2.集族的阶
若M为由一些给定的集合构成的集合,则称集合M为集族.
设A为有限集,由A的若干个子集 构成的集合称为集合A的一个子集族,求满足一定条件
的集族的阶是一类常见的问题.
显然,若|A|=n,则由A的所有子集构成的子集族的阶为2
n
.
Ⅱ.映射,映射法
定义1 设X和Y是两个集合(二者可以相同).如果对于每个
x?X
,都有惟一确定的
y?Y
与之对应,则称这个对应关系为X到Y的映射.记为< br>X?Y或x?X?y?Y.

时,
y?f(x)?Y
称为
x? X
的象,而x称为y的原象,特别当X和Y都是数集时,映射f称为函数.
定义2 设f为从X到Y的一个映射.
(1)如果对于任何x
1

x
2?X,x
1
?x
2
,都有f(x
1
)?f(x
2
),则称f为单射.

(2)如果对于任何
y?Y
,都有
x?X
,使得f(x)=y,则称f为满射;
(3)如果映射f既为单射又为满射,则称f为双射;
(4)如果f为满射且对任何
y?Y
,恰有X中的m个元素x
1
、x
2
、…x
m
,使得
f(x
i
)
?
y,i
?
1,2,
?
,m,则称f为(倍数为m的)倍数映射.

定理1 设X和Y都是有限集,f为从X到Y的一个映射,
(1)如果f为单射,则|X|≤|Y|
(2)如果f为满射,则|X|≥|Y|
(3)如果f为双射,则|X|=|Y|
(4)如果f为倍数为m的倍数映射,则|X|=m|Y|.
这个定理的结果是显然的.
定理2 设有限集
A
?
{a
1
,a
2
,
?
,a
n
},f
是A到A上的映射,
f
1
(
x
)
?f
(
x
),

f
r?1
(x)?f[f
r
(x)](x?A,r?N
?
),
则f是 一一映射(即双射)的充要条件是:对任意
a
i
?A,存在m
i
?N
?
,1?m
i
?n使得f
m
i
(a
i)?a
i
,而f
s
(a
i
)?a
i
( s?N
?
,1?s?m
i
?1).

证明:必要性.若f是 双射,则
f
1
?(a
i
)?a
i
(此时m
i
=1),或者
f
1
(a
i
)?a
i1
? a
i
.
在后一种情形



下,不可能有f
2
(a
i
)?f
1
(a
i
1
)?a
i
1
.
否则,a
i1
在A中有两个原象a
i
和a
i1
,与f是双射不合,而
只可能有
f
2
( a
i
)?a
i
(此时m
i
?2),或者f
2
(a
i
)?a
i
2
?a
i
,a
i
1
,如果f
2
(a
i
)?a
i2
,则依同样的道
理,不可能有
f
3
(a
i
)?f(a
i
2
)?a
i
1
,a
i
2
,而只可能有f
3< br>(a
i
)?a
i
(此时m
i
?3),或者

f
3
(a
i
)?a
i
3
?a
i< br>,a
i
1
,a
i
2
.如此等等.
因为A是 有限集,所以经过有限次(设经过m次)后,有
f
m
i
(a
i
)?a
i
,而f
s
(ai)?a
i

(s?N
?
,1?s?m
i
?1).

这表明当f是双射时,对任一
a
i
?A
都存在着映射圈:
a
i
?a
i1
?a
i2
?
?
a
i m
i
?1
?a
i

在这个映射圈中,诸元素互异,且
1?m
i
?n(m
i
?1,只有一个元素a
i
)

充分性.如果对任意
a
i
?A,存在m
i
?N
?< br>,1?m
i
?n,使f
mi
(a
i
)?a
i
,而f
s
(a
i
)?a
i

(s?N?
,1?s?m
i?1
)
,这说明从A中任一元素a
i
出发,都可以得到一个包含m
i
个互异元素
的映射圈,显然f是双射.
定理3 在命题1的条件下,若对
a
i
?A,存在m
i
? N
?
,使f
mi
(a
i
)?a
i
,则对任 意
t?N
?
,有f
tm
i
(a
i
)?a
i
.

这是明显的事实,证明从略.

赛题精讲
例1:设集合
A?{x|1?x?2000,x?4k?1,k?Z},集合B?{y|1?y?30 00,

y?3k?1,k?Z},求|A?B|
.
【解】形如4k+1的数的数可分三类:
12l?1,12l?5,12l?9(l?Z)< br>,其中只有形如12l+5的数是形如3k-1的数.
令1?12l?5?2000(l?Z) ,
得0?l?166,所以A?B?{5,17,
?
,1997},所以|A?B|? 167.

例2:有1987个集合,每个集合有45个元素,任意两个集合的并集有89个元 素,问此1987个
集合的并集有多少个元素.
【解】显然,可以由题设找到这样的1987 个集合,它们都含有一个公共元素a,而且每两个集合



不含a以外的公共元素.但是,是否仅这一种可能性呢?
由任意两个集合的并集有89个元素 可知,1987个集合中的任意两个集合有且仅有一个公共
元素,则容易证明这1987个集合中必有一 个集合中的元素a出现在A以外的45个集合中,设为
A
1
,A
2
, …,A
45
,其余的设为A
46
,A
47
,…,A
1996
.
设B为A
46
,…,A
1996
中的任一个集 合,且
a?B
,由题设B和A,A
1
,A
2
,…,A
45
都有
一个公共元素,且此46个元素各不相同,故B中有46个元素,与题设矛盾,所以 这1987个集
合中均含有a.
故所求结果为1987×44+1=87429.即这1987个集合的并集有87429个元素. < br>例3:集合
A
?
{0,1,2
?
,9},B
1
,B
2
,
?
,B
n
为A的非空子集族,并且当
i
?
j时
|
B
i
?
B
j
|?2,< br>
求n的最大值.
123
【解】首先考虑至多含三个元素的A的非空子集族, 它们共有
C
10
?C
10
?C
10
?175
个,这说明
n
max
?175.

下证,
n
ma x
?175.
事实上,设D为满足题设的子集族,若
B?D,且|B|?4,设b?B ,

则B与B-{b}不能同时含于D,以B-{b}代B,则D中元素数目不变.仿此对D中 所有元素数
目多于4的集合B作相应替代后,集族D中的每个集合都是元素数目不多于3的非空集合,故
n
max
?175.
.
所以,
n
max
?175.

在许多问题中,计数对象的特 征不明显或混乱复杂难以直接计数,这时可以通过适当的映射
将问题划归为容易计数的对象,然后再解决 ,从而取得化难为易的效果.
例4:设
S?{1,2,?,n},
A为至少含有两项 的公差为正的等差数列,其项都在S中且当将S的其
他元素置于A中之后,均不能构成与A有相同公差的 等差数列.求这种A的个数(只有两项的数
列也视为等差数列)
【解】当
n?2k< br>为偶数时,满足题中要求的每个数列A中必有连续两项,使其前一项在集{1,2,…,k}
和{ k+1,k+2,…,2k}中各任取一数,并以二数之差作为公差可以作出一个满足要求的数列A.容易看n
2
.
出,这个对应是双射.故知A的个数为
k?
4
2
当n=2k+1为奇数时,情况完全类似.惟一的不同在于这时第二个集合
{k?1,k?2 ,?n}

有k+1个元素.故A的个数为
k(k?1)?(n?1)4.


例5:设a
n
为下述自然数N的个数:N的各位数字之和为n且每位数字都 只能取1、3或4.求证
对每个自然数n,a
2n
都是完全平方数.
【证明】记各位数字之和为n且每位数字都是1或2的所有自然数的集合为S
n
,并记
2
|S
n
|?f
n
,则f
1
?1,f2
?2,且当n?3时有f
n
?f
n?1
?f
n?2< br>,
这意味着{f
n
}恰为菲波那契数列.



作对应
S
n
?M
1
?M'
如下:先将M的数字中自 左至右的第一个2与它后邻的数字相加,
其和作为一位数字;然后再把余下数字中第一个2与它后邻的数 字相加,所得的和作为下一位数
字;依此类推,直到无数再相加为止.所得的新自然数M′除最后一位数 可能为2之外,其余各位
数字均为1、3或4.若记所有M′的集合为T
n
,则容易看 出,上述对应是由S
n
到T
n
的双射,从而

|T
n
|?|S
n
|?f
n
,且显然有
f
n
?a
n
?a
n?2
,
n?
3,4,?

对于任一数字和为2n,各位数字均为1或2的自然数M,必存在正整数k,使得下列两条之
一成立:
(1)M的前k位数字之和为n;
(2)M的前k位数字之和为n-1,第k+1位数字为2.
则立即可得
f
2n
?f
n
?f
n?1
,n?2,3,?

由①和②得到
2
a
2n
?a
2n?2
?f
2n
?f
n
2
?f
n?1
,

22a
2n
?f
2
n
??(a
2n?2
?f
2
n?1
),

因为
a
2
?1,a
3
?2,a
4
?4,f
2
?2,所以a
4
?f
2
2
?0.
于是由③递推即得
a
2n
?f
n< br>,
n?
1,2,3,
?
,


a
2n
为完全平方数.
应用映射还可以证明某些与计数相关的不 等式和等式.这时可以通过分别计数来证明等或不
等,也可以不计数而直接通过适当的映射来解决问题.
例6:将正整数n写成若干个1和若干个2之和,和项顺序不同认为是不同的写法,所有写法种
数记为a(n).将n写成若干个大于1的正整数之和,和项顺序不同认为是不同的写法,所有写法的
种 数记为
?
(n)
.求证对每个n,都有
?
(n)?
?
(n?2).

【证法1】将每项都是1或2,各项之和为n的所有数列的集合记为A
n
,每项都是大于1的
正整数,各项之和为n的所有数列的集合记为B
n
, 则问题就是证明
|A
n
|?|B
n?2
|,

显然,只需在两集之间建立一个双射就行了.
2
设(a
1
,a2
,?,a
m
)?a?A
n
,其中a
i1
?a
i2
???a
ik
?2,1?i
1
?i
2
???i
k
?m,其余的a
i

为1且
a
1
?a
2
???a
m
?n.令

b
1
?a
1
?a
2
???a
i
1



b
2
?a
i
1
?1
?a
i
2
?2
?
?
?a
i2
?
b
k
?a
i
k?1
?1
?a
i
k?1
?2
?
?
?a
ik
b
k?1
?a
i
k
?1
?a
i
k
?2
?
?
?a
m?2,
b?(b
1
,b
2
,?,b
k
, b
k?1
),


b?B
n?2
.定义


A
n
?a?b?B
n?2

则f为双射. 事实上,若
a,a
?
?A
n
,且a?a
?
,则或者 数列a和a′中的2的个数不同,或者2的个
数相同但位置不全相同.无论哪种情形,由①和②知
b?f(a)与b
?
?f(a
?
)不同,即f
为单射,另一
方面,对任何
b?B
n?2
利用①式又可确定
a?A
n
,
使得
f(a)?b,即f为满射,
从而f为由A
n
到B
n+ 2
的双射.
【证法2】使用证一中的记号
A
n
和B
n.
对于任意的
(a
1
,a
2
,?,a
m?1< br>,a
m
)?a?A
n?2
,令

a
?
?(a
1
,a
2
,?,a
m?1
).显然,当a
m
?1时,a
?
?A
n?1
;当a
m
?2时,a< br>?
?A
1
,
容易看出,映射
A
n?2
?a f?a
?
?A
n?1
?A
n

是双射,故有
?
(n?2)?
?
(n?1)?
?
(n).
注意到
?
(1)?1,
?
(2)?2
,便知
?
(n)?f
n
,
这里|f
n
|
为菲波那契数列.

对于任 意的
(b
1
,b
2
,?,b
k?1
,b
k
)?b?B
n?2


?
(b
1
,b2
,
?
,b
k?1
)
b
?
?
?
?
(b
1
,b
2
,
?
,b
k? 1
,b
k
?1)
当b
k
?2
当b
k
?2

则当
b
k
?2时,b
?
?2时,b
?
?B
n
;当b
k
?2时,b
?
?B
n ?1
,容易验证,
映射
B
n?2
?b?b
?
?B
n?1
?B
n

为双射,故有
?
(n?2)??
(n?1)?
?
(n),

所以
?
(n?2)?f
n
?
a(n)
【证法3】 显然有
?
(1)?1
?
(3),
?
(2)?2?
?
(4),
即命题于n=1,2时成立.



设命题 于
n?k?1(k?1)时成立,须证当n?k?2时命题成立.既然命题于n?k,

k?1时都成立,故存在A
n
与B
k?2
,A
k?1
与B
k?3
之间的双射f
k
与f
f?1
.令

?
f
k
(a)
f(a)?
?
?
f
k?1< br>(a),
当a?A
k
当b
k
?2

则f为由
A
k
?A
k?1
到B
n?2
?B
n?3< br>的双射.

对于任意的
(a
1
,a
2
,?, a
m?1
,a
m
)?a?A
k?2
和任意(b
1< br>,b
2
,?,b
l
)?b
?
?B
k?2?B
k?3
,令

?
A
k
,当a
m
?2,

a
?< br>?(a
1
,a
2
,
?
,a
m?1
) ?
?
?
A
k?1
,当a
m
?1,
?
(b
1
,b
2
,
?
b
l
,2)?Bk?4
,当b
?
?B
k?2

b?
?
?
b
1
,b
2
,
?
b
l
?1)? B
k?4
,当b
?
?B
k?3
.
则映射g:Ak?2
?a?a
?
?A
k
?A
k?1
.

?
h:B
k?2
?B
k?3
?b?b?B
k? 4
都是双射,从而复合映射
h?f?g:A
k?2
?a?b?B
k?4

为双射,故有
?
(k?2)?
?
(k?4)
,于是由数学归纳法知命题对所有自然 数n都成立.
映射法还可以与其他方法结合起来使用,而且大多数竞赛题是这种类型.例如映射法可与 抽屉
原理、构造法、反证法等各种方法结合起来.
例7:设oxyz是空间直角坐标系,S是 空间中的一个有限点集,S
x
,S
y
,S
z
分别是S中所有 点的坐
标平面oyz,ozx,oxy上的正投影所成的集合.求证
|S|
2
?|S
x
|?|S
y
|?|S
z
|.
(1992 年IMO试题5)
【证明】对每点
(i,j)?S
x
,令

T
ij
?{(x,i,j)|(x,i,j}?S}
显然有S?
(i,j) ?S
ix
?
T
ij

由柯西不等式有


|S|
2
?
(i,j)?S
x
?
?
(i, j)?S
x
?
1?|T
ij
|
2
?|S
x
|?
(i,j)?S
x
?
|T
ij
|
2< br> ①



考虑集合
V?显然,|V|=
(i,j)?S
x
?
(T
ij
?Tij
),其中T
ij
?T
ij
?{(t
1
,t
2
)|t
1
,t
2
?T
ij
},

(i,j)?S
x
?
|T
ij
|
2

定义映射f如下
V?(x,i,j),(x
?
,i,j)?((x,j), (x
?
,i))?S
y
?S
z
,不难看出f为单射,因此有
|V|?|S
y
|?|S
z
|

由①、②即得|S|
2
?|S
x
|?|S
y
|?|S
z|
.
例8:设集合
A?{1,2,?,10},
A到A的映射f满足下列两个条件:
①对任意
x?A,f
30
(x)?x;

②对每个
k?Z
?
,1?k?29,至少存在一个a?A,使得f
k
(a)?a.
求这样的映射的总数. (1992年日本奥林匹克预选赛题)
【解】注意到10=5+3+2,30=5×3×2.这提示我们将A划分成三个不相交的子集
A?{a
1
,a
2
,a
3
,a
4
,a< br>5
}?{b
1
,b
2
,b
3
}?{c
1
,c
2
}
.
因为f满足条件①和②,所以f是A到A上的双射 ,并且由定理2的证明过程得知A中存在
映射圈,因此,定义映射
f:f(a
1)?a
2
,f(a
2
)?a
3
,f(a
3)?a
4
,f(a
4
)?a
5
,f(a
5)?a
1
;f(b
1
)?b
2
,f(b
2)?b
3
,

f(b
3
)?b
1
;f (c
1
)?c
2
,f(c
2
)?c
1
.< br>
因为30是5、3、2的最小公倍数,故由定理2和定理3知f是满足题目条件①和②惟一的一
类映射.
因此,f的总数目相当于从10个元素中选取5个,再从剩下的5个中选取3个,最 后剩下的
两个也选上,它们分别作圆排列的数目,它等于
532
(C
10< br>?4!)(C
5
?2!)(C
2
?1!)?120960.

例9:设集合A={1,2,3,4,5,6},映射
f:A?A
,其三次复合映射f ·f·f是恒等映射,这
样的f有多少个? (1996年日本数学奥林匹克预选赛题)
【解】因为集合A上的三次复合映射是恒等映射,所以定理 2和定理3推知符合条件的映射f有
三类:
(1)f是恒等映射;
(2)A中存在 一个三元映射圈
a?b?c?a(a,b,c互异)
,而其他三个元素是不动点;
( 3)A中存在两个三元映射圈
a?b?c?a和a
?
?b
?
?c?
?a
?
(a,b,c,a
?
,b
?
,c?
互异).



类型(1)的f只有1个.
3
对于类型(2),先从6个元素中选出3个元素
a,b,c的方法有C
6< br>?20
种,又a、b、c作圆排列
有(3—1)!=2种,故这样的f有20×2=40 个.
3
对于类型(3),首先6个元素平分成两组有
C
6

?2?10
种分法,每组分别作圆排列又有(3—1)
(3—1)!=4种方式,所以这样的 f有10×4=40个.
综上所述,所求的f有
1+40+40=81个.
例1 0:把正三角形ABC的各边n等分,过各分点在△ABC内作各边的平行线,得到的图形叫做
正三角形 ABC的n格点阵.
(1)求其中所有边长为
1
|BC|
的菱形个数; < br>n
1
|BC|.
作出正三角形
AB
?
C
?< br>的n+1格点
n
(2)求其中所有平行四边形的个数. (1988年国家集训队选拔考试题)
【解】延长AB至
B
?
,AC至C< br>?
,使得|BB
?
|?|CC
?
|?
阵(图I—3— 1—1).边
B
?
C
?
上有n?2
个点,依次编码为0,1 ,2,…,n+1.
在△ABC中边长为
1
|BC|的菱形可以按边不平
n
1
|BC|的
n
行于BC、AC与AB分为三类.容易看出,这三类
中菱形个数相同.边不平行BC且边长为
所有菱形集合记作S.由正整数1,2,…,n组成
的所有有序的数对(i,j),i2
很明显,
| T|?C
n
,
设菱形EFGH
?
S,延长
它的两条邻边HG与GF,分别交

(i,j)是菱形EFGH在S到T的映射?
下的像,这样便建立了S到T的映射
?
.容易验证,映射
?
2
是双射.因此,
|S|?|T|?C
n
,
所以所求的边长为
B
?
C
?
于点i与j,1?i?j?n,则(i,j)?T.

1
2
|BC|的菱长个数为3
C
n
.
n
其次,将平行四边形按边不平行于BC、AC与AB分为三类,这三类的平行四边形个数应相
同,边不平 行BC的所有平行四边形集合记作V.非负整数0,1,2,…,n+1构成的所有有序四元数组
4(i,j,k,l),
0?i?j?k?l?n?1
构成的集合记作W.很明显,
|W|?C
n?2
.设
?
是V中平行的四
边形,延长它的四条边分别 交
B
?
C
?
于点i,j,k,l
,其中
0?i?j ?k?l?n?1


?
?(i,j,k,l)?W.令
?

?
在V到W的映射
?
下的像.这样便定义了V到W的一个映射
?
.容
易验证,
?
是双射.因此,
|V|?|W|?C
n?2
.
从而所求平行四边形的个数为
3C
n?2
.

44




高中数学必修2pdf下载-江苏凤凰教育出版社高中数学教材


命题 高中数学-高中数学老师近期表现


高中数学难题库及答案-找规律的高中数学题


高中数学三维向量计算方法-人教版高中数学必修5答案


高中数学必修2同步辅导材料-2018高中数学竞赛答案解析


高中数学4_2-高中数学小课题研究方向


高中数学三角函数化简题目-高中数学教师资格面试视频


高中数学题网-高中数学垂直教案



本文更新与2020-09-14 20:20,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/395003.html

高中数学奥赛辅导 第六讲 集合与映射的相关文章