高中数学总是计算总是粗心-高中数学知识点全总结下载
数学奥赛辅导 第六讲 集合与映射
知识、方法、技能
这一讲主
要介绍有限集的阶,有限集上的映射及其性质,这些在与计数有关的数学竞赛问题
中应用极广,是参赛者
必不可少的知识
Ⅰ.有限集元素的数目
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),i
很明显,
|
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