koorio.com
海量文库 文档专家
当前位置:首页 >> 数学 >>

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


高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

第二节 映射与有限集合的元素的个数
数学中的对应关系非常多 ,如数轴上的点与实数的对应 ;平面上的点与坐标的对应 ;函数 与图象的对应等,这些对应有的是单值对应,也有的是一一对应,我们把集合 A 到 B 上的单值 对应称为映射.在数学竞赛中恰当

地利用映射方法解题 ,可以使问题简单具体 ,往往会出奇制 胜.本节我们来初步地了解一个映射与集合中的计数问题.

【基础知识】
一. 有限集合的元素的个数问题 我们首先约定:若 X 是一个有限集,则 X 内所含的全部元素的个数用 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)若 B ? A ,则 Crad ( B) ? Crad ( A) ? Crad (C A B)
?

(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 是两个非空集合,如果按某一个确定的对应关系 f ,使对于集合 A 中的任意一个 元素 x ,在集合 B 中都有唯一的元素 y 与之对应,那么就称这种对应 f : A ? B 为从集合 A 到 集合 B 的一个映射(mapping).其中元素 x 称为这个映射的原象, y 为 x 在这个映射下的象. 2.关于映射的理解 理解映射 f : A ? B 的关键是抓住集合 A 中的元素在集合 B 中的象的存在性和唯一. 根据映射中象与原象的不同状态,有下面几种很常用的特殊映射: (1)满射:如果在映射 f : A ? B 下,集合 B 中每一个元素在集合 A 中都至少有一个原象, 那么称映射 f : A ? B 为 A 到 B 的满射. (2)单射:如果在映射 f : A ? B 下,集合 A 中不同元素在 B 中有不同的象,那么称映射

f : A ? B 为 A 到 B 的单射.

1

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

(3)双射:如果映射 f : A ? B 同时是 A 到 B 上的满射和单射,那么称映射 f : A ? B 为 A 到 B 的双射,即一一映射. (4) 如 果 f 为 满 射 且 任 何 b ? B , 都 有 A 中 的 m 个 元 素 a1 , a2 , ?, am , 使 得

f (ai ) ? b ( i ? 1,2, ?, m ),则称 f 为 m 的倍数映射.
3.映射中的计数问题 (1)对于满射 f : A ? B ,显然有 Card ( A) ? Card ( B). (2)对于单射 f : A ? B ,显然有 Card ( A) ? Card ( B). (3) 配 对 原 理 : 如 果 存 在 集 合 A 到 集 合 B 上 的 双 射 , 那 么 满 射 f : A ? B , 显 然 有

Card ( A) ? Card ( B).
(4)如果 f 为 m 的倍数映射,则 Card ( A) ? mCard( B).

【典例精析】
【例 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 个.根据此种思路,即可求解本题.

} , Ai ? {x | x ?U 且 x 被 i 整除} (i ? 3,4,5). 【解】设全集 U ? {x | x ? 1,2,?,100
令 A ? A3 ? A4 ? A5 , 则所求的数为 Card( A) ? Card( A3 ? A4 ? A5 ) ? card( A3 ) ? Card( A4 )

? Card( A5 ) ? Card( A3 ? A4 ) ? Card( A3 ? A5 ) ? Card( A4 ? A5 ) ? Card( A3 ? A4 ? A5 )
=33+25+20- 8 ? 6 ? 5 ? 1 ? 60 .从而知在 1,2,……,100 中能 3 或 4 或 5 整除的数共有 60 个. 〖说明〗本题主要考查容斥原理的应用. 【例 2】一次会议中有 1990 位数学家参加,每人至少有 1327 位合作者.求证:可以找到 4 位数学家,他们中每两个人都合作过. 【解】记数学们为 vi (i ? 1,2,?,1990 ) ,与 vi 合作过的数学家组成集合 Ai .任取合作过的数

, Card ( A2 ) ? 1327 , Card ( A1 ? A2 ) ? 1990 . 得: 学家 v1 , v2 ,由 Card ( A1 ) ? 1327 Card ( A1 ? A2 ) ? Card ( A1 ) ? Card ( A2 ) ? Card ( A1 ? A2 ) ? 1327? 2 ? 1990? 0.
从而存在数学家 v3 ? A1 ? A2 且 v3 ? v1 , v3 ? v2 . 又 Card ( A1 ? A2 ? A3 ) ? Card ( A1 ? A2 ) ? Card ( A3 ) ? Card[( A1 ? A2 ) ? A3 ]

2

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

? (1327? 2 ? 1990 ) ? 1327? 1990? 1.
从而存在数学家 v4 ? A1 ? A2 ? A3 且 v4 ? v3 , v4 ? v2 , v4 ? v1 ,从而可知 v1 , v2 , v3 , v4 两两合 作过. 〖说明〗本题的实质是证明 A1 ? A2 ? A3 ? ? ,通过容斥原理的计算来完成. 【例 3】称有限集 S 的所有元素的乘积为 S 的“积数”.给定数集 M ? { , , ? , M 的所有含偶数个元素的子集的“积数”之和.

1 1 2 3

1 }. 求数集 100

1 1 1 )(1 ? ) ? (1 ? ) ? 1. 设数集 M 的所有含 2 3 100 偶数个元素的子集的积数和为 x ,所有含奇数个元素的个子集的积数之和为 y ,则 x ? y ? 1 1 1 (1 ? )(1 ? ) ? (1 ? ) ? 1. 只需再建立一个关于 x, y 的方程,就可解出 x, y. 2 3 100
〖分析〗 数集 M 的所有子集的积数之和为 (1 ? 【解】设数集 M 的所有含偶数个元素的子集的积数之和为 x ,所有含奇数个元素的子集的

1 1 1 )(1 ? ) ? (1 ? ) ? 1. 2 3 100 1 1 1 ) ? 1. 又 x ? y ? (1 ? )(1 ? ) ? (1 ? 2 3 100 99 99 4851 ,x? y ? ? . . 所以 x ? y ? 解得 x ? 2 100 200
积数之和为 y ,则 x ? y ? (1 ? 【例 4】设集合 A ? {( x, y) | y ? a | x |}, B ? {( x, y) | y ? x ? a} ,若 Crad ( A ? B) ? 2 ,求 实数 a 的取值范围. 【解】当 a ? 0 时,画出草图,如图.由图可知当且仅当
y ? a | x | (a ? 0)
y

a ? 1 时, 直线 y ? x ? a 与两条射线 y ? a | x | 有两个交
点,即 A ? B 仅有两个元素;当 a ? 0 时,同理可得当 A ? B 有两个元素.从而实数 a 的取值 且仅当 a ? ?1 时, 范围为 | a |? 1.
O

y ? x ? a(a ? 0) y ? x ? a(a ? 0)

x

【例 5】有 1987 个集合,每个集合有 45 个元素,任意两个任意的并集有 89 个元素,问此 1987 个集合的并集有多少个元素? 〖分析〗由每个集合有 45 个元素,且任意两个集合的并集有 89 个元素知,任意两个集合有 且只有一元素. 【解】显然可以由题设找到这样的 1987 个集合,它们都含有一个公共元素 a ,而且每个两 个集合不含 a 以外的公共元素. 下面我们来排除其它可能性: 由任意两个集合的并集有 89 个元素可知,1987 个集合中的任意两个集合有且只有一外公共 元素,则容易证是这 1987 个集合中必有一个集合 A 中的元素 a 出现在 A 以外的 45 个集合 中,设 A1 , A2 ,?, A45 ,其余的设为 A46 , A47 ,?, A1986 . 设 B 为 A46 , A47 ,?, A1986 . 中的任意一个集合,且 a ? B ,由题设 B 和 A, A1 , A2 ,?, A45 都有
3

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

一个公共元素,且此 46 个元素各不相同,故 B 中有 46 个元素,与题设矛盾!所以这 1987 个集合 中都含有 a . 故所求的结果为 1987× 44+1=87429,即这 1987 个集合的并集有 87429 个元素. 〖说明〗这里我们先设计一种符合题设的特殊情形,然后再排除其可能的情形,从而达到解题 的目的,这是一种“先猜后证”的解题策略,应注意加以强化. 【例 6】怎样证明集合 S ? {a1 , a2 ,?, an } 的全体子集的个数为 2 .
n

〖分析〗 本题限定利用一一映射的知识加以解决, 因此首先应建立一个集合 S 与其到自然数 子集 {0,1,?,2n ? 1}间的一一映射. 【证明】将集合 S 的每一个子集合 {ai1 , ai2 ,?, aim }(1 ? i1 ? i2 ? ?im ? n,0 ? m ? n) 与一个 二进制数 (bi1 bi2 ?bim )2 相对应,使得 bi1 ? bi2 ? ?bim ? 1 ,而其余的 bk ? 0(k ? i1 , i2 ,?im ) . 在这种对应下,空集 ? 映射于 (00?0) 2 ? 0 ,而全集映射于 (11?1) 2 = 2 ? 1 ,其余的子集
n

合映射于 (00?0) 2 与 (11?1) 2 之间的某一个确定的二进制数,容易验证这种映射是从 S 的 全体子集到自然数的子集 {0,1,?,2n ? 1} 间的一一映射,所以子集合的个数为 2 .
n

〖说明〗 本题将集合中的元素与自然数集建立起了一种一一映射, 这种建立一一映射的方法 在竞赛中是常用的 . 这个问题也可以这样来解决,子集合中元素个数为 k 的子集合个数是
k Cn (k ? 0,1,2,?, n) ,所以全体子集的个数是,并且这种方法也是常见的证法.

【例 7】如图所示,将 8× 8 的国际象棋棋盘的左上角和右下角都剪去一个方格,问剪去两角 的棋盘能否用 31 个 1× 2 的矩形完全覆盖? 〖分析〗如果将问题改为能否用 32 个 1× 2 的矩形将 8× 8 的国 际象棋棋盘完全覆盖, 这将一个十分容易的问题, 可以找到很 多种方法.但是要注意这种不同的完全覆盖的方法的个数却是 一个十分困难的问题.M· E· Fischer 于 1961 年处出了这个数字 等于 12988816=24× 9012. 但是能过尝试可以发现, 要找到一个 将剪去两个角的国际象棋棋盘完全覆盖的方法却是十分困难 的.虽然剪去两个角的棋盘和原来的棋盘相差 “不大”,然而前 者却不能完全覆盖不定期个问题用一一映射的概念就可以迎 刃而解了. 【解】首先我们注意到一个 1× 2 的矩形,不论用什么样的覆盖方法,它必覆盖住棋盘的一 个黑格与一个白格.假定能用某种方法用 31 个 1× 2 的矩形完全覆盖, 那么这种覆盖方法实质 上就是在剪过的棋盘上的黑格和白格之间建立了一个一一映射.这说明剪过的棋盘上的黑格 和白格是一样多的.然而,实际上剪过的棋盘上还有 32 个黑格和 30 个白格.这一矛盾说明不 能用 1× 2 的矩形将剪过的棋盘完全覆盖. 〖说明〗本题与上节的例 1 一样,也是利用一一映射处理问题,这种处理方法在数学竞赛中 是最常用的方法之一,应重点掌握. 【例 8】集合 A 和 B 分别由适合如下条件的所有五倍数构成:对于集合 A 中的每一个数, 其各位数字之和或者加 1 或者减 1 之后是 5 的倍数;对于集合 B 中的每一个数,其各位数
4

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

字之和或者是 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. ? ? ? A .因此对应 ? ? 109999 ? ? 是 A、B 之间的一一 反之,设 ? ? B ,则 ? ? 109999
对应,从而 Card ( A) ? Card ( B). 〖说明〗建立一一映射证明两集合的个数相同,是奥林匹克数学竞赛中常用的方法,应重点 掌握.

} 的子集, 【例 9】 设 A1 , A2, 且 Card ( Ai ) ? 660 ( i ? 1,2, ?,30 ) . ?,A30 是集合 {1,2,?,2003
求证:存在 i ? j, i, j ?{1,2, ?,30} ,使得 Card( Ai ? Aj ) ? 203 . 【证明】不妨设每一个 Ai 的元素都为 660 个(否则去掉一些元素).作一个集合、元素的关 系表:表中每一行(除最上面的一行外)分别表示 30 个集合 A1 , A2, ?,A30 ,表的 n 列(最 左边的一列除外) 分别表示 2003 个元素 1, 2, ……, 2003.若 i ? Aj (i ? 1,2,?,2003 ,1 ? j ? 30) , 则在 i 所在的列与 Aj 所在行的交叉处写上下班 1,若 i ? Aj ,则在交叉处写上 0.如下表: 1 A1 A2 …… A30 × × × × 2 × × × × 3 × × × × … … … … … 2003 × × × ×

表中每一行有 660 个别,因此共有 30× 660 个 1.设第 j 列有 m j 个 1( j ? 1,2, ?,2003) ,则
2003



?m
j ?1 2 mj

j

2 个 交 集 As ? At , 因 此 , ? 30 ? 660. 由 于 是 每 个 元 素 j 属 于 C m j

2003 j ?1

?C

?

1?s?t ?30

? Crad( A
2003 j ?1

s

? At ). 1 2003 2 (? m j ? 2 j ?1
2003 j ?1

由柯西不等式

2 ? ? Cm j

? mj ) ?

2003 1 1 2003 ( ( ? m j ) ? ? m j )2 2 2003 j ?1 j ?1

5

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著









i? j







Card ( Ai ? A j ) ?

2003 1 2003 660 (30 ? 660 ? 2003 ) 1 1 ( ? 202 , ? ( m ) ? m j )2 = ? ? j 2 29 ? 2003 C30 2 2003 j ?1 j ?1

所以 Card( Ai ? Aj ) ? 203 . 〖说明〗本题中所作的表,称为元素、集合的从属关系表,它在讨论涉及多个集合的问题时 经常采用. 【例 10】 (首届东南地区竞赛) n 支球队要举行主客场双循环比赛(每两支球队比赛两场, 各有一场主场比赛) ,每支球队在一周(从周日到周六的七天)内可以进行多场客场比赛 . 但是如果一周内某球队有主场比赛,在这一周内不能安排该球队的客场比赛.如果 4 周内能 够完成全部比赛,求 n 的最大值.(注:A、B 两队在 A 方场地举行的比赛,称为 A 的主场比 赛,B 的客场比赛.) 【解】如下表所示:表格中的“*”表示该球队在该周有主场比赛,不能出访.容易验证,按表 中的安排,6 支球队四周内可以完成比赛. 球队 1 2 3 4 5 6 第一周 * * * 第二周 * * * * * * * * * 第三周 第四周

下面证明 7 支球队不能在四周内完成比赛.设 Si (i ? 1,2,3,4,5,6,7) 表示 i 号球队的主场比赛 周次的集合.假设 4 周内能完成比赛,则 S i 是{1,2,3,4}的非空真子集. 一方面由于某周内该队有主场比赛,在这一周内不能安排该球的客场比赛,所以

Si (i ? 1,2,3,4,5,6,7) 中,没有一个集合是另外一个集合的子集.
另一方面,设 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}, Si , S j 属于同一集合 A 或 B 或 C 或 D 或 E
或 F,必有 Si ? S j 或 Si ? S j 发生. 所以 n 的最大值是 6. 〖说明〗本题是例 9 的深入延伸,先能过表格得出一个确定的值,再证明大于(小于)这个 数的不能成立,这是求解最值问题的常用方法. 【例 11】 (1992 年全国高中数学联赛)设集合 Sn ? {1,2,?, n} .若 X 是 Sn 的子集,把 X 中 的所有数的和称为 X 的“容量”(规定空集的容量为 0).若 X 的容量为奇(偶)数,则称 X 为 Sn 的奇(偶)子集. (1)求证: Sn 的奇子集与偶子集的个数相等.

6

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

(2)求证:当 n ? 3 时, Sn 的所有奇子集的容量之和与所有偶子集的容量之和相等. (3)当 n ? 3 时,求出 Sn 的所有奇子集的容量之和. 〖分析〗要证明两个集合的元素一样多,一种方法是直接将两个集合中的元素个数算出来, 另外一种方法是在这两个集合之间建立一个一一映射.这里我们采用第二种方法解决. 【解】(1)设 A 是 Sn 的任一奇子集,构造映射 f 如下:

A ? A ? {1} ,若 1 ? A ; A ? A ? {1} ,若 1 ? A .
(注: A ? {1} 表示从集合 A 中去掉 1 后的集合)所以映射 f 是将奇子集映为偶子集的映射. 易知,若 A1 , A2 是 Sn 的两个不同的奇子集,则 f ( A1 ) ? f ( A2 ) ,即 f 为单射. 又对 Sn 的每一个偶子集 B,若 1 ? B ,则存在 A ? B \ {1} ,使得 f ( A) ? B ; 若 1 ? B ,则存在 A ? B ? {1} ,使得 f ( A) ? B ,从而 f 是满射. 所以 f 是使得 Sn 的奇子集的组成的集到 Sn 的偶子集所组成的集之间的一一对应,从而 Sn 的奇子集与偶子集的个数相等,故均为

1 n ? 2 ? 2 n?1 个. 2

(2)设 an (bn ) 表示 Sn 中全体奇(偶)子集容量之和. 若 n(? 3) 是奇数, 则 Sn 的奇子集由如下两类构成: ①S n?1 的奇子集; ②S n?1 的偶子集与集 {n} 的并,于是可得:

an ? an?1 ? (bn ? n ? 2n?2 )

(*)

又 Sn 的偶子集可由 S n?1 的偶子集和 S n?1 的偶子集与集 {n} 的并构成,所以:

bn ? bn?1 ? (an ? n ? 2n?2 )
由(*) 、 (**)便可得 an ? bn . 若 n(? 4) 是偶数,同上可知:

(**)

an ? an?1 ? (an?1 ? n ? 2n?2 ) bn ? bn?1 ? (bn?1 ? n ? 2n?2 )
由于 n ? 1 是奇数,由上面已证 an?1 ? bn?1 ,从而 an ? bn .
7

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

综上即知, an ? bn (n ? 2,3,?). (3)由于 Sn 的每一个元素均在 2
n ?1

个子集 Sn 中出现,所以 Sn 的所有子集容量之和为

2n?1 (1 ? 2 ? ? ? n) ? 2n?2 n(n ? 1)
又由(2)知 an ? bn ,所以 an ?

1 n?2 ? 2 n(n ? 1) ? 2 n?3 n(n ? 1). 2

〖说明〗对于第(2)小题的证明,建立了递推关系,这是解决“计数”问题的一个有效的方 法.

}的恰有 101 个元素的子集. 【例 12】 (2003 年 IOM 试题)设 A 是集合 S ? {1,2, ?,1000000
证明:在 S 中存在数 t1 , t2 ,?, t100 ,使得 Aj ? {x ? t j | x ? A}, j ? 1,2,?,100中,每两个的 交集为空集. 〖分析〗先弄清在什么情况下 Ai ? Aj ? ? .设 a ? Ai ? Aj ,则 a ? x ? ti ? y ? t j , x, y ? A. 于 是 ti ? t j ? y ? x .这说明选取 t1 , t2 ,?, t100 时,只要保证其中任意两个之差不等于 A 中任二 元素之差即可.

. 【解】考虑集合 D ? {x ? y | x, y ? A} ,则 Crad (d ) ? 101? 100? 1 ? 10101
若 Ai ? Aj ? ? , 设 a ? Ai ? Aj , 则 a ? x ? ti , a ? y ? t j , 其中 x, y ? A , 则 ti ? t j ? y ? x ? D . 若 ti ? t j ? D ,即存在 x, y ? A ,使得 ti ? t j ? y ? x ,从而 x ? ti ? y ? t j ,即 Ai ? Aj ? ? . 所以 Ai ? Aj ? ? 的充要条件是 ti ? t j ? D .于是我们只需在集合 S 中取出其 100 个元素, 使 得其中任意的两个的差都不属于 D. 下面用递推的方法来取出这 100 个元素. 先在 S 中任取一个元素 t1 ,再从 S 中取一个元素 t 2 , 使得 t1 ? t2 ? D ? {t2 ? x | x ? D}. 这是 因为取定 t1 后,至多有 10101 个 S 中的元素都不能作为 t 2 ,从而在 S 中存在这样的 t 2 . 若已有 k (? 99) 个 S 中的元素 t1 , t2 ,?, tk 满足要求,再取 tk ?1 , 使得 t1 , t2 ,?, tk 都不属于

tk ?1 ? D ? {tk ?1 ? x | x ? D}. 这是因为 t1 , t2 ,?, tk 取定以后,至多有 10101 k ? 999999 个 S
中的数不能作为 tk ?1 , 故在 S 中存在满足条件的 t k ?1 .所在在 S 中存在 t1 , t2 ,?, t100 ,其中任意 两个的差都不属于 D. 综上所述,命题得证. 〖说明〗条件 Card (S ) ? 10 可以改小一些.一般地,我们有如下更强的结论:
6

8

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

2 若 A 是 S={1,2,3,……,n}的一个 k 元子集,m 为正整数,满足条件 n>(m-1)( Ck ? 1 ),

则存在S中的元素 t1 , t 2 , ?, t m ,使得 Aj ? {x ? t j | x ? A}, j ? 1,2,?, m 中任意两个的交集 为空集.这个结论是可以证明的,请读者自已试证之(见B组习题6).

【赛向点拨】
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

3.(2002 年全国高中数学赛)已知两个实数集合 A={a1,a2,…,a100}与 B={b1,b2,…,b50}, 若从 A 到 B 的映射 f 使得 B 中每个元素都有原象,且 f(a1)≤f(a2)≤…≤f(a100)则这样的映射共 有( )个. A.C50100 B.C4899 C.C49100 D.C4999

2 4.设 f ( x) ? x ? x ? 2, A ? {n | 1 ? n ? n, n ? Z} , B ? { y | y ? f (n), n ? A} ,则集合

B ? {2m | m ? Z} 的元素的个数是(
A.100 B.51 C.36

) D.以上都不对

5. (2007 年江西预赛)正整数集合 Ak 的最小元素为 1 ,最大元素为 2007 ,并且各元素可以 从小到大排成一个公差为 k 的等差数列,则并集 A17 A. 119 B. 120 ; C. 151 ; D. 154 .

A59 中的元素个数为(

) .

6.某班有 50 人,开设英语和日语两种外语.现规定每人至少选学一门,估计报英语的人数

9

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

占全班总人数的 80%~90%之间,报日语的人数占全班总人数的 32%~40%之间.设 M 是两门 都学的人数的最大值,m 是两门都学的人数的最小值,则 M-m= .

7.已知集合 M ? {x | x ? 2n ,0 ? n ? 1000 , n ? Z} ,把 M 中最高位数字是 1 的数全部抽出 出来,组成一个新的集合 S,则 S 中的元素共有 个( lg 2 ? 0.3010).

8.已知映射 f : A ? B ,其中集合 A ? {?3,?2,?1,1,2,3,4} ,其中集合中的元素都是 A 中 元素在映射 f 下的象,且对任意 a ? A, 在 B 中,和对应的元素是 | a | ,则集合 B 中的元素 的个数是 .

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 中任何一个整数整除的整数的个数. 12. n 个点 r1 , r2, ?, rn 顺次排在同一条直线上, 每个点涂上黑色或白色.已知 r1 和 rn 分别涂上 了白色和黑色.求证:相邻点间线段不同色的个数一定是奇数.

(B 组)
1.设 A ? A1 ? A2 ? ? ? Am , R ? {A1 , A2 ,?, Am }, 若 R 中每 r 个元素的交集不空, 而 r ?1个 元素的交集为空集,则: (1) Card ( A) 至少是多少? (2)当 Card ( A) 最小时, Card( Ai ) 为多少? 2.设 Z 是平面上由 n(? 3) 个点组成的点数, 其中任三点不共线, 又设自然数 k 满足不等式

n ? 2

k ? n. 如果 Z 中的每个点都至少与 Z 中的 k 个点有线段相连, 证明: 这些线段中一定有三条
线段构成三角形的三边. 3. (2005 年北方数学奥林匹克数学邀请赛)已知 n 位数的各位数字只能取集合 ?1,2,3,4,5? 中 的元素,设含有数字5且在5的前面不含3的 n 位数个数为 f ? n ? ,求 f ? n ? . 4.对于任何的集合 S,设 n( S ) 为集合 S 的子集的个数.如果 A、B、C 是三集合,满足下列条

10

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

件: (1) n( A) ? n( B) ? n(C ) ? n( A ? B ? C ) ; (2) Card ( A) ? Card ( B) ? 100. 求 Card ( A ? B ? C ) 的最小值. 5.(2006 年山东省第二届夏令营试题)设 T 是由 60
100

的所有的正因数组成的集合,S 是 T

的一个子集,其中没有一个数是另一个数的倍数,求 Card ( S ) 的最大值.
2 6. 若 A 是 S={1, 2, 3, ……, n}的一个 k 元子集, m 为正整数, 满足条件 n>(m-1)( Ck ? 1 ),

则存在S中的元素 t1 , t 2 , ?, t m ,使得 Aj ? {x ? t j | x ? A}, j ? 1,2,?, m 中任意两个的交集 为空集.

【参考答案】
(A 组) 1.解:设班级人数为 100,则两门学科中至少有一门优秀的总人数不大于 100. 由 Card ( A ? B) ? Card ( A) ? Card ( B) ? Card ( A ? B) , 可得 70+75- Card ( A ? B) ? 100 ,即 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 的公共元素 组成的集合 G={4,6,7}的真子集,这样的集合 C 共有 2 ? 1 ? 7 个.
3

3. 解:不妨设 b1<b2<…<b50,将 A 中元素 a1,a2,…,a100 按顺序分为非空的 50 组。 定义映射 f:A→B,使第 i 组的元素在 f 之下的象都是 bi(i=1,2,…,50). 易知这样的 f 满足题设要求,每个这样的分组都一一对应满足条件的映射,于是满足题设 要求的映射 f 的个数与 A 按足码顺序分为 50 组的分法数相等,而 A 的分法数为 C4999,则这 样的映射共有 C4999,故选 D. 4.解:当 n ? A 时, y ? f (n) ? n ? n ? 2 恒为偶数.从而选 A.
2

0 0 7 1 ? ? nk , 5.解: 设 Card ( Ak ) ? n ? 1 , 由2 得n ?

Crad ( A59 ) ?

2006 ? 1 ? 35 , crad ( A17 59

2006 2006 ? 1 ? 119 , , 于是 Crad ( A17 ) ? 17 k 2006 A59 ) ? Crad ( A1003 ) ? ?1 ? 3; 17 ? 59

从而 Crad ( A 17 选 C.

A59 ) ? Crad( A 17 ) ? Crad( A 59 ) ? Crad( A 1003 ) ? 119 ? 35 ? 3 ? 151.故应

11

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

6. 解 : 设 集 合 A={ 报 英 语 的 同 学 } , 集 合 B={ 报 日 语 的 同 学 } , 则 由 题 可 知 50× 80% ? Card ( A) ? 50× 90%,即 40 ? Card ( A) ? 45. 同理, 16 ? Card ( B) ? 20 ,从而 40 ? 16 ? 50 ? Card ( A ? B) ? 45 ? 20 ? 50, 即 6 ? Card ( A ? B) ? 15 ,所以 M ? 15, m ? 6 ,所以 M-m=9. 7 . 解 : 令 10 ? 2 ? 2 ? 10 , 则 有
k n k

k k , 于 是 k ? 0,1,2, ?,301 且 使 得 ? n ? 1? lg 2 lg 2

0 ? n ? 1000 ,从而可以计算得 S 的个数为 302.
8.解:依题意,由 A ? B 的对应法则 f : a ?| a | . 于是,将集合 A 中的 7 个不同的元素分 别取绝对值后依次得 3,2,1,1,2,3,4.由集合元素的互异性可知 B ? {1,2,3,4} ,它有 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 个“魔 幻数” ,M 的不含“魔幻数”的子集 N 共有 2000 ? 118 ? 1882 个.

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

由公式② 得 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 整除的整

12

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

数集合.则 Card ( A) ? ?

? 250? ? 250? ? 125, Card ( B) ? ? ? 83, ? ? 2 ? ? 3 ? ?

? 250? ? 250? Card (C ) ? ? ? 50, Card ( D) ? ? ? 35. ? ? 5 ? ? 7 ? ? ? 250 ? ? 250 ? ? 250 ? Card ( A ? B) ? ? ? 41, Card ( A ? C ) ? ? ? 25, Card ( A ? D) ? ? ? 17, ? ? ? 2 ? 3? ? 2 ? 5? ?2? 7? ? ? 250 ? ? 250 ? ? 250 ? Card ( B ? C ) ? ? ? 16, Card ( B ? D) ? ? ? 11, Card (C ? D) ? ? ? 7. ? ? ?3 ? 5? ?5 ? 7 ? ? ?3 ? 7 ? ? 250 ? ? 250 ? Card ( A ? B ? C ) ? ? ? 8, Card ( A ? B ? D) ? ? ? 5, ? ? 2 ? 3 ? 5? ? 2 ? 3? 7 ? ? ? 250 ? ? 250 ? Card ( A ? C ? D) ? ? ? 3, Card ( B ? C ? D) ? ? ? 2, ? ? 2? 5? 7 ? ?3? 5 ? 7 ? ? ? 250 ? Card ( A ? B ? C ? D) ? ? ? 1. (其中[x]表示不超过 x 的最大整数) ? 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 (C ? D) ? Card( A ? B ? C) ? Card ( A ? B ? D) ? Card ( A ? C ? D) ? Card ( B ? C ? D) ? Card ( A ? B ? C ? D) ? 193.
12.证明:在集合{黑色,白色}和{1,-1}之间建立一个一一映射,使黑色映射到 1,白色映射到 -1,则每个顶点 ri 都映射到一个数 a i (i ? 1,2, ?, n) .设线段 ri ri?1 两端点不同色, 则 ai ai ?1 =-1.设两点不同色的线段的个数为 k ,从下式
2 2 2 -1= a1an ? a1a2 a3 ?an )k ?1an ? (a1a2 )(a2 a3 ) ?(an?1an ) ? (?1

可得 k 为奇数. (B 组) 1.解:考虑下标集合 {1,2, ?, m} 的任一 r 元子集 {i1 , i2 ,?, ir } 在 Ai1 ? Ai2 ? ?? Air 中任取 一个元素 a ,这就建立了从下标 {i1 , i2 ,?, ir } 到元素 a 的一个映射,并且不同的原象其象也 不相同,否则不同的 {i1 , i2 ,?, ir } ,{ j1 , j2 , ?, jr } 对应同一个 a 时,必有 r ? 1 个子集不空,

13

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

r 与题设矛盾.这说明 Card( A) ? Cm .

(2)考虑任一 Ai ,在 R 中任取其余 r 个集合,它们的交集至少有一个元素(不空) ,而此
r 交集与 Ai 的交集为 ? , 所以 A ? A1 ? A2 ? ? Ai?1 ? Ai?1 ? ? ? Am 中至少含有 A 中的 Cm ?1 个不 r 同的元素,有 Card( Ai ) ? Card( A) ? Cm ?1. r r r r r ?1 而当 Card ( A) ? Cm 时, Card( Ai ) ? Card( A) ? Cm ?1 ? Cm ? Cm?1 ? Cm?1.



r ?1 另一方面, Ai 与 R 中任选 r ? 1 个其余的集相交,至少有一个元素,有 Cm ?1 种不同的取法, r ?1 r ?1 可知 Ai 至少有 Cm i ) ? Cm?1. ?1 个不同的元素, Card ( A r ?1 由①②可得 Card( Ai ) ? Cm ?1.



2.证明:因为 k ?

n 3 ? ,所以 k ? 2 ,即每个点都至少与 Z 中 2 个点有线段相连.不妨高 2 2

N ? {P | P ? Z , P 设 AB 为 Z 中点连成的线段.令 M ? {P | P ? Z , P 与 A 有线段相连 } ? {B} ,
与 B 有线段相连 } ? { A} . 由于 Z 中任一点至少引出 k 条直线,所以有 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.
所以 M ? N ? ? ,即存在点 C ? M ,且 C ? N (C ? A, C ? B). 显然线段 AB、AC、BC 构成三角形的三边. 3.解:对于满足条件的 n+1 位数的个数 f (n ? 1) 的计算,可分为如下两种情况: 情形 1:当个位数字不是 5 时,则前 n 位数中一定含有数字 5,它是满足条件的一个 n 位数, 其个数为 f ( n). 对于每一个这样的 n 位数,从 1、2、3、4 中任取一个放在它的最右端,可 得一个 n ? 1 位数,因此个位数字不是 5 的 n ? 1 位数是 4 f (n) 个. 情形 2:当个位数字是 5 时,由于在 5 的前面不能含有 3,则前 n 位数字的每一位数字均为 4 种取法,因此个数字是 5 的 n ? 1 位数共有 4 个.所以 f (n ? 1) ? 4 f (n) ? 4 ,
n

n

14

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

f ( n ? 1) f ( n) ? n?1 ? 1 ,显然 f (1) ? 1. 4n 4 f ( n) 则 n?1 ? 1 ? ( n ? 1) ? n ,故 f (n) ? n ? 4n?1. 4
即 4.解:如果一个集合有 k 个元素,那么它有 2 个子集.由题设有
k

2100 ? 2100 ? 2Card( C) ? 2Crad( A?B?C) ,即 1 ? 2Card(C)?101 ? 2Card( A?B?C)?101.
因为 1 ? 2
Card ( C ) ?101

是大不动声色 1 且等于一个性的整数幂,所以 Card (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?C 、 A ? C ? A ? B ? C 得 Card ( A ? B), Card ( A ? C ), Card ( B ? C ) ? 102, 由 A? B、
所以 Card ( A ? B ? C ) ? 403? 102? 3 ? 97.

}, B ? {3,4,5,?,102 }, C ? {1,2,4,5,6,?,100,101 ,102 } ,满 另一个方面,取 A ? {1,2, ?,100 }) ? 97. 足题设条件.这时 Card ( A ? B ? C ) ? Crad ({4,5,6, ?,100
所以 Card ( A ? B ? C ) 的最小值为 97.
a b c 5.解:? 60 ? 2 ? 3 ? 5 ,?T ? {2 3 5 | 0 ? a ? 200 ,0 ? b, c ? 100, a, b, c ? Z}
2

设 S ? {2

200?b?c b c

3 5 | 0 ? b, c ? 100, b, c ? Z}
200 ?b1 ?c1 b1 c1

若 u, v ? S , u | v ,设 u ? 2

3 5 , v ? 2200?b2 ?c2 3b2 5c2

?200 ? b1 ? c1 ? 200 ? b2 ? c2 ? b1 ? b2 由u | v 知? ,从而 b1 ? b2 , c1 ? c2 ,即 u ? v 矛盾! ? c1 ? c2 ?
故 S 中没有一个元素是另一个元素的倍数,?Card(S ) ? 101 .
2

下证:若 T 的一个子集 S ? 的元素个数 101 ,则 S ? 中一定有一个元素是另一个元素的倍数.
2

因为 Card ( S ?) ? 101 ,所以考虑 3 和 5 的指数对 (b, c ) ,一定有两个元素是相同的.
2

15

高中数学新课标奥林匹克竞赛辅导讲义(高一部分)

贾广素

编著

不妨设 u ? 2m ? 3i ? 5 j , v ? 2n ? 3i ? 5 j. 当 m ? n 时, u | v ;当 m ? n 时, v | u. 综上所述,所求的 Card ( S ) 的最大值为 101 .
2 6.解:考虑集合 B ? {| x ? y || x, y ? A} ,显然, Card( B) ? Ck ? 1.
2

下证存在 t1 , t2 ,?, tm ? S ,使得对 i ? j ,有 | ti ? t j |? B.. 我们递归地构造 t1 , t 2 , ?, t m .
2 取 t1 ? 1 ,令 c1 ? S \ ( B ? t1 ) ,则有: Card(c1 ) ? n ? (Ck ? 1) ? (m ? 2)(Ck2 ? 1). 2 对1 ? i ? m , 假定 t1 , t2 , ?, ti 和 c i 已经选定, 且 Card(c1 ) ? (m ? i ? 1)(Ck 取 ci 中 ? 1) ? 0 ,

的最小元素为 ti ?1 ,考虑集合 ci?1 ? ci \ ( B ? ti?1 ) ,则有

Card(ci?1 ) ? Card(ci ) ? (Ck2 ? 1) ? (m ? i ? 2)(Ck2 ? 1) ? 0 ,
显然 t1 , t 2 , ?, t m 满足要求. 注:题中 B ? t1 表示集合 {b ? t1 | b ? B}.

16


推荐相关:

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

第二节 映射与有限集合元素的个数_数学_高中教育_教育专区。高中数学新课标奥林匹克竞赛辅导讲义(高一部分) 贾广素 编著 第二节 映射与有限集合的元素的个数数学...


奥数培训映射运算(学生版)

2014 级奥数培训学案 第三讲【基础知识】 1.映射的定义 映射映射法 (1)设集合 A 有 m 个元素,集合 B 有 n 个元素,那么映射 f : A ? B 的个数为 ...


有关映射个数问题的求法

一、一般型映射的计数问题 这类问题是指课本中介绍的映射知识, 这类问题常涉及求元素个数集合个数映射个数等,较简单的可用枚举法、图表法、分类讨论法,...


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

有限集元素的数目 1.有限集的阶 有限集 A 的元素...特别当 X 和 Y 都是数集时, 映射 f 称为函数...惟一的不同在于这时第二个集合 {k ? 1, k ? ...


第14讲:映射个数问题探究

第二问因象的大小有具体要 求,为了使问题简化可选择一个分类标准逐层求解。 ...(1)对映射定义的理解:①映射集合的元素是任意的,可以是数、可以是点、可以...


映射的计数问题(经典)

这类问题常涉及有求元素个数集合个数映射个数等, 较简单的可用枚举法、...因为若 Ai 是第二 类的,则必有 Ai∪{2001}是第一类的集合;如果 Bi 是第...


题目5bf2b6f67c1cfad6195fa71f

单选题 数学 函数、映射的概念 设集合A和集合B都是自然数集N,映射f:A→B把集合A中的元素n映射集合B中的元素n2+n,则在映射f下,像20的原像是( ) A2...


题目3c0557eef8c75fbfc77db21c

单选题 数学 函数、映射的概念 设集合A和集合B都是自然数集N,映射f:A→B把集合A中的元素n映射集合B中的元素n2+n,则在映射f下,像20的原像是( ) A2...


排列组合中的映射问题

根据映射的定义,当集合 A,B 中的元素个数不只有一个时不同的对应会构成不同...的映射,A 中 4 元都对应 B 中的第二元素构成一个 A → B 的映射, (...


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

数学奥赛辅导 第二讲 整除 数学奥赛辅导 第三讲 同余...有限集的有限集 A 的元素数目叫做这个集合的阶...特别当 X 和 Y 都是数集时, 映射 f 称为函数...

网站首页 | 网站地图
All rights reserved Powered by 酷我资料网 koorio.com
copyright ©right 2014-2019。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com