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

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

知识、方法、技能

这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识

Ⅰ.有限集元素的数目 1．有限集的阶

有限集A的元素数目叫做这个集合的阶，记作|A|[或n(A)]. 2．集族的阶

若M为由一些给定的集合构成的集合，则称集合M为集族.

设A为有限集，由A的若干个子集构成的集合称为集合A的一个子集族，求满足一定条件的集族的阶是一类常见的问题.

显然，若|A|=n，则由A的所有子集构成的子集族的阶为2n. Ⅱ.映射，映射法

定义1 设X和Y是两个集合（二者可以相同）.如果对于每个x X，都有惟一确定的y Y与之对应，则称这个对应关系为X到Y的映射.记为X Y或x X y Y.这时,y f(x) Y称为x X的象,而x称为y的原象,特别当X和Y都是数集时，映射f称为函数.

定义2 设f为从X到Y的一个映射.

(1)如果对于任何x1、x2 X,x1 x2,都有f(x1) f(x2),则称f为单射. （2）如果对于任何y Y，都有x X，使得f(x)=y，则称f为满射; （3）如果映射f既为单射又为满射，则称f为双射；

（4）如果f为满射且对任何y Y，恰有X中的m个元素x1、x2、…xm，使得

f(xi) 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 {a1,a2, ,an},f是A到A上的映射，f1(x) f(x),

fr 1(x) f[fr(x)](x A,r N ),则f是一一映射（即双射）的充要条件是：对任意

ai A,存在mi N ,1 mi n使得fmi(ai) ai,而fs(ai) ai(s N ,1 s mi 1).

证明：必要性.若f是双射，则f1 (ai) ai（此时mi=1）,或者f1(ai) ai1 ai.在后一种情形

下，不可能有f2(ai) f1(ai1) ai1.否则，ai1在A中有两个原象ai和ai1，与f是双射不合，而只可能有f2(ai) ai(此时mi 2),或者f2(ai) ai2 ai,ai1,如果f2(ai) ai2，则依同样的道理，不可能有f3(ai) f(ai2) ai1,ai2,而只可能有f3(ai) ai(此时mi 3),或者

f3(ai) ai3 ai,ai1,ai2.如此等等.

因为A是有限集，所以经过有限次（设经过m次）后，有fmi(ai) ai,而fs(ai) ai

(s N ,1 s mi 1).

这表明当f是双射时，对任一ai A都存在着映射圈:

ai ai1 ai2 aimi 1 ai

在这个映射圈中，诸元素互异，且1 mi n(mi 1,只有一个元素ai)

充分性.如果对任意ai A,存在mi N ,1 mi n,使fmi(ai) ai,而fs(ai) ai

(s N ,1 s mi 1)，这说明从A中任一元素ai出发，都可以得到一个包含mi个互异元素

的映射圈，显然f是双射.

定理3 在命题1的条件下，若对ai A,存在mi N ,使fmi(ai) ai，则对任意

t N ,有ftmi(ai) ai.

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

赛题精讲

例1：设集合A {x|1 x 2000,x 4k 1,k Z},集合B {y|1 y 3000,

y 3k 1,k Z},求|A B|.

【解】形如4k+1的数的数可分三类：

12l 1,12l 5,12l 9(l Z)，其中只有形如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个集合中，设为A1，A2，…，A45，其余的设为A46，A47，…，A1996.

设B为A46，…，A1996中的任一个集合，且a B，由题设B和A，A1，A2，…，A45都有一个公共元素，且此46个元素各不相同，故B中有46个元素，与题设矛盾，所以这1987个集合中均含有a.

故所求结果为1987×44+1=87429.即这1987个集合的并集有87429个元素. 例3：集合A {0,1,2 ,9},B1,B2, ,Bn为A的非空子集族，并且当i j时|Bi Bj| 2, 求n的最大值.

123

【解】首先考虑至多含三个元素的A的非空子集族，它们共有C10 C10 C10 175个，这说明

nmax 175.

下证，nmax 175.事实上，设D为满足题设的子集族，若B D,且|B| 4,设b B, 则B与B-{b}不能同时含于D，以B-{b}代B，则D中元素数目不变.仿此对D中所有元素数目多于4的集合B作相应替代后，集族D中的每个集合都是元素数目不多于3的非空集合，故

