nbhkdz.com冰点文库

高中数学奥赛讲义:映射与计数在解竞赛题中的应用

时间:2012-07-25


高中数学奥赛讲义:

映射与计数在解竞赛题中的应用
【内容综述】 利用映射来解决计数问题,就是通过建立集合 A 与另一集合 B 之间的映射,把对集合 A 的计数转移到对集合 B 的计数。实现这种转移的关键是: (1)选择适当的便于计数的集合; (2)建立集合间的映射关系。 设 f: 是集合 A 到集合 B 上的映射,那么 。 。 。

/>(1)若 f 为单射,则 (2)若 f 为满射,则 (3)若 f 为一一映射,则 【例题分析】 例 1 从 里

的棋盘中,取出一个由三个小方格组成的 L 形,有多少种不同取法?这

棋盘是指 m 条横线与 n 条竖线所构成的棋盘。

解 每种取法,都有一个点与它对应,这个点就是所取 L 形中三个小方格的公共点(如 图 1),它是棋盘上横线与竖线的交点,且不在棋盘的边界上。从图 2 可看出,每个点对应 于 4 种不同取法,这 4 种取法构成一个“田”字形。而每个“田”字形都有唯一的中心。 (例如点 B),即映射 f:“田”字形→“田”字形中心,是棋盘上由小方格组成的“田” 字集合到棋盘内横线与竖线的交点集(不包括边界上的点)的一一映射。 显然棋盘内横线与竖线的交点有 种不同取法。 例 2 求 n 元集合 A 的所有子集的个数 解 设集合 A 的所有子集的集合为 P(A),B 为集合 A 到集合 对于任意的 ,可唯一确定一个从集合 A 到集合 的映射 的全体映射的集合, 个,所以,共有



通常称为集合 M 的特征函数),即有唯一的 , 有唯一的集合

与 M 对应。 。 显然 ,

反过来, 对于任意的 且 就是 。因此,映射 f: 由于 n 元素集 A 到集合

是集合 P(A)到 B 的一一映射。 的映射的个数为 ,即 ,根据对应原理

? ? 说明 一般地, 集合 X ? { x 1, x 2, , x m } 到集合 y ? { y 1, y 2, , y m } 的所有映射的个

数为



例 3 中日围棋擂台赛,双方各派 6 名队员按预定顺序出场,直到最后一方取胜,问可 能出现的比赛过程种数有多少种? 解 设中国队员对应红球,日方队员对应白球。将被淘汰队员对应的球按被淘汰的时间 顺序一一排列出来。负方队员全部被淘汰,则相应球全部排出,然后将胜方所剩队员对应 的球依次排在后面。由于双方队员出场顺序已定,故可设同色球之间无区别,于是一种比 赛过程就对应于 6 个红球和 6 个白球的一种排列;反之,6 个红球和 6 个白球的一种排列对 应着一种比赛过程,即球的不同排列与不同比赛过程之间存在一一对应关系。6 个红球和 6 个白球的不同排列数为 ,此即所求比赛过程种数。

说明 在某种映射下,两个集合元素间一一对应,该映射即为一一映射,所以对于明显 的一一映射只须指出两集合间的一一对应关系,就可运用对应原理。 例 4 求 m 元方程 解法一 由于数组 的正整数解的组数。 中各数可以重复,且大小无序,因此作如下映射 :

显然 且

① 一一对应,所以,映射

是一一映射。 因为,满足①的数组有 个,所以所求方程解的组数为 。

解法二 考虑长度为 n 的线段 AB。方程的任一组解对应于把线段分成 m 节的一种分法,

其中第一节的长度为

,第二节的长度为

,?,第 m 节的长度为

,而每一种分法又对

应于线段长 n-1 个分点中取出 m-1 个分点的一种取法。反过来,线段 n-1 个分点中取出 m-1 个分点的任一种取法,都把线段 AB 分成 m 节。令 x i (1 ? i ? m ) 依次取 m 节的长度,就得到 方程的一组解。 所以, 原方程解的组数就是线段 AB 上 n-1 个分点中取出 m-1 个的不同取法的种数 说明 若把问题改为:求 m 元方程 ,则化为求方程 4 可知所求解的组数为 例 5 设 。 为 A 的三元子集,若满足 为 A 的“好子集”,求 A 的“好子集”的个数。 解 令 。

的非负整数解的组数,只要令 的正整数解的组数,由例





射 。

f 是



上的一一映射。事实上,当

时,

,那么

即 另 一 方 面 , 若

。 , , 。 则 即

于是由对应原理,

,即 A 的“好子集”有

个。 中存在 ,使

2 3, 2 例 6 设 n 为正整数,若 {1,, ? ,n } 的一个排列

成立,则称该排列具有性质 P。证明:具有性质 P 的排列比不具有性质 P 的排 列多。 证明 设 A 是由不具有性质 P 的排列构成的集合, 是恰有一对 B 满足

的排列构成的集合,C 是具有性质 P 的所有排列构成的集合,显然 设 ,其中必有一个 ,使

,从而



,于是调整 满足

