数学竞赛论-5组合

《数学竞赛论-5组合》由会员分享，可在线阅读，更多相关《数学竞赛论-5组合（17页珍藏版）》请在金锄头文库上搜索。

1、2-5 数学竞赛中的组合问题数学竞赛中的组合数学不是一个严格的概念，它离中学教材最远，通常指中学代数、几何、算术（数论）之外的内容（俗称杂题）对中学生而言，这类问题的基本特点是不需要专门的数学语言就可以表述明白，解决起来也没有固定的程式（非常规），常需精巧的构思从内容上可以归结为两大类：组合计数问题，组合设计问题（1）组合计数问题这包括有限集合元素的计算、相应子集的计算、集合分拆方法数的计算等，表现为数值计算、组合恒等式或组合不等式的证明知识基础是加法原理、乘法原理和排列组合公式；常用的方法有：代数恒等变形、二项式定理、数学归纳法、递推、组合分析、容斥原理等（2）组合设计问题其基本含义是，对有

2、限集合，按照性质来作出安排，有时，只是证实具有性质的安排是否存在、或者验证作出的安排是否具有性质（称为存在性问题，又可分为肯定型、否定型和探究型）；有时，则需把具体安排（或具体性质）找出来（称为构造型问题）；进一步，还要找出较好的安排（称为最优化问题）值得注意的一个新趋势是组合与几何、数论的结合，产生组合几何、组合数论，它们与集合分拆一起组成IMO试题的三个热点，突出而鲜明的体现数学竞赛的“问题解决”特征这三方面之所以成为热点，从思维方式、解题技巧上分析，是因为其更适宜数学尖子的脱颖而出，且常与现代数学思想相联系；从技术层面上分析，还由于都能方便提供挑战中学生的新颖题目链接资料组合数学又称组合

3、分析或组合学研究将有限个元素安排到适合（服从）某些限制条件的集合有三个基本问题： （1）组态问题，解决存在这种安排的条件，给出明确的结论；（2）组态存在时，确定其数目或将它们进行分类；（3）研究安排的性质和结构，包括最优化问题组合数学最早出现的是神话传说：大禹时代（公元前2200年）的神龟背上驮着的幻方，古代称为九宫，即 4 9 2 3 5 7 8 1 6一般是将放到格子中，使每行每列各数之和相等，称为阶幻方还有缺角棋盘的覆盖问题、柯克曼女生散步问题、欧拉名军官问题都是著名的组合学例子现代科学技术中，又提出离散性问题及关系结构分析，图论、信息论、编码、实验设计、线性规定划等领域也提了一系列问题

4、，促进了组合学的发展一中的组合题（智力题）1数量统计 从开始，占20%2基本类型（1）组合计数问题：问题类型有限集合元素的计算，子集的计算，集合分拆的计算解题方法：代数恒等变形二项式定理组合等式递推组合分析容斥原理数学归纳法（2）组合设计问题：对集合A，按照某种性质P来作出安排问题类型存在性问题，构造性问题，最优化问题解题方法：构造法、反证法抽屉原理染色方法递推方法更多的解题技巧 见 2-73发展特点以组合计数、组合设计为基础，与数论、几何交叉，形成组合数论、组合几何、集合分拆三大热点二、基础知识（与基本类型相一致）有个定义、9条定理：定义 从个不同的元素中取出个，按照一定的顺序排成一列，叫做

5、从个不同的元素中取出个元素的一个排列相异元素排列数的计算公式为： 定义 从个不同的元素中取出个，并成一组，叫做从个不同的元素中取出个元素的一个组合相异元素组合数的计算公式为： 定理 （加法原理）做一件事，完成它可以有类办法，在第一类办法中有种不同的方法，在第二类办法中有种不同的方法，在第类办法中有种不同的方法，那么完成这件事共有 种不同的方法定理2 （乘法原理）做一件事，完成它需要分成个步骤，做第一步有种不同的方法，做第二步有种不同的方法，做第步有种不同的方法，那么完成这件事共有 种不同的方法定理3 组合恒等式（1）（2）（3）（4）定理4 （二项式定理）定义 从个不同的元素中取出个，按照一定

6、的顺序排在一个封闭曲线上，叫做环形排列（或循环排列、圆排列）相异元素的 圆排列数公式为： 定义 从个不同的元素中，允许重复取出个元素，按照一定的顺序排成一列，称为个相异元素允许重复的元排列相异元素的可重复排列数计算公式为：定义 从个不同的元素中，允许重复取出个元素，不管怎样的顺序并成一组，称为个相异元素允许重复的元组合 相异元素的可重复组合数计算公式为： 定义 若个元素中，有个，个个，且，则这个元素的全排列，称为不尽相异元素的全排列不尽相异元素的全排列公式为： 定义 如果是一个元有限集合，那么，它的子集组成的集合叫做的一个子集系定理5 元集合中含有个元素的子集有个；集合的所有子集共个定理6 （

7、抽屉原理）（1）若把元素放进个集合，则必存在一个集合至少放有个元素（2）若把个元素放进个集合，则至少有个集合的元素一样多（3）若把元素放进个集合，则必有一个集合至多含有个元素定理7 （容斥原理）设集合，记为对于全集的补集，则(1)(2)定理8 （自然数的良序性）自然数的任一非空子集中，必有一个元素是最小的定理9 设是两个有限元集合，分别是两集合的元素个数，是到的一个映射（）若是单射，则；特别的，是单射而非满射，则（）若是满射，则（）若是一一映射（双射），则主要类型（1）排列、组合的知识（2）集合、影射的知识（3）抽屉原理（4）容斥原理（5）组合恒等式三、例题讲解例1 （1）将10个苹果分给3个

8、人，每人至少1个，问有几种不同的分法？（10的有序分拆）（2）将10个苹果分成3堆，每堆至少1个，问有几种不同的分法？（10的无序分拆）解（1）设第个人分得个苹果，则有对应9个加号取2个的取法，得相当于10个苹果一字排开两手拿隔板往里一插，得一种分法（2）10的3项分拆：每堆先放1个苹果，剩下的7个苹果可以拆开放到3堆，也可以放到2堆，或全放到1堆，故得10的3项分拆=7的3项分拆+7的2项分拆+7的1项分拆=4的3项分拆+4的2项分拆+4的1项分拆+3+1=1+2+1+3+1=8 一般地 的项分拆=的项分拆+的项分拆+的2项分拆+的1项分拆 数字小时可以列举10=1+1+8=1+2+7=1+

9、3+6=1+4+5=2+2+6=2+3+5=2+4+4=3+3+4共8种例2（1988，高中联赛，例2-104）甲乙两队各出7名队员按事先安排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，依次类推，直到有一方队员全被淘汰为止，另一方获胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数有多少？（P205）解法解法 设胜 场，甲胜等价于方程 ，非负整数解的个数，令，方程，正整数解的个数，从13个加号取6个的方法数种 同理，乙胜也有种得2=种2=3432种例2-1 联欢晚会准备了个礼物，平分为两串公开吊挂在墙上，每个获奖者可以（也只能）从两串的最下方任

10、选一个礼物，则个获奖者选这个礼物，共有 种不同的选法（）例3（1989，例2-105）设是正整数，我们说集合的一个排列具有性质，是指在当中至少有一个，使得，求证对于任何，具有性质的排列比不具有性质的排列的个数多（P85） 解 显然成立对设不具有性质的排列组成集合，设恰有一个元素具有性质的排列组成集合，取，则存在，使，作对应，则，且中不同的元素在中有不同的像，得 具有性质的排列个数例4（1989，高中）如果从数1，2，14中按由小到大的顺序取出，使同时满足 那么，所有符合上述要求的不同取法有多少种？ 解 由已知得4项均为非负数，相加得，于是的取法数就是不定方程 的非负整数解的个数，作一一对应问题

11、又等价于不定方程 的正整数解由 得个解，即符合要求的不同取法有种（P240）例5 （1992高中联赛） 设集合，若是的子集，把中的所有数的和称为的“容量”（规定空集的容量为0）若的容量为奇（偶数），则称为的奇（偶）子集 （1）求证：的奇子集与偶子集个数相等（2）求证：当时，的所有奇子集的容量之和与所有偶子集的容量之和相等 （3）当时，求的所有奇子集的容量之和 证明1 分别求解3问 （1）对，我们取与对应：当时，就从中取出1得；当时，就从中添上1得于是，与一一对应，且一个为奇（偶）子集时，另一个便为偶（奇）子集，故中的奇子集与偶子集一一对应，个数相等 （2）设中的奇子集个数有个，偶子集个数有个，

12、所有奇子集的容量之和为，所有偶子集的容量之和为，由第（1）问及中有个子集知 1）当且为奇数时，中的奇（偶）子集由两部分组成，其一是的奇（偶）子集，其二是的每一个偶（奇）子集与的并集，有2）当且为偶数时，则为奇数，由上证，有 此时，中的奇（偶）子集由两部分组成，其一是的奇（偶）子集，其二是的每一个奇（偶）子集与的并集，有 综上得，当时 （3）由于中每个元素都出现在个子集中，所以的所有子集的容量为=得 证明2 同时求解3问 设中的奇子集个数有个，偶子集个数有个，所有奇子集的容量之和为，所有偶子集的容量之和为，有对，用数学归纳法证明命题（1）当时，的奇子集有，偶子集有，得命题成立（2）现假设时，命题

13、成立即 对的子集可以分成两部分，一部分是的子集，有；另一部分是的子集与的并集，其奇子集的个数与偶子集的个数也是相等的有并且，等于的2倍，再加上个，即 这说明时，命题成立由数学归纳法知，题目中的3问均已成立作业从个不同的元素中，允许重复取出个元素，不管怎样的顺序并成一组，称为个相异元素允许重复的元组合证明：相异元素的可重复组合数计算公式为：2.凸n边形（）玫瑰园的n个顶点各栽有1棵红玫瑰，每两棵红玫瑰之间都有一条直小路相通，这些直小路没有出现“三线共点”的情况它们把花园分割成许多不重叠的区域（三角形、四边形，），每块区域都栽有一棵白玫瑰或黑玫瑰 求出玫瑰园里玫瑰总棵数的表达式 花园里能否恰有99棵玫瑰？说明理由作业处理1.求方程的整数解.解：由2009的分解式，有 ， 有 2、2009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子的数为吉祥数，请证明最简分数的分子是吉祥数证明：由其中为正整数，有 ，这表明，整除，但为素数，不能整除，所以整除，得是吉祥数