高二数学竞赛班二试

《高二数学竞赛班二试》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、高二数学竞赛班二试第一讲组合计数与极端原理班级姓名一、知识要点：1．定理1（容斥原理）（也称逐步淘汰公式）设是的子集，则．定理2（容斥原理的对偶形式）设是的子集，则（因为，所以）2．极端原理极端原理就是通过讨论“极端”对象来解题的方法，它考虑的是极端情况——最大或最小。因此，它往往在题目中增加一个（最大或最小）条件，从而使问题巧妙地得以解决。同时，它常跟反证法结合，通过与“最大”与“最小”的矛盾来解决问题。3．通常考虑的极端情况，可以是边最长（最短），最大数（或最小数）等，其在不等式、不定方程、图论及一些组合问题（特别是一些存

2、在性问题）中都经常被用到。二、经典例题例1．求个红球个白球的满足下列条件：在每个位置前的红球数不少于白球数的排列数。例2．由数码1,2,3构成位数，使位数中数码1,2,3都至少出现一次，求所有这种位数的个数。7例3．设个点，它们之间至少有条连线，则至少有一个三角形。例4．设，若的一个元的子集的元素之和被整除，则称其为的好子集，求的好子集的个数。三、精选习题：1．（2013年浙江省数学竞赛）某动点在平面直角坐标系第一象限的整点上运动（含第一象限轴上的整点），其运动规律为或。若该动点从原点出发，经过6步运动到（6,2）点，则有__

3、_____________种不同的运动轨迹。2．个人到同一台自动售货机去各买一罐饮料，饮料每罐5元，假设这个人中，有7人持5元面值的钞票，有人持10元面值的钞票，售货机内无零钱。求这个人各自买好饮料而售货机未出现找不出零钱的排列总数。3．在六个字母的全排列中，求不出现和的排列的个数。4．设是一个有限集合，，是正整数。求的满足的个有序子集组的个数。5．设集合，求一个包含元素个数最多的集合的子集，使得集合中的任意三个元素，都有。76．在某种比赛中，每一个选手都恰与其他选手比赛一局，每局赢者得1分，输者得0分，平局各得分。比赛结束后

4、，发现每个选手所得的分数中恰好有一半是在他同10位得分最低的选手的对局中得到的（10位得分最低的选手所得的分数有一半是在他们彼此对局中得到的）。求参加比赛的选手的总数。7．出席某会议共个人，其中每个人均恰好同其余个人相识；对任何两个人，均有个人同他们相识，问共有多少人出席会议？7第一讲组合计数与极端原理例1．如果不考虑附加条件，排列数为。以下证明不满足附加条件的排列数为。任取一个不满足条件的且有个红球，个白球的排列，必定存在一个位置，这里，使得排列在这一位上正好是白球，且在这一位前有个红球和个白球。我们取满足这个条件的中的最小

5、的一个，且在这个排列的最前面加一个红球，这样就得到一个个白球，个红球的排列。这个排列的第一个是红球，且在前面个球红白球数相同。现在，再在前个位置上将红球换成白球，白球换成红球，得到一个个白球，个红球的、且第一个是白球的排列。这个排列同每个不满足条件的排列相对应，现证明这是个一一映射：，由以上构造可得，这是一个单射。反之，对于每一个以白球开始，个白球，个红球的排列，由于，因此从首位开始，总有一个位置红白球数相等（因为首位是白球，开始白球球数多，但总的红球数多于白球数）。在从首位到第一个这样的位置，将红白球交换，再去掉第一个红球，

6、就得到个红球，个白球的不满足条件的排列了，映射为一一映射。因此，不满足条件的排列数为。故满足条件的排列数为例2．记由数码1,2,3构成的位数的全体是，并记中不含数码，，则例3．证明：用反证法，设不存在三角形，要证边数小于设这个点为，不妨设从引出的边数最多，共有条，适当调整下标，可认为是。由于不存在三角形，则之间无线段相连，从而每条连线至少有一个端点是中的点，以为一个端点的边至多为条，故连线总数，连线总数为整数，故连线总数，矛盾！例4．这一解法基于一一对应，我们将的全部个元素分成5个类，其中是元素和被5除余的元子集构成的集合（）

7、易知，对于任意的，有唯一的，使得被整除，我们作如下的对应：对任意，设，令7其中，，由于的元素之和被5除余，故由的选取可知，的元素之和5除余，从而，于是如上的对应给出了的一个映射。我们证明，这一映射必是一个单射，即对，，有。这只需要将中的元素从小到大排列，并注意，对，有。由此易知，若，则。因上述的映射是单射，所有。由于的对称性，同样也有，故，于是。因共有个元子集，故1．解答.2．3．4．如图，如果元素属于集合，就在第行与第列的交叉格子中标上数1，否则就标上0。显然，等价于这一数表中任一列都不全是1。记上述且每一列都不全是1的数表

8、之集为，则易见符合要求的有序子集组之集与集合一一对应。由于数表中每一格子都有两种填数法，故中任一列都有种选取，又各列的选取是独立的。从而。因此问题中所求的个数是。5．考察最大数，若，则由于所以这个集合中每一个集合的元素中至多有一个在中，可见集合中至多有个元素。如若，且，则集合