nmax 175..

所以，nmax 175.

在许多问题中，计数对象的特征不明显或混乱复杂难以直接计数，这时可以通过适当的映射将问题划归为容易计数的对象，然后再解决，从而取得化难为易的效果.

例4：设S {1,2, ,n},A为至少含有两项的公差为正的等差数列，其项都在S中且当将S的其他元素置于A中之后，均不能构成与A有相同公差的等差数列.求这种A的个数（只有两项的数列也视为等差数列） 【解】当n 2k为偶数时，满足题中要求的每个数列A中必有连续两项，使其前一项在集{1,2,…,k}和{k+1,k+2,…,2k}中各任取一数，并以二数之差作为公差可以作出一个满足要求的数列A.容易看

n2

. 出，这个对应是双射.故知A的个数为k 4

2

当n=2k+1为奇数时，情况完全类似.惟一的不同在于这时第二个集合{k 1,k 2, n} 有k+1个元素.故A的个数为k(k 1) (n 1)/4.

例5：设an为下述自然数N的个数：N的各位数字之和为n且每位数字都只能取1、3或4.求证对每个自然数n，a2n都是完全平方数.

【证明】记各位数字之和为n且每位数字都是1或2的所有自然数的集合为Sn，并记

2

|Sn| fn,则f1 1,f2 2,且当n 3时有fn fn 1 fn 2,这意味着{fn}恰为菲波那契数列.

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

fn an an 2,n 3,4, ①

对于任一数字和为2n，各位数字均为1或2的自然数M，必存在正整数k，使得下列两条之一成立：

（1）M的前k位数字之和为n;

（2）M的前k位数字之和为n-1，第k+1位数字为2.

则立即可得f2n fn fn 1,n 2,3, ② 由①和②得到

2

a2n a2n 2 f2n fn2 fn 1,

2

2

a2n f2n (a2n 2 f2n 1),③

因为a2 1,a3 2,a4 4,f2 2,所以a4 f22 0.于是由③递推即得

a2n fn,n 1,2,3, ,

即a2n为完全平方数.

应用映射还可以证明某些与计数相关的不等式和等式.这时可以通过分别计数来证明等或不等，也可以不计数而直接通过适当的映射来解决问题.

例6：将正整数n写成若干个1和若干个2之和，和项顺序不同认为是不同的写法，所有写法种数记为a(n).将n写成若干个大于1的正整数之和，和项顺序不同认为是不同的写法，所有写法的种数记为 (n).求证对每个n，都有 (n) (n 2).

【证法1】将每项都是1或2，各项之和为n的所有数列的集合记为An，每项都是大于1的正整数，各项之和为n的所有数列的集合记为Bn，则问题就是证明|An| |Bn 2|, 显然，只需在两集之间建立一个双射就行了.

2

设(a1,a2, ,am) a An,其中ai1 ai2 aik 2,1 i1 i2 ik m,其余的ai均

为1且a1 a2 am n.令

b1 a1 a2 ai1，

b2 ai1 1 ai2 2 ai2

bk aik 1 1 aik 1 2 aikbk 1 aik 1 aik 2 am 2,

b (b1,b2, ,bk,bk 1),

则b Bn 2.定义

①

An a b Bn 2

②

则f为双射.事实上，若a,a An,且a a ，则或者数列a和a′中的2的个数不同，或者2的个数相同但位置不全相同.无论哪种情形,由①和②知b f(a)与b f(a )不同,即f为单射，另一方面，对任何b Bn 2利用①式又可确定a An,使得f(a) b,即f为满射,从而f为由An到Bn+2的双射.

【证法2】使用证一中的记号An和Bn.对于任意的(a1,a2, ,am 1,am) a An 2,令

a (a1,a2, ,am 1).显然,当am 1时,a An 1;当am 2时,a A1,容易看出，映射 An 2 af a An 1 An

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

对于任意的(b1,b2, ,bk 1,bk) b Bn 2令

(b1,b2, ,bk 1)b

(b1,b2, ,bk 1,bk 1)

当bk 2当bk 2

则当bk 2时,b 2时,b Bn;当bk 2时,b Bn 1,容易验证,映射

Bn 2 b b Bn 1 Bn

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

所以 (n 2) fn a(n)

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