第二节映射与有限集合元素的个数

第二节映射与有限集合元素的个数 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 第二节 映射与有限集合的元素的个数 数学中的对应关系非常多,如数轴上的点与实数的对应;平面上的点与坐标的对应;函数与图象的对应等,这些对应有的是单值对应,也有的是一一对应,我们把集合A到B上的单值对应称为映射.在数学竞赛中恰当地利用映射方法解 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ,可以使问题简单具体,往往会出奇制胜.本节我们来初步地了解一个映射与集合中的计数问题. 【基础知识】 一. 有限集合的元素的个数问题 我们首先约定:若X是一个有限集,则X内所含的全部元素的个数用 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示. Card(X)如果A、B、C是任意的三个有限集,那么有以下几个公式(容斥原理): (1); Card(A:B),Card(A)，Card(B),Card(A:B) (2) Card(A:B:C),Card(A)，Card(B)，Card(C),Card(A:B),Card(B:C) . ,Card(A:C)，Card(A:B:C) (3) Card(A:B),Card(A)，Card(B),Card(A:B) (4)若,则 Crad(B),Crad(A),Crad(CB)B,AA, (5) Card(A:B:C),Card(A:B:C),Card(A),Card(B),Card(C) ，Card(A:B)，Card(B:C)，Card(A:C) 二(映射 1(映射的概念 设A、B是两个非空集合,如果按某一个确定的对应关系,使对于集合A中的任意一个f y元素,在集合B中都有唯一的元素与之对应,那么就称这种对应为从集合A到xf:A,B y集合B的一个映射(mapping).其中元素称为这个映射的原象,为在这个映射下的象. xx2(关于映射的理解 理解映射的关键是抓住集合A中的元素在集合B中的象的存在性和唯一.根f:A,B 据映射中象与原象的不同状态，有下面几种很常用的特殊映射: (1)满射:如果在映射下，集合B中每一个元素在集合A中都至少有一个原象，f:A,B 那么称映射f:A,B为A到B的满射. (2)单射:如果在映射f:A,B下，集合A中不同元素在B中有不同的象，那么称映f:A,B射为A到B的单射. 1 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 (3)双射:如果映射同时是A到B上的满射和单射,那么称映射为A到f:A,Bf:A,BB的双射,即一一映射. b,B (4)如果为满射且任何,都有A中的个元素,使得a,a,？,amf12m (),则称为的倍数映射. i,1,2,？,mf(a),bmfi 3.映射中的计数问题 (1)对于满射,显然有 f:A,BCard(A),Card(B). (2)对于单射,显然有 f:A,BCard(A),Card(B). (3)配对原理:如果存在集合A到集合B上的双射,那么满射,显然有f:A,B Card(A),Card(B). (4)如果为的倍数映射,则 mfCard(A),mCard(B). 【典例精析】 【例1】试问在1，2，……，100中能3或4或5整除的数共有多少, ～2～……～100中能被3整除的数有33个～能被〖 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 〗先分析能被3或4整除的数.在1 整除的数有25个～同时被3且被4整除的数有8个～从而在1～2～……～100中能被3或4整除的数共有33+25-8=50个.根据此种思路～即可求解本题. i【解】设全集，且被整除} A,{x|x,UxU,{x|x,1,2,？,100}(i,3,4,5).i 令，则所求的数为 A,A:A:ACard(A),Card(A:A:A),card(A)，Card(A)34534534，Card(A),Card(A:A),Card(A:A),Card(A:A)，Card(A:A:A) 5343545345 8,6,5,1,60=33+25+20,.从而知在1，2，……，100中能3或4或5整除的数共有60个. 〖说明〗本题主要考查容斥原理的应用. 【例2】一次会议中有1990位数学家参加，每人至少有1327位合作者.求证:可以找到4位数学家，他们中每两个人都合作过. v(i,1,2,？,1990)vA【解】记数学们为，与合作过的数学家组成集合.任取合作过的数iii学家v,v，由Card(A),1327,Card(A),1327,Card(A:A),1990.得: 121212 Card(A:A),Card(A)，Card(A),Card(A:A),1327，2,1990,0. 121212 v,A:Av,v,v,v.从而存在数学家且 3123132 Card(A:A:A),Card(A:A)，Card(A),Card[(A:A):A]又 1231231232 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 ,(1327，2,1990)，1327,1990,1. 从而存在数学家且，从而可知两两合v,A:A:Av,v,v,v,v,vv,v,v,v41234342411234作过. 〖说明〗本题的实质是证明，通过容斥原理的计算来完成. A:A:A,,123 111【例3】称有限集S的所有元素的乘积为S的“积数”.给定数集求数集M,{,,？,}.23100M的所有含偶数个元素的子集的“积数”之和. 111〖分析〗数集M的所有子集的积数之和为设数集M的所有含(1，)(1，)？(1，),1.23100 偶数个元素的子集的积数和为～所有含奇数个元素的个子集的积数之和为～则x，y, yx 111(1，)(1，)？(1，),1.只需再建立一个关于的方程～就可解出 x,yx,y.23100 【解】设数集M的所有含偶数个元素的子集的积数之，所有含奇数和为个元素的子集的x 111积数之和为x，y,(1，)(1，)？(1，),1.，则 y23100 111(1,)(1,)？(1,),1. 又 x,y,23100 99994851x，y,,x,y,,.x,.所以 解得 2002100 【例4】设集合，若，求A,{(x,y)|y,a|x|},B,{(x,y)|y,x，a}Crad(A:B),2实数的取值范围. ayy,a|x|(a,0)a,0【解】当时，画出草图，如图.由图可知当且仅当y,x，a(a,0)a,1y,x，a时，直线与两条射线有两个交y,a|x|y,x，a(a,0) A:Ba,0点，即仅有两个元素;当时，同理可得当且OxA:Ba,,1仅当时，有两个元素.从而实数的取值范a 围为 |a|,1. 【例5】有1987个集合，每个集合有45个元素，任意两个任意的并集有89个元素，问此1987个集合的并集有多少个元素? 〖分析〗由每个集合有45个元素～且任意两个集合的并集有89个元素知～任意两个集合有且只有一元素. 【解】显然可以由题设找到这样的1987个集合，它们都含有一个公共元a，而且每个两素个 a集合不含以外的公共元素. 下面我们来排除其它可能性: 由任意两个集合的并集有89个元素可知，1987个集合中的任意两个集合有且只有一外公共 a元素，则容易证是这1987个集合中必有一个集合A中的元素出现在A以外的45个集合中，A,A,？,AA,A,？,A.设，其余的设为 124546471986 a,BA,A,？,A.A,A,？,A设B为中的任意一个集合，且，由题设B和A,都有464719861245 3 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 一个公共元素,且此46个元素各不相同,故B中有46个元素,与题设矛盾!所以这1987个集合中都含有. a 故所求的结果为1987×44+1=87429,即这1987个集合的并集有87429个元素. 〖说明〗这里我们先 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一种符合题设的特殊情形,然后再排除其可能的情形,从而达到解题的目的,这是一种“先猜后证”的解题策略～应注意加以强化. n【例6】怎样证明集合的全体子集的个数为 2.S,{a,a,？,a}12n 〖分析〗本题限定利用一一映射的知识加以解决～因此首先应建立一个集合S与其到自然 n数子集间的一一映射. {0,1,？,2,1} 【证明】将集合S的每一个子集合与一个二进制数相对应，使得{a,a,？,a}(1,i,i,？i,n,0,m,n)(bb？b)iii12miii212m12m ，而其余的.在这种对应下，空集映射b,b,？b,1b,0(k,i,i,？i)iiik12m12m n于，而全集映射于=，其余的子集合映射于2,1(00？0),0(11？1),22 与之间的某一个确定的二进制数，容易验证这种映射是从S的全体子集(00？0)(11？1)22 nn到自然数的子集间的一一映射，所以子集合的个数为2. {0,1,？,2,1} 〖说明〗本题将集合中的元素与自然数集建立起了一种一一映射～这种建立一一映射的方法 k在竞赛中是常用的.这个问题也可以这样来解决～子集合中元素个数为的子集合个数‎‎是k～所以全体子集的个数是～并且这种方法也是常见的证法. C(k,0,1,2,？,n)n 【例7】如图所示，将8×8的国际象棋棋盘的左上角和右下角都剪去一个方格，问剪去两角的棋盘能否用31个1×2的矩形完全覆盖? 〖分析〗如果将问题改为能否用32个1×2的矩形将8×8的国 际象棋棋盘完全覆盖～这将一个十分容易的问题～可以找到很 多种方法.但是要注意这种不同的完全覆盖的方法的个数却是 一个十分困难的问题.M?E?Fischer于1961年处出了这个数字 42等于12988816×901=2. 但是能过尝试可以发现～要找到一个 将剪去两个角的国际象棋棋盘完全覆盖的方法却是十分困难 的.虽然剪去两个角的棋盘和原来的棋盘相差“不大”～然而前 问题用一一映射的概念就可以迎者却不能完全覆盖不定期个 刃而解了. 【解】首先我们注意到一个1×2的矩形，不论用什么样的覆盖方法，它必覆盖住棋盘的一个黑格与一个白格.假定能用某种方法用31个1×2的矩形完全覆盖，那么这种覆盖方法实质上就是在剪过的棋盘上的黑格和白格之间建立了一个一一映射.这说明剪过的棋盘上的黑格和白格是一样多的.然而，实际上剪过的棋盘上还有32个黑格和30个白格.这一矛盾说明不能用1×2的矩形将剪过的棋盘完全覆盖. 〖说明〗本题与上节的例1一样～也是利用一一映射处理问题～这种处理方法在数学竞赛中是最常用的方法之一～应重点掌握. 【例8】集合A和B分别由适合如下条件的所有五倍数构成:对于集合A中的每一个数，其4 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 各位数字之和或者加1或者减1之后是5的倍数;对于集合B中的每一个数，其各位数字之和或者是5的倍数，或者是减去2之后是5的倍数.证明:集合A和集合B中所含的元素个数相等. 〖分析〗若要证明两个集合所含的元素个数相同～只需在两个集合之间建立一种一一映射即可. 【解】分别用表示的数字和.对是五位数，并且 S(,),S(,),,A,,,109999,,,,, ，因此或S(,)，S(,),9，9，9，9，10,46,1(mod5)S(,),,1(mod5),S(,),0 ，即 2(mod5),,B. ,,109999,,反之，设，则.因此对应是A、B之间的一一,,B,,109999,,,A 对应，从而 Card(A),Card(B). 〖说明〗建立一一映射证明两集合的个数相同～是奥林匹克数学竞赛中常用的方法～应重点掌握. 【例9】设是集合的子集，且(). A,A，？，ACard(A),660{1,2,？,2003}i,1,2,？,301230i 求证:存在，使得 Card(A:A),203.i,j,i,j,{1,2,？,30}ij 【证明】不妨设每一个的元素都为660个(否则去掉一些元素).作一个集合、元素的关Ai 系表:表中每一行(除最上面的一行外)分别表示30个集合，表的列(最A,A，？，An1230 i,A(i,1,2,？,2003,1,j,30)左边的一列除外)分别表示2003个元素1，2，……，2003.若，j iAi,A则在所在的列与所在行的交叉处写上下班1，若，则在交叉处写上0.如下表: jj 1 2 3 … 2003 A × × × … × 1 A × × × … × 2 …… × × × … × A × × × … × 30 mj表中每一行有660个别，因此共有30×660个1.设第列有个1()，则j,1,2,？,2003j 20032m,30，660.jA:A有由于是每个元素属于个交集，因此，C,jstmjj,1 20032C,Crad(A:A). ,,mstjj,11,s,t,30 5 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 20032003200320032003111222由柯西不等式 ,(C,(m,m)(m),m),,,,,jjjmjj2200321j,1j,1j,j,j,11 所以必有满足: i,j 2003200311660(30，660,2003)12=， ,202()((m),m)CardA:A,，,,jjij2200329，20032Cj,j,1130 所以 Card(A:A),203.ij 〖说明〗本题中所作的表～称为元素、集合的从属关系表～它在讨论涉及多个集合的问题时经常采用. 【例10】(首届东南地区竞赛)支球队要举行主客场双循环比赛(每两支球队比赛两场，n 各有一场主场比赛)，每支球队在一周(从周日到周六的七天)内可以进行多场客场比赛.但是如果一周内某球队有主场比赛，在这一周内不能安排该球队的客场比赛.如果4周内能够完成全部比赛，求的最大值.(注:A、B两队在A方场地举行的比赛，称为A的主场比n 赛，B的客场比赛.) 【解】如下表所示: 表格 关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载 中的“*”表示该球队在该周有主场比赛，不能出访.容易验证，按表中的安排，6支球队四周内可以完成比赛. 球队 第一周 第二周 第三周 第四周 1 * * 2 * * 3 * * 4 * * 5 * * 6 * * i下面证明7支球队不能在四周内完成比赛.设表示号球队的主场比赛周S(i,1,2,3,4,5,6,7)i 次的集合.假设4周内能完成比赛，则是{1S，2，3，4}的非空真子集. i 一方面由于某周内该队有主场比赛，在这一周内不能安排该球的客场比赛，所以S(i,1,2,3,4,5,6,7)中，没有一个集合是另外一个集合的子集. i 另一方面，设 A,{{1},{2},{1,2,3}},B,{{2},{2,3},{2,3,4}},C,{{3},{1,3},{1,3,4}} D,{{4},{1,4},{1,2,4}},E,{{2,4}},F,{{3,4}} i,j,i,j,i,j,{1,2,3,4,5},S,S由抽屉原理，一定存在属于同一集合A或B或C或D或Eij S,SS,S或F，必有或发生. ijij n所以的最大值是6. 〖说明〗本题是例9的深入延伸～先能过表格得出一个确定的值～再证明大于,小于,这个数的不能成立～这是求解最值问题的常用方法. S,{1,2,？,n}S【例11】(1992年全国高中数学联赛)设集合.若X是的子集，把X中nn的所有数的和称为X的“容量”(规定空集的容量为0).若X的容量为奇(偶)数，则称X6 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 为的奇(偶)子集. Sn (1)求证:的奇子集与偶子集的个数相等. Sn n,3(2)求证:当时，的所有奇子集的容量之和与所有偶子集的容量之和相等. Sn n,3(3)当时，求出的所有奇子集的容量之和. Sn 〖分析〗要证明两个集合的元素一样多～一种方法是直接将两个集合中的元素个数算出来～ 另外一种方法是在这两个集合之间建立一个一一映射.这里我们采用第二种方法解决. 【解】(1)设A是的任一奇子集，构造映射如下: Sfn ，若1,A; A!A,{1} 1,A，若. A!A:{1} (注:表示从集合A中去掉1后的集合)所以映射是将奇子集映‎‎为偶子集的映射. A,{1}f 易知，若是的两个不同的奇子集，则，即为单射. SA,Af(A),f(A)fn1212 1,B又对的每一个偶子集B，若，则存在，使得; SA,B\{1}f(A),Bn 1,B若，则存在，使得，从而是满射. A,B:{1}f(A),Bf 所以是使得的奇子集的组成的集到的偶子集所组成的集之间的一一对应，从而的奇SSfnn 1nn,1,2,2子集与偶子集的个数相等，故均为个. Sn2 (2)设表示中全a(b)体奇(偶)子集容量之和. Snnn 若SS是奇数，则的奇子集S由如下两类构成:?的奇子集;?的偶子集与集n(,3)nn,1n,1 的并，于是可得: {n} n,2 (*) a,a，(b，n,2)nn,1n SSS又的偶子集可由的偶子集和的偶子集与集的并构成，所以: {n}nn,1n,1 n,2b,b，(a，n,2) (**) nn,1n a,b.由(*)、(**)便可得 nn n(,4)若是偶数，同上可知: 7 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 n,2 a,a，(a，n,2)nn,1n,1 n,2 b,b，(b，n,2)nn,1n,1 n,1由于是奇数，由上面已证，从而 a,ba,b.n,1n,1nn 综上即知， a,b(n,2,3,？).nn n,1(3)由于的每一个元素均在个子集中出现，所以的所有子集容量之和为 2SSSnnn n,1n,2 2(1，2，？，n),2n(n，1) 1n,2n,3又由(2)知，所以a,,2n(n，1),2n(n，1). a,bnnn2 〖说明〗对于第,2,小题的证明～建立了递推关系～这是解决“计数”问题的一个有效的方 法. 【例12】(2003年IOM试题)设A是集合的恰有101个元素的子集.S,{1,2,？,1000000}证明:在S中存在数，使得中，每两个的A,{x，t|x,A},j,1,2,？,100t,t,？,tjj12100 交集为空集. A:A,,A:A〖分析〗先弄清在什么情况下.设～则a,x，t,y，t,x,y,A.于a,ijijij 是t,t,y,x.这说明选取时～只要保证其中任意两个之差不等于A中任二元t,t,？,tij12100 素之差即可. 【解】考虑集合，则 D,{x,y|x,y,A}Crad(d),101，100，1,10101.A:A,,A:Aa,x，t,a,y，tx,y,At,t,y,x,D若，设，则，其中，则. a,ijijijij A:A,,t,t,Dt,t,y,xx，t,y，t若，即存在，使得，从而，即. x,y,Aijijijij A:A,,t,t,D所以的充要条件是.于是我们只需在集合S中取出其100个元素，使ijij 得其中任意的两个的差都不属于D. 下面用递推的方法来取出这100个元素. 先在S中任取一个元素t，再从S中取一个元素使t,得这是因21 t,t，D,{t，x|x,D}.tt为取定后，至多有10101个S中的元素都不能作为，从而12221 t在S中存在这样的. 2 t,t,？,tt,t,t,？,tk(,99)若已有个S中的元素满足要求，再取使得都不属于这12kk，112k8 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 k,999999是因为取定以后，至多有10101个S中t，D,{t，x|x,D}.t,t,？,tk，1k，112k 的数不能作为故在S中存在满足条件的.所在在S中存在，其中任意两个t,tt,t,？,tk，1k，112100 的差都不属于D. 综上所述，命题得证. 6〖说明〗条件可以改小一些.一般地～我们有如下更强的结论: Card(S),10 2若A是S={1～2～3～……～n}的一个k元子集～m为正整数～满足条件n>(m,1)()～C，1k则存在,中的元素～使得中任意两个的交集A,{x，t|x,A},j,1,2,？,mt,t,？,tjj12m 为空集.这个结论是可以证明的～请读者自已试证之(见,组习题,). 【赛向点拨】 1.集合中的计数问题是最近几年竞赛试题中的常见问题，是综合考查集合知识的一个很好的出发点. 2.映射方法是处理竞赛问题的一种非常重要的方法，将问题利用映射的方法重往往可以化难为易、化繁为简. 3. 集合是组合数学的基础，也是高中数学竞赛中的重要组成部分.希望大家通过本讲学习开拓思路，灵活解题，另外，要想解好集合题目，相关知识也很重要. 【针对练习】 (A组) 1(某班期中考试中，数学优秀率为70%，语文优秀率为75%，则两门学科都优秀的百分率是( ) A(60% B(55% C(50% D(45% 2(已知集合A={2，4，6，8，9}，集合B={1，2，3，4，6，7}.又已知集合C是这样的一个非空集合:若C的各元素都加上2，则变为A的一个子集;若C的各元素都减去2，则变为B的一个子集，则( ) Card(C), A(9 B(8 C(7 D(6 ((2002年全国高中数学赛)已知两个实数集合A,,a3,a,…,a,与B,,b,b,…,b,，121001250若从A到B的映射f使得B中每个元素都有原象，且)?f(af(a)?…?f(a)则这样的映射共有12100 ( )个. A(C5010 B.C4899 C.C4910 D.C499900 24(设，B,{y|y,f(n),n,A}，则集合 f(x),x，x,2,A,{n|1,n,n,n,Z} B:{2m|m,Z}的元素的个数是( ) A(100 B(51 C(36 D(以上都不对 9 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 20075((2007年江西预赛)正整数集合的最小元素为，最大元素为，并且各元素可以1Ak k从小到大排成一个公差为的等差数列，则并集中的‎‎元素个数为( )( AA:1759 119120151154A( B. ; C. ; D.. 6(某班有50人，开设英语和日语两种外语.现规定每人至少选学一门，估计报英语的人数占全班总人数的80%~90%之间，报日语的人数占全班总人数的32%~40%之间.设M是两门都学的人数的最大值，m是两门都学的人数的最小值，则M,m= . n7(已知集合，把M中最高位数字是1的数全部抽出出M,{x|x,2,0,n,1000,n,Z} 来，组成一个新的集合S，则S中的元素共有 个(). lg2,0.3010 8(已知映射，其中集合，其中集合中的元素都是A中元f:A,BA,{,3,,2,,1,1,2,3,4} 素在映射下的象，且对任意在B中，和对应的元素是，则集合B中的元素的个fa,A,|a| 数是 . 9(一个自然数若与它的“反序数”相等，这个自然数就称为一个“魔幻数”.如3和1991都是“魔幻数”.在集合的元素中，去掉所有的“魔幻数”后，M,{x|x,Z,1,x,2000} 形成一个不含“魔幻数”的子集N，则集合N中的元素共有 个. 10.(2007年山东省青岛市奥林匹克学校入学试题)开运动会时，高一某班共有28名同学参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳比赛和田径比赛的有3人，同时参加游泳比赛和球类比赛的有3人，没有人同时参加三项比赛，问同时参加田径比赛和球类比赛的有多少人,只参加游泳一项比赛的有多少人, 11.求1至250之间能被2、3、5和7中任何一个整数整除的整数的个数. r,r？,r12. r个点顺次排在同一条直线上，每个点涂上黑色或白色.已知和分别涂上nr12,nn1了白色和黑色.求证:相邻点间线段不同色的个数一定是奇数. (B组) A,A:A:？:A,R,{A,A,？,A},1.设若R中每个元素的交集不空，而个元r12m12m r，1素的交集为空集，则: (1)Card(A)至少是多少, Card(A)(2)当Card(A)最小时，为多少, i k2.设Z是平面上由个点组n(,3)成的点数，其中任三点不共线，又设自然数满足不等式‎‎10 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 n ,2 k,n.k如果Z中的每个点都至少与Z中的个点有线段‎‎相连，证明:这些线段中一定有三条线段构成三角形的三边. 3. (2005年北方数学奥林匹克数学邀请赛)已知位数的各位数字只‎‎能取集合中1,2,3,4,5n,,的元素，设含有数字,且在,的前面不含,的位数个数为，求( fnfnn，，，，4.对于任何的集合S，设为集合S的子集的个数.如果A、B、C是三集合，满足下列条n(S) 件: (1);(2) n(A)，n(B)，n(C),n(A:B:C)Card(A),Card(B),100.求的最小值. Card(A:B:C) 1005.(2006年山东省第二届夏令营试题)设T是由的所有的正因‎‎数组成的集合，S是T60 的一个子集，其中没有一个数是另一个数的倍数，求的最大值. Card(S) 26. 若A是S={1，2，3，……，n}的一个k元子集，m为正整数，满足条件n>(m,1)()，C，1k则存在,中的元素，使得中任意A,{x，t|x,A},j,1,2,？,m两个的交集t,t,？,tjj12m 为空集. 【参考答案】 (A组) 1(解:设班级人数为100，则两门学科中至少有一门优秀的总人数不大于100. 由， Card(A:B),Card(A)，Card(B),Card(A:B) ,100可得70+75,,即 Card(A:B)Card(A:B),45. 45%.故两门学科都优秀的百分率至少为 2(解:逆向思维，即A中各元素都减去2，得集合D={0，2，4，6，7}，集合B中的各元素都加上2，得集合E={3，4，5，6，7，10}，因此集合C是集合D与集合E的公共元素组 32,1,7成的集合G={4，6，7}的真子集，这样的集合C共有个. 3. 解:不妨设b1,b,…,b，将A中元素,aa,…,a100按顺序分为非空的50组。 25012 定义映射f:A?B，使第i组的元素在f之下的象都是(i=1,2,…,50).b i 易知这样的满足题设f要求，每个这样的分组都一一对应满足条件的映射，于是满足题设要求的映射f的个数与A按足码顺序分为50组的分法数相等，而A的分法数为C49，则99 9这样的映射共有C4，故选D. 99 11 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 2n,A4.解:当时，恒为偶数.从而选A. y,f(n),n，n,2 2006200620071,，nk5.解:设，由，得，于是，CradA()1119,，,n,CardAn()1,，17k17k 20062006，; CradA()135,，,cradAACradA()()13:,,，,5917591003591759， 从而(故应CradAACradACradACradA()()()()119353151:,，,,，,,175917591003 选C. 6.解:设集合A={报英语的同学}，集合B={报日语的同学}，则由题可知50×80%50×90%,即40. ,Card(A),,Card(A),45 同理，，从而， 16,Card(B),2040，16,50,Card(A:B),45，20,50即，所以，所以M,m=9. 6,Card(A:B),15M,15,m,6 kkknk7(解:令10,2,2，10，则有，于是且使得,n,1，lg2lg2 0,n,1000，从而可以计算得S的个数为302. k,0,1,2,？,301 A,B8.解:依题意，由的对应法则于是，将集合A中的7个不同的元素分别f:a,|a|. 取绝对值后依次得3，2，1，1，2，3，4.由集合元素的互异性可知,它有4个元B,{1,2,3,4}素. 9(显然前9个数都是“魔幻数”，两位数中有11，22，33，44，55，66，77，88，99共9个“魔幻数”三位数中有101，111，121，131，141，151，161，171，18，191，202，212，„„，989，999共90个“魔幻数”;在不大于2000的四位中还有10个“魔幻数”，它们分别是1001，1111，1221，1331，1441，1551，1661，1771，1881，1991.所以共有9+9+90+10=118 ,118,1882个“魔幻数”，M的不含“魔幻数”的子集N共有2000个. 10.解,A,{参加游泳比赛的同学},B,{参加田径比赛的同学},C,{参加球类比赛的同学} 则card(A)=15,card(B)=8,card(C)=14,card(A?B?C)=28 且card(A?B)=3,card(A?C)=3,card(A?B?C)=0 12 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 由公式?得28,15，8，14,3,3,card(B?C)+0 即card(B?C)=3 所以同时参加田径和球类比赛的共有3人，而只参加游泳比赛的人有15,3,3,9(人) 11.解:设A表示1至250之间能被2整除的整数集合，B表示1至250之间能被3整除的整数集合，C表示1至250之间能被5整除的整数集合，D表示1至250之间能被7整除的整 250250，，，，数集合.则 Card(A),,125,Card(B),,83,,,,,32，，，， 250250，，，， Card(C),,50,Card(D),,35.,,,,57，，，， 250250250，，，，，， Card(A:B),,41,Card(A:C),,25,Card(A:D),,17,,,,,,,2，32，52，7，，，，，， 250250250，，，，，， Card(B:C),,16Card,(B:D),,11Card,(C:D),,7.,,,,,,3，53，75，7，，，，，， 250250，，，， Card(A:B:C),,8Card,(A:B:D),,5,,,,,2，3，52，3，7，，，， 250250，，，， Card(A:C:D),,3,Card(B:C:D),,2,,,,,2，5，73，5，7，，，， 250，，(其中[x]表示不超过的最大整x数) Card(A:B:C:D),,1.,,2，3，5，7，， 所以由容斥原理得:++ Card(A:B:C:D),Card(A)Card(B)，Card(C)Card(D) ,Card(A:B),Card(A:C),Card(A:D),Card(B:C),Card(B:D) Card(B:C:D) ,Card(C:D)，Card(A:B:C)，Card(A:B:D)，Card(A:C:D)， ,Card(A:B:C:D),193. 12.证明:在集合{黑色,白色}和{1,,1}之间建立一个一一映射，使黑色映射到1，白色映射到 arrr,1，则每个顶点都映射到一个数(i,1,2,？,n).设线段两端点不同色， iiii，1 kaa则=,1.设两点不同色的线段的个数为，从下式 ii，1 222kaa,aaa？aa,(aa)(aa)？(aa),(,1),1= 1123,11223,1nnnnn 13 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 k可得为奇数. (B组) 1(解:考虑下标集合的任一元子集在中任A:A:？:A{i,i,？,i}{1,2,？,m}riii12r12r取一个元素，这就建立了从下标到元素的一个映射，并且不同的原象其象a{i,i,？,i}a12r 也不相同，否则不同的，对应同一个时，必有个子集不r，1{i,i,？,i}{j,j,？,j}a12r12r r空，与题设矛盾.这说明 Card(A),C.m (2)考虑任一，在R中任取其余个集合，它们的交集‎‎至少有一个元素(不空)，而此Ari r交集与的交集为，所以中至少含有A中的个AA,A:A:？A:A:？:A,Ci12i,1i，1m,1m r不同的元素，有 Card(A),Card(A),C.im,1 rrrrr,1而当时， ? Card(A),CCard(A),Card(A),C,C,C,C.mim,1mm,1m,1 r,1r,1另一方面，与R中任选个其余的集相交，至少有一个元素，有种不同的取法，ACim,1 r,1r,1可知至少有个不同的元素， ? ACard(A),C.Ciim,1m,1 r,1由??可得 Card(A),C.im,1 n3k,2k,,2(证明:因为，所以，即每个点都至少与Z中2个点有线段相连.不妨高22 N,AM,{P|P,Z,P{P|P,Z,P设AB为Z中点连成的线段.令与有线段相连，},{B} B与有线段相连. },{A} k由于Z中任一点至少引出条直线，所以有 Card(M),k,1,Card(N),k,1. M:N又由于中不含A、B，所以有因此 Card(M:),n,2. Card(M:N),Card(M)，Card(N),Card(M:N),(k,1)，(k,1),(n,2) ,2k,2,(n,2),(n,2),(n,2),0. C,M所以M:N,,，即存在点，且C,N(C,A,C,B). 显然线段AB、AC、BC构成三角形的三边. 3(解:对于满足条件的n+1位数的个数f(n，1)的计算，可分为如下两种情况: nn情形1:当个位数字不是5时，则前位数中一定含有数字5，它是满足条件的一个位14 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 数，其个数为对于每一个这样的位数，从1、2、3、4中任取一个放在它的最右端，nf(n). n，1n，1可得一个位数，因此个位数字不是5的位数是个. 4f(n) 情形2:当个位数字是5时，由于在5的前面不能含有3，则前位数字的每一位数‎‎字均为n nnn，14种取法，因此个数字是5的位数共有个.所以， 4f(n，1),4f(n)，4 (，1)()fnfn即，显然 ,,1f(1),1.nn,144 f(n)n,1则，故 ,1，(n,1),nf(n),n,4.n,14 kk4.解:如果一个集合有个元素，那么它有个‎‎子集.由题设有 2 Card(C),101Card(A:B:C),101100100Card(C)Crad(A:B:C)，即 1，2,2.2，2，2,2 Card(C),101因为是大不动声色1且等于一个性的整数幂，所以从而有 1，2Card(C),101. Card(A:B:C),102. 由容斥原理得:Card(A:B:C),Card(A:B:C)，Card(A)，Card(B)，Card(c) . ,Card(A:B),Card(A:C),Card(B:C) 从而有 Card(A:B:C),403,Card(A:B),Card(A:C),Card(B:C) B:CA:C,A:B:CA:BCard(A:B),Card(A:C),Card(B:C),102由、、得， 所以 Card(A:B:C),403,102，3,97. 另一个方面，取，满A,{1,2,？,100},B,{3,4,5,？,102},C,{1,2,4,5,6,？,100,101,102}足题设条件.这时 Card(A:B:C),Crad({4,5,6,？,100}),97. 所以的最小值为97. Card(A:B:C) 2abc60,2，3，55.解:， ？T,{235|0,a,200,0,b,c,100,a,b,c,Z}？ 200,b,cbc设 S,{235|0,b,c,100,b,c,Z} 200,b,cbc200,b,cbc11112222235235u,v,若u,v,S,u|v，设， 15 高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 200bc200bc,,,,,,1122,bb,由知，从而，即矛盾～ b,b,c,cu,vu|v,121212,cc,12, 2故S中没有一个元素是另一个元素的倍数， ？Card(S),101. 2,,SS下证:若T的一个子集的元素个数，则中一定有一个元素是另一个元素的倍数. 101 2,因为，所以考虑3和5的指数对，一定有两个元素是相同的. (b,c)Card(S),101 mijnij不妨设 u,2，3，5,v,2，3，5. 当时，;当时， m,nm,nu|vv|u. 2综上所述，所求的的最大值为 101.Card(S) 26.解:考虑集合，显然， B,{|x,y||x,y,A}Card(B),C，1.k下证存在，使得对，有我们递归地构造. |t,t|,B..t,t,？,t,Si,jt,t,？,tij12m12m 22，令，则有: 取t,1c,S\(B，t)Card(c),n,(C，1),(m,2)(C，1).111kk1 21,i,m对，假定和已经选定，且，取中t,t,？,tcCard(c),(m,i,1)(C，1),0i12ik1的最小元素为，考虑集合，则有 ctc,c\(B，t)ii，1ii，1i，1 22， Card(c),Card(c),(C，1),(m,i,2)(C，1),0i，ikk1 显然满足要t,t,？,t求. 12m 注:题中表示集合 B，t{b，t|b,B}.11 16