高二数学竞赛班二试

高二数学竞赛班二试

ID:26346731

大小:521.00 KB

页数:7页

时间:2018-11-26

高二数学竞赛班二试_第1页
高二数学竞赛班二试_第2页
高二数学竞赛班二试_第3页
高二数学竞赛班二试_第4页
高二数学竞赛班二试_第5页
资源描述:

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

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分,平局各得分。比赛结束后,发现每个选手所得的分数中恰好有一半是在他同10位得分最低的

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

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

6、列数为例2.记由数码1,2,3构成的位数的全体是,并记中不含数码,,则例3.证明:用反证法,设不存在三角形,要证边数小于设这个点为,不妨设从引出的边数最多,共有条,适当调整下标,可认为是。由于不存在三角形,则之间无线段相连,从而每条连线至少有一个端点是中的点,以为一个端点的边至多为条,故连线总数,连线总数为整数,故连线总数,矛盾!例4.这一解法基于一一对应,我们将的全部个元素分成5个类,其中是元素和被5除余的元子集构成的集合()易知,对于任意的,有唯一的,使得被整除,我们作如下的对应:对任意,设,令7其中,,由于的元素之和被5除余,故由的选取可知

7、,的元素之和5除余,从而,于是如上的对应给出了的一个映射。我们证明,这一映射必是一个单射,即对,,有。这只需要将中的元素从小到大排列,并注意,对,有。由此易知,若,则。因上述的映射是单射,所有。由于的对称性,同样也有,故,于是。因共有个元子集,故1.解答.2.3.4.如图,如果元素属于集合,就在第行与第列的交叉格子中标上数1,否则就标上0。显然,等价于这一数表中任一列都不全是1。记上述且每一列都不全是1的数表之集为,则易见符合要求的有序子集组之集与集合一一对应。由于数表中每一格子都有两种填数法,故中任一列都有种选取,又各列的选取是独立的。从而。因

8、此问题中所求的个数是。5.考察最大数,若,则由于所以这个集合中每一个集合的元素中至多有一个在中,可见集合中至多有个元素。如若,且,则集合

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。