当前位置:首页 >> 学科竞赛 >>

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


高中数学奥赛讲义:

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

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


相关文章:
浅谈构造法解题在高中数学竞赛中的应用
浅谈构造法解题在高中数学竞赛中的应用苏 传忠 在数学竞赛辅导过程中,需要长期...构造法在解数学竞赛题中... 3页 免费 构造法在数学竞赛中的应... 3页 ...
浅谈构造法解题在高中数学竞赛中的应用
浅谈构造法解题在高中数学竞赛中的应用苏 传忠 在数学竞赛辅导过程中,需要长期...构造法在解数学竞赛题中... 3页 免费 构造法在数学竞赛中的应... 3页 ...
高中数学奥赛辅导 第八讲 组合计数
高中数学奥赛辅导 第八讲 组合计数_学科竞赛_高中教育...Ⅲ.映射法(略,见第一讲) Ⅳ.分类计数原理与分步...(第 4 届 AIME 试题,1986 年) 【解】符合题意...
浅谈构造法解题在高中数学竞赛中的应用 (3)
浅谈构造法解题在高中数学竞赛中的应用苏 传忠 在数学竞赛辅导过程中,需要长期...构造法在数学竞赛中的应... 3页 1下载券 构造法在解数学竞赛题中... 3...
浅谈构造法解题在高中数学竞赛中的应用 (2)
浅谈构造法解题在高中数学竞赛中的应用苏 传忠 在数学竞赛辅导过程中,需要长期...构造法在解数学竞赛题中... 3页 免费 浅谈高中数学解题中运用... 1页 1...
数学奥赛辅导 第六讲 集合与映射
高中数学奥赛系列辅导资料... 暂无评价 6页 2财富...映射及其性质,这些在与计数有关的数学竞赛问题 中...【解】显然,可以由题设找到这样的 1987 个集合,...
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用_学科竞赛_高中教育_...解:将问题一般化,考虑 n 块木块放入 n ? n 的棋盘的问题,答案是肯定的.现...
高中数学复习——计数原理与排列组合(讲义及习题)
高中数学复习——计数原理与排列组合(讲义及习题)_数学...现要从中选出男、女生各一名代表班级参加比 赛,共...解: (1) 从书架上任取 1 本书,有 3 类方法:...
高中数学奥赛讲义:赋值法在函数方程中的应用
高中数学奥赛讲义:映射与...1/2 相关文档推荐 ...x ? 解: ,(1)中以 x 2x ?1 ? x ?1? ?...? x x ?1。 显然,这一函数满足题设条件。 ...
高中竞赛数学讲义第48讲截面、面积与体积题目
高中竞赛数学讲义第48讲截面、面积与体积题目_学科竞赛_高中教育_教育专区。第8...求顶点 D 到底面的距离. 解: (1)如图甲设 AB=13,AC=15,将图甲中的三...
更多相关标签: