数学奥赛辅导 第六讲 集合与映射知识、方法、技能这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识Ⅰ.有限集元素的数目 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 ≠=在后一种情形下，不可能有.)()(1112i 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()(,,)()(33212====i i i i i i i m a a f a a a f a f213,,)(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 m i 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 m i 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 的非空子集族，它们共有175310210110=++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 的个数为.422n 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 ② 由①和②得到,2122222--+==+n n n n n f f f a a),(122222----=-n n n n f a f a ③因为.0,2,4,2,12242432=-====f a f a a a 所以于是由③递推即得,,3,2,1,22 ==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 b2+∈→∍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 当当 43212:.:+++++∈→'∍⋃⋃∈'→∍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 ∈∑∈=∈=ixS j i ijij TS S j i x j i x T ),(}},,(|),,{(显然有由柯西不等式有2),(2),(),(2||||||1||ij S j i x ijS j i S j i T S TS xxx∑∑∑∈∈∈⋅=⋅⋅≤①考虑集合},,|),{(),(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(2235510=⋅⋅⋅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）求其中所有边长为||1BC n的菱形个数； （2）求其中所有平行四边形的个数. （1988年国家集训队选拔考试题） 【解】延长AB 至.||1||||,,BC nC 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 中边长为n1|BC|的菱形可以按边不平 行于BC 、AC 与AB 分为三类.容易看出，这三类 中菱形个数相同.边不平行BC 且边长为n1|BC|的 所有菱形集合记作S.由正整数1，2，…，n 组成 的所有有序的数对（i ,j ）,i <j 所构成的集合记作T.很明显，,||2n C T =设菱形EFGH ∈S ，延长它的两条邻边HG 与GF ，分别交.),(,1,T j i n j i j i C B ∈≤<≤''则与于点令（i ,j ）是菱形EFGH 在S 到T 的映射ϕ下的像，这样便建立了S 到T 的映射ϕ.容易验证，映射ϕ是双射.因此，,||||2n C T S ==所以所求的边长为n1|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 .。
