当前位置:首页 >> 学科竞赛 >> 高二数学竞赛班讲义 第一讲 组合计数

高二数学竞赛班讲义 第一讲 组合计数


高二数学竞赛班二试 第一讲
一、知识要点:

组合计数与极端原理
班级 姓名

1.定理 1(容斥原理) (也称逐步淘汰公式)设 S1 , S2 , ???, Sn 是 S 的子集,则

S1 ? ??? ? Sn ? S ? ? Si ?
i ?1

n

r />1?i1 ?i2 ? n

?

Si1 ? Si2 ? ??? ? (?1) k

1?i1 ?????ik ? n

?

Si1 ? ??? ? Sik

? ??? ? (?1) n S1 ? ??? ? Sn .
定理 2(容斥原理的对偶形式)设 S1 , S2 , ???, Sn 是 S 的子集,则

S1 ? ??? ? Sn ? ? Si ?
i ?1

n

1?i1 ?i2 ? n

?

Si1 ? Si2 ? ??? ? (?1) k ?1

1?i1 ????? ik ? n

?

Si1 ? ??? ? Sik

? ??? ?(?1) n ?1 S1 ? ??? ? Sn
(因为 S1 ? ??? ? Sn ? CS ( S1 ? ??? ? S n ) ,所以 S1 ? ??? ? S n ? S ? S1 ? ??? ? S n ) 2.极端原理 极端原理就是通过讨论 “极端” 对象来解题的方法, 它考虑的是极端情况——最大或最小。 因此,它往往在题目中增加一个(最大或最小)条件,从而使问题巧妙地得以解决。同时, 它常跟反证法结合,通过与“最大”与“最小”的矛盾来解决问题。 3.通常考虑的极端情况,可以是边最长(最短) ,最大数(或最小数)等,其在不等式、不 定方程、图论及一些组合问题(特别是一些存在性问题)中都经常被用到。

二、经典例题
例 1.求 k 个红球 m 个白球 (k ? m) 的满足下列条件:在每个位置前的红球数不少于白球数 的排列数。

例 2.由数码 1,2,3 构成 n 位数,使 n 位数中数码 1,2,3 都至少出现一次,求所有这种 n 位数 的个数。

1

例 3.设 n 个点,它们之间至少有 ?

? n2 ? ? ? 1 条连线,则至少有一个三角形。 ?4?

例 4.设 S ? ?1, 2, ???,1990? ,若 S 的一个 51 元的子集的元素之和被 5 整除,则称其为 S 的 好子集,求 S 的好子集的个数。

三、精选习题:
1. (2013 年浙江省数学竞赛)某动点在平面直角坐标系第一象限的整点上运动(含第一象 限 x, y 轴上的整点) ,其运动规律为 (m, n) ? (m ? 1, n ? 1) 或 (m, n) ? (m ? 1, n ? 1) 。若该 动点从原点出发,经过 6 步运动到(6,2)点,则有_______________种不同的运动轨迹。 2.2n 个人到同一台自动售货机去各买一罐饮料, 饮料每罐 5 元, 假设这 2n 个人中, n 人 有

2

持 5 元面值的钞票,有 n 人持 10 元面值的钞票,售货机内无零钱。求这 2n 个人各自买 好饮料而售货机未出现找不出零钱的排列总数。

3.在 a, b, c, d , e, f 六个字母的全排列中,求不出现 abc 和 ef 的排列的个数。

4.设 S 是一个有限集合, S ? n , k 是正整数。求 S 的满足 S1 ? ??? ? Sk ? ? 的 k 个有序 子集组 ( S1 , ???, S k ) 的个数。

5. 设集合 A ? ?1, 2,3, ???, 2n ? 1? , 求一个包含元素个数最多的集合 A 的子集 B , 使得集合 B 中的任意三个元素 a, b, c ,都有 a ? b ? c 。

3

6.在某种比赛中,每一个选手都恰与其他选手比赛一局,每局赢者得 1 分,输者得 0 分, 平局各得 0.5 分。比赛结束后,发现每个选手所得的分数中恰好有一半是在他同 10 位得 分最低的选手的对局中得到的 (10 位得分最低的选手所得的分数有一半是在他们彼此对 局中得到的) 。求参加比赛的选手的总数。

7.出席某会议共 12k 个人 (k ? Z ? ) ,其中每个人均恰好同其余 3k ? 6 个人相识;对任何两 个人,均有 n 个人同他们相识,问共有多少人出席会议?

4

第一讲
例 1. C
m m? k

组合计数与极端原理
m m ?1

?C

m ?1 m? k

如果不考虑附加条件,排列数为 C m ? k 。以下证明不满足附加条件的排列数为 C m ? k 。 任取一个不满足条件的且有 k 个红球, m 个白球的排列,必定存在一个位置 2S ? 1 , 这里 S ? 0 ,使得排列在这一位上正好是白球,且在这一位前有 S 个红球和 S 个白球。我们 取满足这个条件的 S 中的最小的一个, 且在这个排列的最前面加一个红球, 这样就得到一个 m 个白球, k ? 1 个红球的排列。这个排列的第一个是红球,且在前面 2S ? 2 个球红白球数 相同。现在,再在前 2S ? 2 个位置上将红球换成白球,白球换成红球,得到一个 m 个白球, k ? 1 个红球的、且第一个是白球的排列。这个排列同每个不满足条件的排列相对应,现证 明这是个一一映射:

