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 的个数为 。

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


高中数学奥赛辅导教材(共十讲)精品

高中数学奥赛辅导教材(共十讲)精品_高三数学_数学_...相当不错的数学竞赛资料 第一讲 集合概念及集合上...【评述】此题解方程中,应用了不等式取等号的充要...

高中数学奥赛讲义:数学学习中的学法指导

高中数学奥赛讲义:数论函... 高中数学奥赛讲义:映射与...1/2 相关文档推荐 ...求 大小?(1964,北京赛题) 解:利用三面角余弦公式 得 ∴例 5. 已知四面体 ...

高中数学竞赛解析几何问题选讲

高中数学竞赛解析几何问题选讲_数学_自然科学_专业资料。解析几何问题选讲: 1....并证明你的 结论.(2000 年全国高中数学联合竞赛试题) 解设 PQRS 是与 C0 外...

高中数学竞赛讲义_解三角形

高中数学竞赛讲义_解三角形_学科竞赛_高中教育_教育专区。高中数学竞赛习题解三角形 一、基础知识 在本章中约定用 A , B , C 分别表示 △ ABC 的三个内角,...

高中竞赛数学讲义第56讲解析法证几何题

高中竞赛数学讲义第56讲解析法证几何题_学科竞赛_高中教育_教育专区。第 56 讲...设 解得 C=± (a2+b2)-ab. 如图,应舍去负号. 所以直线 ED 方程为 ax+...

高中数学联合竞赛二试讲义8.1 平几名定理、名题与竞赛...

高中数学奥赛讲义:映射与... 6页 8财富值 8.1平面...也是数学 竞赛命题的背景题, 在很多竞赛题中都可以...用解析几何方法来解,下面提供的 解法则利用了面积...

高中竞赛数学讲义第80讲存在性问题(新)

高中竞赛数学讲义第80讲存在性问题(新)_学科竞赛_...解 按题意有 A(-2,0),B(2,0),C(2,4a),...,n}, 是否存在一一映射 φ:An→An 满足 条件:对...

高中数学竞赛讲义01:集合与简易逻辑

所以 1) 若,则; ,若 ,因为 ,所以 ,所 4.计数原理的应用。 例 4 集合 ...,求有序集 2 高中数学竞赛讲义(一) 【解】 (1)集合 I 可划分为三个不...

高中数学竞赛讲义15:复数

高中数学竞赛讲义15:复数_学科竞赛_高中教育_教育...集与坐标平面内所有的点构成的集合之间的一一映射。...例 4 设 n≤2000,n∈ [解] 由题设得 , 所以...

高中竞赛数学讲义第12讲计数基本原理:分步与分类

高中竞赛数学讲义第12讲计数基本原理:分步与分类_学科竞赛_高中教育_教育专区。...解 ?4 位数由高位到低位的数字分别设为 a,b,c,d,则由题意知 a 取 9 ...