的位置如下 ,从而 。

,该排列仅有一对相邻数

。上述调整构成了一个 A 到 B 的映射,因此, 又 ,故 例 7 ,即具有性质 P 的排列比不具有性质 P 的排列多。 已 知 ① 求 解 由②知 样的有序数组 如果 (1) (2) 将 统 统 改 变 符 号 , 这 一 对 的个数。 中有 n 个+1,n 个-1,这样的有序数组有 中有多少不符合①,设其个数为 。 不符合①,那么一定存在最小的自然数 s ( s ? n ) ,满足 ; , ② , 并



个。下面考虑这



改为 n+1 个+1, n-1 个-1 组成的有序数组。 反之,对于任何一个 n+1 个+1,n-1 个-1 组成的有序数组 -1,必然存在一个最小的自然数 s,满足 将 变为 。 , 就得到一个 n 个+1, ,由于+1 多于

n 个-1 组成的不符合①的有序数组,所以,f 是一一映射,由对应原理知 等于 n+1 个+1, n-1 个-1 组成的有序数组的个数,即 。

因此,符合题目条件的有序数组的个数为

例 8 已知数列

满足

。 对每一个整数 ,求满足条件

的下标 n 的个数。 解 将满足 的自然数 n 用二进制表示为 ,可以证明 ① ,这里

事实上,如果

为偶数,则

,均有

为偶数,且

;如果

为奇数,则

,均有

为奇数,且

所以①式成立。 反复利用①式可知 ② 上式右边为 k 个+1 或-1 的和。所以,当 k 为奇数时,②的右边为奇数,不会等于 0, 这表明,当 k 为奇数时,满足条件的下标 n 的个数为 0。

当 k 为偶数时,若 设

,则②式右边恰有 , n

个+1,

个-1。 , :

的 二 进 制 表 示 为 ,②式确定了一个 A 到 B 的映射 。

由 于

A

中 任 意 两 个 元 素 的 二 进 制 表 示 首 位 都 为 。并设 j 为使 。这说明 是 A 到 B 的单射。又易知

1 , 设

的最大下标。则 ,所以 又是 A

到 B 的满射,从而 是 A 到 B 的一一映射。

故满足 即 。

, 且

的下标 n 的个数为 B 中恰有

个-1 的有序数组的个数,

综上所述,当 为奇数时,满足条件的下标 n 的个数为 0;当 k 为偶数时,满足条件的 下标 n 的个数为 。

运用映射法解决计数问题,关键在于建立映射关系,将难于计数的集合化为易于计数 的集合来计数。这项工作具有较强的技巧性,需在平时学习中多体会,多实践。


高中数学竞赛讲义_函数

高中数学竞赛讲义_函数_学科竞赛_高中教育_教育专区。高中数学竞赛讲义 函数 一、基础知识 定义 1 映射,对于任意两个集合 A,B,依对应法则 f,若对 A 中的任意...

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

数学奥赛辅导 第六讲 集合与映射数学奥赛辅导 第六...这些在与计数有关的数学竞赛问题 中应用极广,是...【解】显然,可以由题设找到这样的 1987 个集合,...

映射的计数问题(经典)

映射的计数问题(经典)_高三数学_数学_高中教育_教育...(D). ) 解:由题意可知,A 中必有两个元素的象...一类的集合,则 Bi 中除 2001 外,还 应用 1,2,...

映射与函数习题

映射与函数习题_数学_高中教育_教育专区。广州至慧...(2,1)在A中的对应元素 解:(1)将 x= 2 代入...这是分类加法计数原理;完成一件事需要两个步骤,做...

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

高中数学新课标奥林匹克竞赛辅导讲义(高一部分) ...3.映射中的计数问题 (1)对于满射 f : A ? B ...【解】显然可以由题设找到这样的 1987 个集合,它们...

必修1映射典型习题(含答案)

必修1映射典型习题(含答案)_数学_高中教育_教育专区...中不同的方法,这是分类加法计数原理;完成一件事...1 各取一个. 解:∵ f (a) ? N ,?? f (...

6643高一数学映射与函数试题

高一数学同步测试(5)—映射与函数 一、选择题: 1.下列对应是从集合 A 到集合 B 的映射的是 A.A=R,B={x|x>0 且 x∈R},x∈A,f:x→|x| B.A=N...

高一数学《映射与函数》习题

高一数学映射与函数》习题_高一数学_数学_高中教育...中某一元素 a 的象可能不只一个 (C) A 中两...f [ g ( x)] = 0 有实数解,则 g[ f ( ...

高一数学《函数—映射与函数》测试题(含答案)[1]

高一数学《函数—映射与函数》测试题(含答案)[1]_数学_高中教育_教育专区。经典...解:?B 中元素 y ? 3x ? 1 和 A 中元素 x 对应,?A 中元素 1 的象...

映射练习题

映射练习题_高一数学_数学_高中教育_教育专区。武汉成就未来教育 映射一、选择题...武汉成就未来教育 映射一、选择题 1.下列表格中的 x 与 y 能构成函数的是(...