资源预览内容
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
第9页 / 共16页
第10页 / 共16页
亲,该文档总共16页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著1第二第二节节 映射与有限集合的元素的个数映射与有限集合的元素的个数数学中的对应关系非常多,如数轴上的点与实数的对应;平面上的点与坐标的对应;函数 与图象的对应等,这些对应有的是单值对应,也有的是一一对应,我们把集合 A 到 B 上的单值 对应称为映射.在数学竞赛中恰当地利用映射方法解题,可以使问题简单具体,往往会出奇制 胜.本节我们来初步地了解一个映射与集合中的计数问题. 【基础知识基础知识】 一一. 有限集合的元素的个数问题有限集合的元素的个数问题我们首先约定:若 X 是一个有限集,则 X 内所含的全部元素的个数用表示.)(XCard如果 A、B、C 是任意的三个有限集,那么有以下几个公式(容斥原理容斥原理):(1);)()()()(BACardBCardACardBACardIU(2) )()()()()()(CBCardBACardCCardBCardACardCBACardIIUU.)()(CBACardCACardIII(3) )()()()(BACardBCardACardBACardUI(4)若,则AB )()()(BCCradACradBCradA(5) )(CBACardII)()()()(CCardBCardACardCBACardUU)()(CBCardBACardII)(CACardI二映射二映射 1映射的概念设 A、B 是两个非空集合,如果按某一个确定的对应关系,使对于集合 A 中的任意一f个元素,在集合 B 中都有唯一的元素与之对应,那么就称这种对应为从集合xyBAf:A 到集合 B 的一个映射映射(mapping).其中元素称为这个映射的原象原象,为在这个映射下的xyx 象象. 2关于映射的理解理解映射的关键是抓住集合 A 中的元素在集合 B 中的象的存在性和唯一.BAf:根据映射中象与原象的不同状态,有下面几种很常用的特殊映射:(1)满射:如果在映射下,集合 B 中每一个元素在集合 A 中都至少有一个原象,BAf:那么称映射为 A 到 B 的满射.BAf:(2)单射:如果在映射下,集合 A 中不同元素在 B 中有不同的象,那么称映射BAf:为 A 到 B 的单射.BAf:高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著2(3)双射:如果映射同时是 A 到 B 上的满射和单射,那么称映射为 ABAf:BAf:到 B 的双射,即一一映射.(4)如果为满射且任何,都有 A 中的个元素,使得(fBbmmaaa,21Lbafi)(),则称为的倍数映射.mi, 2 , 1Lfm3.映射中的计数问题(1)对于满射,显然有BAf:).()(BCardACard(2)对于单射,显然有BAf:).()(BCardACard(3)配对原理配对原理:如果存在集合 A 到集合 B 上的双射,那么满射,显然有BAf:).()(BCardACard(4)如果为的倍数映射,则fm).()(BmCardACard【典例精析典例精析】 【例 1】试问在 1,2,100 中能 3 或 4 或 5 整除的数共有多少? 分析先分析能被 3 或 4 整除的数.在 1,2,100 中能被 3 整除的数有 33 个,能被整除 的数有 25 个,同时被 3 且被 4 整除的数有 8 个,从而在 1,2,100 中能被 3 或 4 整除 的数共有 33+25-8=50 个.根据此种思路,即可求解本题.【解】设全集,且被 整除100, 2 , 1|LxxUUxxAi|xi).5 , 4 , 3( i令,则所求的数为543AAAAUU)()()()(43543ACardAcardAAACardACardUU)()()()()(5435453435AAACardAACardAACardAACardACardIIUUU=33+25+20.从而知在 1,2,100 中能 3 或 4 或 5 整除的数共有601568 60 个. 说明本题主要考查容斥原理的应用.【例 2】一次会议中有 1990 位数学家参加,每人至少有 1327 位合作者.求证:可以找到 4 位数学家,他们中每两个人都合作过.【解】记数学们为,与合作过的数学家组成集合.任取合作过的数)1990, 2 , 1(LiviiviA学家,由得:21,vv.1990)(,1327)(,1327)(2121AACardACardACardU. 0199021327)()()()(212121AACardACardACardAACardUI从而存在数学家且213AAvI.,2313vvvv高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著3又)()()()(321321321AAACardACardAACardAAACardUIIII. 119901327)199021327(从而存在数学家且,从而可知两两3214AAAvII142434,vvvvvv4321,vvvv合作过.说明本题的实质是证明,通过容斥原理的计算来完成.321AAAII【例 3】称有限集 S 的所有元素的乘积为 S 的“积数”.给定数集求数.1001,31,21LM集 M 的所有含偶数个元素的子集的“积数”之和.分析数集 M 的所有子集的积数之和为设数集 M 的所有含. 1)10011 ()311)(211 (L偶数个元素的子集的积数和为,所有含奇数个元素的个子集的积数之和为,则xy yx只需再建立一个关于的方程,就可解出. 1)10011 ()311)(211 (Lyx,., yx【解】设数集 M 的所有含偶数个元素的子集的积数之和为,所有含奇数个元素的子集的x积数之和为,则y yx. 1)10011 ()311)(211 (L又 yx. 1)10011 ()311)(211 (L所以 解得.10099,299yxyx.2004851x【例 4】设集合,若,| ),(|,| ),(axyyxBxayyxA2)(BACradI求实数的取值范围.a【解】当时,画出草图,如图.由图可知当且仅当0a时,直线与两条射线有两个1aaxy| xay 交点,即仅有两个元素;当时,同理可得BAI0a当且仅当时,有两个元素.从而实数的1aBAIa取值范围为. 1|a【例 5】有 1987 个集合,每个集合有 45 个元素,任意两个任意的并集有 89 个元素,问此 1987 个集合的并集有多少个元素? 分析由每个集合有 45 个元素,且任意两个集合的并集有 89 个元素知,任意两个集合有且 只有一元素. 【解】显然可以由题设找到这样的 1987 个集合,它们都含有一个公共元素,而且每个两a 个集合不含以外的公共元素.a 下面我们来排除其它可能性: 由任意两个集合的并集有 89 个元素可知,1987 个集合中的任意两个集合有且只有一外公Oyx) 0( |axay) 0( aaxy) 0( aaxy高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著4共元素,则容易证是这 1987 个集合中必有一个集合 A 中的元素出现在 A 以外的 45 个集a合中,设,其余的设为4521,AAAL.,19864746AAAL设 B 为中的任意一个集合,且,由题设 B 和 A,都.,19864746AAALBa4521,AAAL有一个公共元素,且此 46 个元素各不相同,故 B 中有 46 个元素,与题设矛盾!所以这 1987 个 集合中都含有.a 故所求的结果为 198744+1=87429,即这 1987 个集合的并集有 87429 个元素. 说明这里我们先设计一种符合题设的特殊情形,然后再排除其可能的情形,从而达到解题的 目的,这是一种“先猜后证”的解题策略,应注意加以强化.【例 6】怎样证明集合的全体子集的个数为,21naaaSL.2n分析本题限定利用一一映射的知识加以解决,因此首先应建立一个集合 S 与其到自然数子集间的一一映射.12 , 1 , 0nL【证明】将集合 S 的每一个子集合与一)0 ,1(,2121nmniiiaaamiiimLL个二进制数相对应,使得,而其余的2)( 21miiibbbL1 21 miiibbbL.在这种对应下,空集映射于,而全集映射于),(021mkiiikbL0)000(2L=,其余的子集合映射于与之间的某一个确定的二进制2) 111(L12 n 2)000(L2) 111(L数,容易验证这种映射是从 S 的全体子集到自然数的子集间的一一映射,12 , 1 , 0nL所以子集合的个数为.2n说明本题将集合中的元素与自然数集建立起了一种一一映射,这种建立一一映射的方法 在竞赛中是常用的.这个问题也可以这样来解决,子集合中元素个数为的子集合个数是k,所以全体子集的个数是,并且这种方法也是常见的证法.), 2 , 1 , 0(nkCk nL【例 7】如图所示,将 88 的国际象棋棋盘的左上角和右下角都剪去一个方格,问剪去两 角的棋盘能否用 31 个 12 的矩形完全覆盖? 分析如果将问题改为能否用 32 个 12 的矩形将 88 的国际 象棋棋盘完全覆盖,这将一个十分容易的问题,可以找到很多 种方法.但是要注意这种不同的完全覆盖的方法的个数却是一 个十分困难的问题.MEFischer 于 1961 年处出了这个数字等 于 12988816=249012. 但是能过尝试可以发现,要找到一个将 剪去两个角的国际象棋棋盘完全覆盖的方法却是十分困难的. 虽然剪去两个角的棋盘和原来的棋盘相差“不大”,然而前者 却不能完全覆盖不定期个问题用一一映射的概念就可以迎刃而解了. 【解】首先我们注意到一个 12 的矩形,不论用什么样的覆盖方法,它必覆盖住棋盘的一 个黑格与一个白格.假定能用某种方法用 31 个 12 的矩形完全覆盖,那么这种覆盖方法实高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著5质上就是在剪过的棋盘上的黑格和白格之间建立了一个一一映射.这说明剪过的棋盘上的黑 格和白格是一样多的.然而,实际上剪过的棋盘上还有 32 个黑格和 30 个白格.这一矛盾说明 不能用 12 的矩形将剪过的棋盘完全覆盖. 说明本题与上节的例 1 一样,也是利用一一映射处理问题,这种处理方法在数学竞赛中是 最常用的方法之一,应重点掌握.【例 8】集合 A 和 B 分别由适合如下条件的所有五倍数构成:对于集合 A 中的每一个数, 其各位数字之和或者加 1 或者减 1 之后是 5 的倍数;对于集合 B 中的每一个数,其各位数 字之和或者是 5 的倍数,或者是减去 2 之后是 5 的倍数.证明:集合 A 和集合 B 中所含的 元素个数相等. 分析若要证明两个集合所含的元素个数相同,只需在两个集合之间建立一种一一映射即可.【解】分别用表示的数字和.对是五位数,并且)(),(SS,109999,A,因此或)5(mod146109999)()(
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号