?k个红,m个白的不满足条件的排列?

? ?白球在首,m个白、k +1个红的排列? ,

由以上构造可得,这是一个单射。 反之,对于每一个以白球开始, m 个白球, k ? 1 个红球的排列,由于 m ? k +1 ,因此 从首位开始,总有一个位置红白球数相等(因为首位是白球,开始白球球数多,但总的红球 数多于白球数) 。在从首位到第一个这样的位置,将红白球交换,再去掉第一个红球,就得 到 k 个红球, m 个白球的不满足条件的排列了,映射为一一映射。 因此,不满足条件的排列数为 Cm ? k 。 故满足条件的排列数为 Cm ? k ? Cm ? k
m m ?1
m ?1

例 2.记由数码 1,2,3 构成的 n 位数的全体是 S ,并记 Sk ? {x | x ? S , x 中不含数码 k } ,

k ? 1, 2,3 ,则
S1 ? S2 ? S3 ? S ? ? Si ?
i ?1 3 1?i1 ?i2 ?3

?

Si1 ? Si2 ? S1 ? S 2 ? S3 ? 3n ? 3 ? 2n ? 3
? n2 ? ? ?1 ?4?

例 3.证明:用反证法,设不存在三角形,要证边数小于 ?

设这 n 个点为 A1 , A2 , ???, An ,不妨设从 A1 引出的边数最多,共有 k 条,适当调整下标, 可认为是 A1 An , A1 An ?1 , ???, A1 An ? k ?1 。由于不存在三角形,则 An , An ?1 , ???, An ? k ?1 之间无 线 段 相 连 , 从 而 每 条 连 线 至 少 有 一 个 端 点 是 A1 , A2 , ???, An ? k 中 的 点 , 以

n Ai (i ? 1, 2, ???, n ? k ) 为一个端点的边至多为 k 条,故连线总数 ? k (n ? k ) ? ( ) 2 ,连 2 2 ?n ? 线总数为整数,故连线总数 ? ? ? ,矛盾! ?4?
例 4.这一解法基于一一对应,我们将 S 的全部 51 个元素分成 5 个类 S0 , S1 , ???, S4 ,其中 S i 是元素和被 5 除余 i 的 51 元子集构成的集合( i ? 0,1, 2,3, 4 ) 易知,对于任意的 i, j (0 ? i, j ? 4, i ? j ) ,有唯一的 m(0 ? m ? 4) ,使得 (i ? m) ? j 被

5 整除,我们作如下的对应: ? ? ? 对任意 A ? Si ,设 A ? ? x1 , x2 , ???, x51? ,令 A? ? ? x1 ? m, x2 ? m, ???, x51 ? m?

5

? 其中, xk ? ?

xk ? m ? 1990 ? xk , , k ? 1, 2, ???,51 ? xk ? 1990, xk ? m ? 1990

由于 A 的元素之和被 5 除余 i , 故由 m 的选取可知,A? 的元素之和 5 除余 j , 从而 A? ? S j , 于是如上的对应给出了 Si ? S j 的一个映射。 我们证明,这一映射必是一个单射,即对 A, B ? Si , A ? B ,有 A? ? B? 。这只需要将

A, B 中的元素从小到大排列,并注意,对 1 ? xk , yl ? 1990 ,有 xk ? m ? 1990 ? yl ? m 。 由此易知,若 A? ? B? ,则 A ? B 。 因上述的映射是单射,所有 Si ? S j 。由于 i, j 的对称性,同样也有 S j ? Si ,
51 故 Si ? S j , 于是 S0 ? S1 ? S2 ? S3 ? S4 。 S 共有 C1990 个 51 元子集, S0 ? 因 故 2 1 C6 ? C6 ? 9 . n ?1

1 51 C1990 5

1.解答
n

2. C2 n ? C2 n

3. S1 ? S 2 ? 6!? 5!? 4!? 3! ? 582 4.如图,如果元素 x j 属于集合 S i ,就在第 i 行与第 j 列的交叉格子中标上数 1,否则就标 上 0。显然,
n

?S
i ?1

i

? ? 等价于这一数表中任一列都不全是 1。记上述 k ? n 且每一列都

不全是 1 的数表之集为 T , 则易见符合要求的有序子集组 ( S1 , ???, S k ) 之集与集合 T 一一 对应。 由于数表中每一格子都有两种填数法,故 T 中任一列都有 2k ? 1 种选取,又各列的选取
k n 是独立的。从而 T ? (2 ? 1) 。因此问题中所求的个数是 (2 ? 1) 。
k n

x1

x2

xn

