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

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


高中数学奥赛讲义:

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

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


相关文章:
高中数学奥赛讲义:映射与计数在解竞赛题中的应用
高中数学奥赛讲义:映射与计数在解竞赛题中的应用_学科竞赛_高中教育_教育专区。高中数学奥赛讲义:映射与计数在解竞赛题中的应用 【内容综述】 利用映射来解决计数问...
高中竞赛数学讲义第12讲计数基本原理:分步与分类
高中竞赛数学讲义第12讲计数基本原理:分步与分类_学科竞赛_高中教育_教育专区。...解 ?4 位数由高位到低位的数字分别设为 a,b,c,d,则由题意知 a 取 9 ...
高中数学奥赛辅导 第六讲 集合与映射
有限集上的映射及其性质,这些在与计数有关的数学竞赛问题 中应用极广,是参赛者...【解】显然,可以由题设找到这样的 1987 个集合,它们都含有一个公共元素 a,...
高中数学奥赛辅导 第八讲 组合计数
高中数学奥赛辅导 第八讲 组合计数_学科竞赛_高中教育...Ⅲ.映射法(略,见第一讲) Ⅳ.分类计数原理与分步...(第 4 届 AIME 试题,1986 年) 【解】符合题意...
浅谈构造法解题在高中数学竞赛中的应用
浅谈构造法解题在高中数学竞赛中的应用苏 传忠 在数学竞赛辅导过程中,需要长期...构造合乎要求的几何图形,可以是所求解的问 题变得直观明朗,从而找到一个全新的...
浅谈构造法解题在高中数学竞赛中的应用
浅谈构造法解题在高中数学竞赛中的应用苏 传忠 在数学竞赛辅导过程中,需要长期...构造法在解数学竞赛题中... 3页 免费 构造法在数学竞赛中的应... 3页 ...
浅谈构造法解题在高中数学竞赛中的应用
浅谈构造法解题在高中数学竞赛中的应用苏 传忠 在数学竞赛辅导过程中,需要长期...构造法在解数学竞赛题中... 3页 免费 构造法在数学竞赛中的应... 3页 ...
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用
高中数学竞赛专题讲座---数学归纳法在高考及竞赛中的应用_学科竞赛_高中教育_...解:将问题一般化,考虑 n 块木块放入 n ? n 的棋盘的问题,答案是肯定的.现...
数学奥赛辅导 第六讲 集合与映射
高中数学奥赛系列辅导资料... 暂无评价 6页 2财富...映射及其性质,这些在与计数有关的数学竞赛问题 中...【解】显然,可以由题设找到这样的 1987 个集合,...
高中数学奥赛讲义:赋值法在函数方程中的应用
高中数学奥赛讲义:映射与...1/2 相关文档推荐 ...x ? 解: ,(1)中以 x 2x ?1 ? x ?1? ?...? x x ?1。 显然,这一函数满足题设条件。 ...
更多相关标签: