nbhkdz.com冰点文库

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


高中数学奥赛讲义:

映射与计数在解竞赛题中的应用
【内容综述】 利用映射来解决计数问题,就是通过建立集合 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 的个数为 。

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


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

高中数学奥赛系列辅导资料... 暂无评价 6页 2财富...映射及其性质,这些在与计数有关的数学竞赛问题 中...【解】显然,可以由题设找到这样的 1987 个集合,...

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

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

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

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

(本小题满分14分)某工厂统计资料显示,一种产品次品率与...

简答题 数学 函数、映射的概念 (本小题满分14分)某工厂统计资料显示,一种产品次品率与日产量件之间的关系如下表所示: 其中(为常数).已知生产一件正品盈利元,...

高中数学专题01:集合、映射、简易逻辑与函数

及其应用,属中、高档题; (3) 考查以函数为模型的实际应用题,让考生从数学...充分条件与必要条件与三角、立几、解几中的知识点的结合等) 映射的概 念以...

...数学·必修1(苏教版)习题:第2章2.3映射的概念 Word...

答案:D数学学习资料 数学学习资料 3.已知集合 A 中元素(x、y)在映射 f 下...解:(1)A 中元素(1,2),即当 x=1,y=2 时, 3x-2y+1=3×1-2×2+1...

...计算利息,若本金为元,每期利率_答案_百度高考

简答题 数学 函数、映射的概念 (本题满分14分)某种储蓄按复利(把前一期的利息本金加在一起作本金,再计算下一期的利息)计算利息,若本金为元,每期利率为,设...

...映射f满足条件:对M中的每个元素x与它在N中的_答案_百度高考...

教育频道 小学教育 初中教育 高中教育 专业资料 ...简答题 数学 函数、映射的概念 设集合M={-1,0...它们在N中的象只能为偶数-2、0或2,由分步计数...

...f:A→B把集合A中的元素(x,y)映射成集合B中的_答案_百度高考...

填空题 数学 函数、映射的概念 设集合A和B都是坐标平面上的点集{(x,y)|x∈R,y∈R},映射f:A→B把集合A中的元素(x,y)映射成集合B中的元素(x+y,x-...

从A={a1,a2,a3,a4}到B={b1,b2,b3,b4}的一一映射中,限定...

单选题 数学 函数、映射的概念、分类加法计数原理、分步乘法计数原理 从A={a1,a2,a3,a4}到B={b1,b2,b3,b4}的一一映射中,限定a1的象不能是b1,且b4的原...