数学奥赛辅导讲集合与映射.docVIP

数学奥赛辅导 第六讲 集合与映射 知识、方法、技能 这一讲主要介绍有限集的阶，有限集上的映射及其性质，这些在与计数有关的数学竞赛问题中应用极广，是参赛者必不可少的知识 Ⅰ.有限集元素的数目 1．有限集的阶 有限集A的元素数目叫做这个集合的阶，记作|A|[或n(A)]. 2．集族的阶 若M为由一些给定的集合构成的集合，则称集合M为集族. 设A为有限集，由A的若干个子集构成的集合称为集合A的一个子集族，求满足一定条件的集族的阶是一类常见的问题. 显然，若|A|=n，则由A的所有子集构成的子集族的阶为2n. Ⅱ.映射，映射法 定义1 设X和Y是两个集合（二者可以相同）.如果对于每个，都有惟一确定的与之对应，则称这个对应关系为X到Y的映射.记为这时,称为的象,而x称为y的原象,特别当X和Y都是数集时，映射f称为函数. 定义2 设f为从X到Y的一个映射. (1)如果对于任何x1、 （2）如果对于任何，都有，使得f(x)=y，则称f为满射; （3）如果映射f既为单射又为满射，则称f为双射； （4）如果f为满射且对任何，恰有X中的m个元素x1、x2、…xm，使得 定理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上的映射， 则f是一一映射（即双射）的充要条件是：对任意 证明：必要性.若f是双射，则（此时mi=1）,或者在后一种情形下，不可能有否则，ai1在A中有两个原象ai和ai1，与f是双射不合，而只可能有，则依同样的道理，不可能有 .如此等等. 因为A是有限集，所以经过有限次（设经过m次）后，有 这表明当f是双射时，对任一都存在着映射圈: 在这个映射圈中，诸元素互异，且 充分性.如果对任意 ，这说明从A中任一元素ai出发，都可以得到一个包含mi个互异元素的映射圈，显然f是双射. 定理3 在命题1的条件下，若对，则对任意 这是明显的事实，证明从略. 赛题精讲 例1：设集合 . 【解】形如4k+1的数的数可分三类： ，其中只有形如12l+5的数是形如3k-1的数. 例2：有1987个集合，每个集合有45个元素，任意两个集合的并集有89个元素，问此1987个集合的并集有多少个元素. 【解】显然，可以由题设找到这样的1987个集合，它们都含有一个公共元素a，而且每两个集合不含a以外的公共元素.但是，是否仅这一种可能性呢？ 由任意两个集合的并集有89个元素可知，1987个集合中的任意两个集合有且仅有一个公共元素，则容易证明这1987个集合中必有一个集合中的元素a出现在A以外的45个集合中，设为A1，A2，…，A45，其余的设为A46，A47，…，A1996. 设B为A46，…，A1996中的任一个集合，且，由题设B和A，A1，A2，…，A45都有一个公共元素，且此46个元素各不相同，故B中有46个元素，与题设矛盾，所以这1987个集合中均含有a. 故所求结果为1987×44+1=87429.即这1987个集合的并集有87429个元素. 例3：集合为A的非空子集族，并且当 求n的最大值. 【解】首先考虑至多含三个元素的A的非空子集族，它们共有个，这说明 下证，事实上，设D为满足题设的子集族，若 则B与B-{b}不能同时含于D，以B-{b}代B，则D中元素数目不变.仿此对D中所有元素数目多于4的集合B作相应替代后，集族D中的每个集合都是元素数目不多于3的非空集合，故. 所以， 在许多问题中，计数对象的特征不明显或混乱复杂难以直接计数，这时可以通过适当的映射将问题划归为容易计数的对象，然后再解决，从而取得化难为易的效果. 例4：设A为至少含有两项的公差为正的等差数列，其项都在S中且当将S的其他元素置于A中之后，均不能构成与A有相同公差的等差数列.求这种A的个数（只有两项的数列也视为等差数列） 【解】当为偶数时，满足题中要求的每个数列A中必有连续两项，使其前一项在集{1,2,…,k}和{k+1,k+2,…,2k}中各任取一数，并以二数之差作为公差可以作出一个满足要求的数列A.容易看出，这个对应是双射.故知A的个数为 当n=2k+1为奇数时，情况完全类似.惟一的不同在于这时第二个集合 有k+1个元素.故A的个数为 例5：设an为下述自然数N的个数：N的各位数字之和为n且每位数字都只能取1、3或4.求证对每个自然数n，a2n都是完全平方数. 【证明】记各位数字之和为n且每位数字都是1或2的所有自然数的集合为Sn，并记 这意味着{fn}恰为菲波那契数列. 作对应如下：先将M的数字中自左至