S1 S2 Sk
5.考察最大数,若 2n ? 1? B , 则由于 1 ? 2n ? 2 ? (2n ? 1) ? 3 ? (2n ? 2) ? ??? ? n ? (n ? 1) 所以 ?1, 2n? , ?2, 2n ? 1? , ???, ?n, n ? 1? 这 n 个集合中每一个集合的元素中至多有一个在 B 中, 可见集合 B 中至多有 n ? 1个元素。如 B ? ?n ? 1, n ? 2, ???, 2n ? 1? 若 2n ? 1? B ,且 2n ? B ,则集合 B 中至多有 n 个元素。 6.考虑极端元素(得分最低者) 设共有 n 名选手,则他们共得 Cn 分。10 位得分最低的选手彼此对局中得到 C10 ? 45 ,这是
2 2

他们所得分数之半, 故他们 10 位共得 90 分。 其余的 n ? 10 位选手在他们彼此间对局中共得
2 2 Cn ?10 分,这也是他们所得分数之半,故这 n ? 10 位选手共得 2Cn ?10 分。

2 于是 Cn ? 90 ? 2Cn ?10 ,即 n ? 41n ? 400 ? 0 ,解得 n ? 16 或 n ? 25
2 2

但若只有 16 位选手,那么就有 6 位得高分者,他们共得 30 分,平均每人 5 分,而 10 位得 低分者平均每人得 90 ?10 ? 9 分,矛盾! 所以 n ? 25 ,即共有 25 为参加比赛的选手。 6

7.组合中的“算两次思想” 将人视为点,相识就连线,每点共组成 C3 k ? 6 个角,每个角对应一个顶点,因此图中共有角
2

12k ? C32k ?6 个
另一方面,对任何两个人,与该两人都相识的人有 n 个,因此对该两人对有且仅有 n 个角, 从这一角度说总角数为 n ? C12k 个
2

2 所以 12k ? C3k ? 6 ? n ? C12k ,即 9k ? 33k ? 12nk ? n ? 30 ? 0
2 2

易见 3|n ,设 n ? 3m ,则 4m ? k ? 3 ? 所以共有 36 人出席会议

9k ? 43 ,得 k ? 3 , m ? 2 , n ? 6 , 12k ? 36 12k ? 1

R V B G Y O

O R V B G Y

Y O R V B G

G Y O R V B

B G Y O R V

V B G Y O R

7


更多相关文档:

高二数学竞赛班讲义 第一讲 组合计数

高二数学竞赛班讲义 第一讲 组合计数_学科竞赛_高中教育_教育专区。高二数学竞赛班二试 第一讲一、知识要点: 组合计数与极端原理班级 姓名 1.定理 1(容斥原理)...

数学竞赛讲义组合计数

数学竞赛讲义组合计数_学科竞赛_高中教育_教育专区。数竞必备,组合计数 ...联赛班·第 1 讲·教师版 1 最基本的加法、乘法原理,以及枚举方法来计数.这...

高二数学竞赛班讲义 第六讲 组合问题

高二数学竞赛班二试 第六讲 组合问题班级 姓名 一、知识要点:组合数学是一个既古老又年轻的离散数学分支, 竞赛中的组合问题主要包括组合计数问 题、组合极值问题...

数学竞赛讲义组合1-6

数学竞赛讲义组合1-6_学科竞赛_高中教育_教育专区。全国高中数学联赛组合讲义数学竞赛讲义 1-6 讲 第一讲 组合计数(1)本讲概述组合数学是竞赛中最重要的一个板块...

高二数学竞赛班讲义 第四讲 组合不等式

高二数学竞赛班二试 第四讲 组合不等式(一)班级 姓名 一、知识要点:组合不...组合不等式问题有:组合数不等式、组合 计数不等式、组合最值、组合几何不等式、...

高中数学竞赛之组合计数

,在第 n组合计数(一)一、基础知识(一) 、两条基本原理 1、 (加法原理)...2011全国高中数学竞赛讲... 4页 免费 高中数学竞赛讲义_组合 暂无评价 3页 ¥...

高二数学竞赛培训 第一讲 集合与容斥原理(含答案)

高二数学竞赛培训 第一讲 集合与容斥原理(含答案)_...要条件,描述排列组合,用集合的性质 进行组合计数等...(容斥原理) 请看以下问题: 开运动会时,高一某班...

高中数学奥赛辅导 第八讲 组合计数

高中数学奥赛辅导 第八讲 组合计数_学科竞赛_高中教育_教育专区。数学奥赛辅导组合计数知识、方法、技能 第八讲 组合计数就是计算集合的元素个数。它是组合数学的重...

数学竞赛讲义:排列与组合

数学竞赛讲义:排列与组合_学科竞赛_高中教育_教育专区...×mn;使用乘法原理的关键在于对所计数的对象进行完全...年高考江苏第 15 题) 某城市在中心广场建造一个花...
更多相关标签:
图形计数 讲义 | 高中数学竞赛讲义 | 高中生物竞赛讲义 | 蔡子星物理竞赛讲义 | 高中物理竞赛讲义 | 学而思物理竞赛讲义 | 初中数学竞赛讲义 | 高二数学培优拔高讲义 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com