资源描述：
《数学竞赛讲义组合.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七讲组合综合问题本讲概述在前六讲我们对组合数学中的不少专题进行了研究，本讲不再进行具体某个专题的学习，而是通过一些综合性的问题的探讨来寻找组合数学“解题的感觉”.本讲的题目与前面相比，综合性更强，难度在二试与冬令营之间，可能需要综合应用前面所学的多种组合知识乃至其它学科的知识来解决.事实上，组合与几何学、数论相联系形成的组合几何、组合数论问题往往难度较大，又能同时考察多个学科，是命题人青睐的对象，而在组合问题的探索过程中，特别是组合极值问题中，常常用到代数知识特别是数列与不等式知识.教师备注：本讲主要研究两大方面问题：（1）组合与其它学科相结
2、合（2）组合极值及其构造、论证；部分题目来自冬令营或相当冬令营难度的比赛，教师可自行选择适当问题讲述例题精讲【例1】设ABC为正三角形，E为线段BC，CA，AB上点的集合（包括A，B，C在内）。将E分成两个子集，求证：总有一个子集中含有一个直角三角形的顶点。【解析】将E中的点染成红、蓝二色，即证明必存在一个直角三角形，它们的顶点同色。在三边上取三等分点P，Q，R，如图01—05。易知RQ⊥BC，QP⊥AC，PR⊥AB。这三点必至少有两点同色。不妨设R，Q为红色。（1）如果BC边上除Q点外还有红色的点X，则Rt△RQX三个顶点同为红色。（2）如果
3、BC边上除Q外不存在红色点，则B点是蓝色的。如果AB上除B外还有蓝色点Y，作YM⊥BC，M为垂足，显然M不同于Q。所以Rt△YBM三个顶点均为蓝色；如果AB上除B点外均为红色。作QZ⊥AB，Z为垂足，则Rt△RQZ的三个顶点均为红色。证毕。【例2】某足球邀请赛有16个城市参加，每市派出甲乙两队.根据比赛规则，每两队之间至多赛一场，且同一城市两队之间不比赛.比赛进行若干天后统计，发现除A市甲队之外，其它各队已赛过场次互不相同.试问A市乙队已赛过多少场？【解析】依比赛规则，每队至多赛30场，所以除A市甲队之外，其它各队已赛过场次依次为.考场赛过30
4、场和0场的队，经简单推理知此两队必为同城队；接下来依次配对（29,1），（28,2），…，（14,16）.只有15没有配对，这就是乙队.于是乙队赛过15场.【例3】20支足球队参加比赛，每两队至多赛一场.为了使任何三队中都有两队赛过，球赛组委会安排了m场比赛，试求m最小值.【解析】设A队赛过k场，是所有队中赛过场次最少的.与A队赛过的k个队，各至少赛过k场，没有与A赛过的19-k个队中的任何两队B,C必赛过（否则就出现A,B,C三队两两未赛过，矛盾！）.于是比赛场数,于是至少要赛90场.下面给出一种比赛方案，使得恰赛90场：把20支队分成两组，
5、每组10个队，同组两两都赛，不同组不比赛，共安排场比赛.显然这个方案合要求.注本题为组合中最难的安排赛程表题型，也可以把它看成一个图论问题.比赛方案是受到论证过程的结果启发构造出来的.【例4】设，为给定的整数，.对任意元的数集，作的所有元子集的元素和，记这些和组成的集合为，集合中元素个数是，求的最大值.【解析】的最大值为.因共有个元子集，故显然有.下面我们指出，对集合，相应的等于，即的任意两个不同的元子集的元素之和不相等.从而的最大值为.事实上，若上述的集合有两个不同的元子集，，使得与的元素之和相等，则（设）.①因①可视为正整数的二进制表示，由
6、于互不相同，互不相同，故由正整数的二进制表示的唯一性，我们由①推出，集合必须与相同，从而子集，矛盾.这就证明了我们的断言.注本题为2009江苏赛区复赛题.这是一道典型的组合极值问题，难度并不太大.这种问题一般分为两部分：构造与论证，分别考察不同的数学能力，因此是近年来的命题热点.【例5】(1)若N*)个棱长为正整数的正方体的体积之和等于2005,求的最小值,并说明理由；(2)若N*)个棱长为正整数的正方体的体积之和等于2002,求的最小值,并说明理由.【解析】(1)因为,，故.因为，所以存在，使．………………6分若，因,则最大的正方体边长只能为
7、或，计算，而与均不是完全立方数,所以不可能是的最小值.………………9分若，设此三个正方体中最大一个的棱长为,由,知最大的正方体棱长只能为、、或.由于,,,所以.由于,,,,所以.由于,,,所以.由于,,所以.因此不可能是的最小值.综上所述，才是的最小值.………………12分(2)设个正方体的棱长分别是，则．……………⑤由，，得．……⑥……15分又当N*时，，所以，，.…⑦……………21分⑤式模,由⑥、⑦可知,．而，则．……24分因此为所求的最小值．注本题为2005年江苏预赛16题.这类与数论相联系的极值问题往往兼具组合构造与数论证明两大特点但鉴于
8、本题组合味道并不太浓，建议选讲.【例1】假定100个人中的每一个人都知道一个消息，而且这100个消息都不相同。为了使所有的人都知道一切消息，他们一共至
