数学奥赛辅导 第六讲 集合与映射
知识、方法、技能
这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识
Ⅰ.有限集元素的数目 1．有限集的阶
有限集A 的元素数目叫做这个集合的阶，记作|A|[或n(A)]. 2．集族的阶
若M 为由一些给定的集合构成的集合，则称集合M 为集族. 设A 为有限集，由A 的若干个子集构成的集合称为集合A 的一个子集族，求满足一定条件的集族的阶是一类常见的问题.
显然，若|A|=n ，则由A 的所有子集构成的子集族的阶为2n . Ⅱ.映射，映射法
定义1 设X 和Y 是两个集合（二者可以相同）.如果对于每个X x ∈，都有惟一确定的Y y ∈与之对应，则称这个对应关系为X 到Y 的映射.记为
.Y y X x Y X ∈→∈→或这时,Y x f y ∈=)(称为X x ∈的象,而x 称为y 的原象,特
别当X 和Y 都是数集时，映射f 称为函数.
定义2 设f 为从X 到Y 的一个映射.
(1)如果对于任何x 1、.),()(,,21212为单射则称都有f x f x f x x X x ≠≠∈ （2）如果对于任何Y y ∈，都有X x ∈，使得f (x )=y ，则称f 为满射; （3）如果映射f 既为单射又为满射，则称f 为双射；
（4）如果f 为满射且对任何Y y ∈，恰有X 中的m 个元素x 1、x 2、…
x m ，使得
.)(,,,2,1,)(倍数映射的倍数为为则称m f m i y x f i ==
定理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 设有限集f a a a A n },,,,{21 =是A 到A 上的映射，),()(1x f x f =
),,)](([)(1*+∈∈=N r A x x f f x f r r 则f 是一一映射（即双射）的充要条件是：
对任意
).11,()(,)(1,,-≤≤∈≠=≤≤∈∈**i i i s i i m i i i m s N s a a f a a f n m N m A a i 而使得存在
证明：必要性.若f 是双射，则i i a a f ==)(1（此时m i =1）,或者.)(11i i i a a a f ≠=在后一种情形下，不可能有.)()(1
1
12i i i a a f a f ==否则，a i 1在A 中有两个原象
a i
和
a i 1，与
f 是双射不合，而只可能有
2222)(,,)(),2()(12i i i i i i i i i a a f a a a a f m a a f =≠===如果或者此时，则依同样的道理，
不可能有或者此时而只可能有),3()(,,)()(332
1
2
====i i i i i i i m a a f a a a f a f
213,,)(3i i i i i a a a a a f ≠=.如此等等.
因为A 是有限集，所以经过有限次（设经过m 次）后，有
i s i i m a ai f a a f i ≠=)(,)(而 ).11,(-≤≤∈*i m s N s
这表明当f 是双射时，对任一A a i ∈都存在着映射圈:
i im i i i a a a a a i →→→→-121
在这个映射圈中，诸元素互异，且),1(1i i i a m n m 只有一个元素=≤≤ 充分性.如果对任意i i s i i mi i i i a a f a a f n m N m A a ≠=≤≤∈∈*)(,)(,1,,而使存在
)1,(1-*≤≤∈i m s N s ，这说明从A 中任一元素a i 出发，都可以得到一个
包含m i 个互异元素的映射圈，显然f 是双射.
定理3 在命题1的条件下，若对i i mi i i a a f N m A a =∈∈*)(,,使存在，则对任意
.)(,i i tm a a f N t i =∈*有
这是明显的事实，证明从略. 赛题精讲
例1：设集合,30001|{},,14,20001|{≤≤=∈+=≤≤=y y B Z k k x x x A 集合
||},,13B A Z k k y ?∈-=求.
【解】形如4k +1的数的数可分三类：
)(912,512,112Z l l l l ∈+++，其中只有形如12l +5的数是形如3k -1的数.
.
167||},1997,,17,5{,1660),
(20005121=?=?≤≤∈≤+≤B A B A l Z l l 所以所以得令
例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中的任一个集合，且B a ?，由题设B 和A ，A 1，A 2，…，A 45都有一个公共元素，且此46个元素各不相同，故B 中有46个元素，与题设矛盾，所以这1987个集合中均含有a .
故所求结果为1987×44+1=87429.即这1987个集合的并集有87429个元素.
例3：集合n B B B A ,,,},9,2,1,0{21 =为A 的非空子集族，并且当
,2||≤?≠j i B B j i 时
求n 的最大值.
【解】首先考虑至多含三个元素的A 的非空子集族，它们共有
1753
10210110=++C C C 个，这说明.175max ≥n
下证，.175max ≤n 事实上，设D 为满足题设的子集族，若
,,4||,B b B D B ∈≥∈设且
则B 与B-{b}不能同时含于D ，以B-{b}代B ，则D 中元素数目不变.仿此对D 中所有元素数目多于4的集合B 作相应替代后，集族D 中的每个集合都是元素数目不多于3的非空集合，故.175max ≤n .
所以，.175max =n
在许多问题中，计数对象的特征不明显或混乱复杂难以直接计数，这时可以通过适当的映射将问题划归为容易计数的对象，然后再解决，从而
取得化难为易的效果.
例4：设},,,2,1{n S =A 为至少含有两项的公差为正的等差数列，其项都在S 中且当将S 的其他元素置于A 中之后，均不能构成与A 有相同公差的等差数列.求这种A 的个数（只有两项的数列也视为等差数列） 【解】当k n 2=为偶数时，满足题中要求的每个数列A 中必有连续两项，使其前一项在集{1,2,…,k}和{k +1,k +2,…,2k }中各任取一数，并以二数之差作为公差可以作出一个满足要求的数列A.容易看出，这个对应是双射.故
知A 的个数为.4
22
n k =
当n =2k +1为奇数时，情况完全类似.惟一的不同在于这时第二个集合
},2,1{n k k ++
有k +1个元素.故A 的个数为.4/)1()1(2-=+n k k
例5：设a n 为下述自然数N 的个数：N 的各位数字之和为n 且每位数字都只能取1、3或4.求证对每个自然数n ，a 2n 都是完全平方数.
【证明】记各位数字之和为n 且每位数字都是1或2的所有自然数的集合为S n ，并记
,3,2,1,||2121--+=≥===n n n n n f f f n f f f S 时有且当则这意味着{f n }恰为菲波那契
数列.
作对应'1M M S n →?如下：先将M 的数字中自左至右的第一个2与它后邻的数字相加，其和作为一位数字；然后再把余下数字中第一个2与它后邻的数字相加，所得的和作为下一位数字；依此类推，直到无数再相加
为止.所得的新自然数M′除最后一位数可能为2之外，其余各位数字均为1、3或4.若记所有M ′的集合为T n ，则容易看出，上述对应是由S n 到T n 的双射，从而有n n n f S T ==||||，且显然有
,4,3,2=+=-n a a f n n n ①
对于任一数字和为2n ，各位数字均为1或2的自然数M ，必存在正整数k ，使得下列两条之一成立：
（1）M 的前k 位数字之和为n ;
（2）M 的前k 位数字之和为n -1，第k +1位数字为2. 则立即可得 ,3,2,2122=+=-n f f f n n n ② 由①和②得到
,2
122222--+==+n n n n n f f f a a
),(1
2
2222----=-n n n
n f
a f
a ③
因为.0,2,4,2,12242432=-====f a f a a a 所以于是由③递推即得
,,3,2,1,2
2 ==n f a n n
即n a 2为完全平方数.
应用映射还可以证明某些与计数相关的不等式和等式.这时可以通过分别计数来证明等或不等，也可以不计数而直接通过适当的映射来解决问题.
例6：将正整数n 写成若干个1和若干个2之和，和项顺序不同认为是不同的写法，所有写法种数记为a (n ).将n 写成若干个大于1的正整数之和，和项顺序不同认为是不同的写法，所有写法的种数记为)(n β.求证对每个n ，都有).2()(+=n n βα
【证法1】将每项都是1或2，各项之和为n 的所有数列的集合记为A n ，每项都是大于1的正整数，各项之和为n 的所有数列的集合记为B n ，则问题就是证明|,|||2+=n n B A
显然，只需在两集之间建立一个双射就行了.
i k ik i i n m a m i i i a a a A a a a a 其余的其中设,1,2,),,,(212121≤<<≤≤====∈= 均
为1且令.21n a a a m =+++
1211i a a a b +++= ，
,
22112122121121+++++++++++=+++=+++=--m i i k ik i i k i i i a a a b a a a b a a a b k k k k
),,,,,(121+=k k b b b b b
①
则定义.2+∈n B b
2+∈→?n n B b a A
②
则f 为双射.事实上，若a a A a a n '≠∈'且,,，则或者数列a 和a ′中的2的个数不同，或者2的个数相同但位置不全相同.无论哪种情形,由①和②知
f a f b a f b 即不同与,)()('='=为单射，另一方面，对任何2+∈n B b 利用①式又可
确定,n A a ∈使得,,)(为满射即f b a f =从而f 为由A n 到B n +2的双射. 【证法
2】使用证一中的记号.n n B A 和对于任意的
令,),,,,(2121+-∈=n m m A a a a a a
,,2;,1,).,,,(11121A a a A a a a a a a m n m m ∈'=∈'=='+-时当时当显然 容易看出，映射 n n n A A a af A ?∈'→?++12
是双射，故有).()1()2(n n n ααα++=+注意到2)2(,1)1(==αα，便知
,)(n f n =α这里|f n |为菲波那契数列.
对于任意的令2121),,,,(+-∈=n k k B b b b b b
??
?>-=='--2
)
1,,,,(2),,,(121121k k k k k b b b b b b b b b b 当当
则当,,,2;,2,21容易验证时当时时+∈'>∈'='=n k n k B b b B b b b 映射
n n n B B b b B ?∈'→?++12
为双射，故有),()1()2(n n n βββ++=+
==+n f n )2(β所以a (n )
【证法3】显然有),4(2)2(),3(1)1(βαβα===即命题于n =1,2时成立. 设命题于,.2,)1(1k n k n k k n =+=≥+≤既然命题于时命题成立须证当时成立
令与之间的双射与与故存在时都成立.,,11312+++++f k k k k n f f B A B A k
??
?>∈=+2
),
()()(1k k k k b a f A a a f a f 当当
则f 为由.321的双射到+++??n n k k B B A A
对于任意的令和任意,),,,(),,,,(32212121+++-?∈'=∈=k k l k m m B B b b b b A a a a a a
???==∈='+-,1,,
2,),,,(1121m k m k m a A a A a a a a 当当
???∈'∈+∈'∈=++++.
,)1,,,)2,,,(34212421k k l k k l B b B b b b B b B b b b b 当当 4
3212:.
:+++++∈→'???∈'→?k k k k k k B b b B B h A A a a A g 则映射
都是双射，从而复合映射
42:++∈→?k k B b a A g f h
为双射，故有)4()2(+=+k k βα，于是由数学归纳法知命题对所有自然数n 都成立.
映射法还可以与其他方法结合起来使用，而且大多数竞赛题是这种类型.例如映射法可与抽屉原理、构造法、反证法等各种方法结合起来. 例7：设oxyz 是空间直角坐标系，S 是空间中的一个有限点集，S x ，S y ，S z 分别是S 中所有点的坐标平面oyz ，ozx ，oxy 上的正投影所成的集合.求证
.||||||||2z y x S S S S ??≤（1992年IMO 试题5）
【证明】对每点令,),(x S j i ∈
∑∈=
∈=ix
S j i ij
ij T
S S j i x j i x T ),(}},,(|),,{(显然有
由柯西不等式有
2),(2),(),(2||||||1||ij S j i x ij
S j i S j i T S T
S x
x
x
∑
∑∑
∈∈∈?
=??
≤
①
考虑集合},,|),{(),(2121),(ij ij ij ij ij S j i T t t t t T T T T V x
∈=??=∑
∈其中
显然，|V|=
2),(||ij S j i T x
∑
∈
定义映射f 如下
z y S S i x j x j i x j i x V ?∈'→'?)),(),,((),,(),,,(，不难看出f 为单射，因此有
||||||z y S S V ?≤
由①、②即得||||||||2z y x S S S S ??≤.
例8：设集合},10,,2,1{ =A A 到A 的映射f 满足下列两个条件：
①对任意;)(,30x x f A x =∈
②对每个.)(,,291,a a f A a k Z k k ≠∈≤≤∈+使得至少存在一个
求这样的映射的总数. (1992年日本奥林匹克预选赛题)
【解】注意到10=5+3+2，30=5×3×2.这提示我们将A 划分成三个不相交的子集
},{},,{},,,,{2132154321c c b b b a a a a a A ??=.
因为f 满足条件①和②，所以f 是A 到A 上的双射，并且由定理2的证明过程得知A 中存在映射圈，因此，定义映射
,)(,)(;)(,)(,)(,)(,)(:32211554433221b b f b b f a a f a a f a a f a a f a a f f ======= .)(,)(;)(122113c c f c c f b b f ===
因为30是5、3、2的最小公倍数，故由定理2和定理3知f 是满足题目条件①和②惟一的一类映射.
因此，f 的总数目相当于从10个元素中选取5个，再从剩下的5个中选取3个，最后剩下的两个也选上，它们分别作圆排列的数目，它等于
.120960)!1)(!2)(!4(2
235510=???C C C
例9：设集合A={1，2，3，4，5，6}，映射A A f →:,其三次复合映射f ·f ·f 是恒等映射，这样的f 有多少个？ （1996年日本数学奥林匹克预选赛题）
【解】因为集合A 上的三次复合映射是恒等映射，所以定理2和定理3推知符合条件的映射f 有三类： （1）f 是恒等映射；
（2）A 中存在一个三元映射圈),,(互异c b a a c b a →→→，而其他三个元素是不动点； （
3
）
A
中
存
在
两
个
三
元
映
射
圈
).,,,,,(互异和c b a c b a a c b a a c b a ''''→'→'→'→→→
类型（1）的f 只有1个.
对于类型（2），先从6个元素中选出3个元素20,,36=C c b a 的方法有种，又a 、b 、c 作圆排列有（3—1）！=2种，故这样的f 有20×2=40个. 对于类型（3），首先6个元素平分成两组有10236=÷C 种分法，每组分别作圆排列又有（3—1）！（3—1）！=4种方式，所以这样的f 有10×4=40个.
综上所述，所求的f 有 1+40+40=81个.
例10：把正三角形ABC 的各边n 等分，过各分点在△ABC 内作各边的平行线，得到的图形叫做正三角形ABC 的n 格点阵. （1）求其中所有边长为||1
BC n
的菱形个数；
（2）求其中所有平行四边形的个数. （1988年国家集训队选拔考试题）
【解】延长AB 至.||1||||,,BC n
C C B B C AC B ='='''使得至作出正三角形C B A ''的n+1格点阵（图I —3—1—1）.边2+''n C B 上有个点，依次编码为0，1，2，…，n+1.
在△ABC 中边长为n
1|BC|的菱形可以按边不平 行于BC 、AC 与AB 分为三类.容易看出，这三类
中菱形个数相同.边不平行BC 且边长为n
1|BC|的 所有菱形集合记作S.由正整数1，2，…，n 组成 的所有有序的数对（i ,j ）,i .),(,1,T j i n j i j i C B ∈≤<≤''则与于点令 （i ,j ）是菱形EFGH 在S 到T 的映射?下的像，这样便建立了S 到T 的映射?.容易验证，映射?是双射.因此，,||||2n C T S ==所以所求的边长为 n 1 |BC|的菱长个数为32n C . 其次，将平行四边形按边不平行于BC 、AC 与AB 分为三类，这三类的平行四边形个数应相同，边不平行BC 的所有平行四边形集合记作V .非负整数 0,1,2,…,n+1 构成的所有有序四元数组 （i ,j ,k ,l ）,10+≤<<<≤n l k j i 构成的集合记作W.很明显，42||+=n C W .设α是V 中平行的四边形，延长它的四条边分别交l k j i C B ,,,于点''，其中 10+≤<<<≤n l k j i ， 则?αββ的映射到在是令W V W l k j i .),,,(∈=下的像.这样便定义了V 到W 的一个映射?.容易验证，?是双射.因此，.||||42+==n C W V 从而所求平行四边形的个数为423+n C .
相关主题
文本预览