数学竞赛讲义组合

PAGE2高一·联赛班·寒假第7讲·教师版PAGE4高一·联赛班·寒假第7讲·教师版第七讲组合综合问题本讲概述在前六讲我们对组合数学中的不少专题进行了研究，本讲不再进行具体某个专题的学习，而是通过一些综合性的问题的探讨来寻找组合数学“解题的感觉”.本讲的题目与前面相比，综合性更强，难度在二试与冬令营之间，可能需要综合应用前面所学的多种组合知识乃至其它学科的知识来解决.事实上，组合与几何学、数论相联系形成的组合几何、组合数论问题往往难度较大，又能同时考察多个学科，是命题人青睐的对象，而在组合问题的探索过程中，特别是组合极值问题中，常常用到代数知识特别是数列与不等式知识.教师备注：本讲主要研究两大方面问题：（1）组合与其它学科相结合（2）组合极值及其构造、论证；部分题目来自冬令营或相当冬令营难度的比赛，教师可自行选择适当问题讲述例题精讲设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）如果BC边上除Q外不存在红色点，则B点是蓝色的。如果AB上除B外还有蓝色点Y，作YM⊥BC，M为垂足，显然M不同于Q。所以Rt△YBM三个顶点均为蓝色；如果AB上除B点外均为红色。作QZ⊥AB，Z为垂足，则Rt△RQZ的三个顶点均为红色。证毕。某足球邀请赛有16个城市参加，每市派出甲乙两队.根据比赛规则，每两队之间至多赛一场，且同一城市两队之间不比赛.比赛进行若干天后统计，发现除A市甲队之外，其它各队已赛过场次互不相同.试问A市乙队已赛过多少场？依比赛规则，每队至多赛30场，所以除A市甲队之外，其它各队已赛过场次依次为.考场赛过30场和0场的队，经简单推理知此两队必为同城队；接下来依次配对（29,1），（28,2），…，（14,16）.只有15没有配对，这就是乙队.于是乙队赛过15场.20支足球队参加比赛，每两队至多赛一场.为了使任何三队中都有两队赛过，球赛组委会安排了m场比赛，试求m最小值.设A队赛过k场，是所有队中赛过场次最少的.与A队赛过的k个队，各至少赛过k场，没有与A赛过的19-k个队中的任何两队B,C必赛过（否则就出现A,B,C三队两两未赛过，矛盾！）.于是比赛场数,于是至少要赛90场.下面给出一种比赛方案，使得恰赛90场：注本题为组合中最难的安排赛程表题型，也可以把它看成一个图论问题.比赛方案是受到论证过程的结果启发构造出来的.设，为给定的整数，.对任意元的数集，作的所有元子集的元素和，记这些和组成的集合为，集合中元素个数是，求的最大值.的最大值为.因共有个元子集，故显然有.下面我们指出，对集合，相应的等于，即的任意两个不同的元子集的元素之和不相等.从而的最大值为.事实上，若上述的集合有两个不同的元子集，，使得与的元素之和相等，则（设）.①因①可视为正整数的二进制表示，由于互不相同，互不相同，故由正整数的二进制表示的唯一性，我们由①推出，集合必须与相同，从而子集，矛盾.这就证明了我们的断言.注本题为2009江苏赛区复赛题.这是一道典型的组合极值问题，难度并不太大.这种问题一般分为两部分：构造与论证，分别考察不同的数学能力，因此是近年来的命题热点.(1)若N*)个棱长为正整数的正方体的体积之和等于2005,求的最小值,并说明理由；(2)若N*)个棱长为正整数的正方体的体积之和等于2002,求的最小值,并说明理由.(1)因为,，故.因为，所以存在，使．………………6分若，因,则最大的正方体边长只能为或，计算，而与均不是完全立方数,所以不可能是的最小值.………………9分若，设此三个正方体中最大一个的棱长为,由,知最大的正方体棱长只能为、、或.由于,,,所以.由于,,,,所以.由于,,,所以.由于,,所以.因此不可能是的最小值.综上所述，才是的最小值.………………12分(2)设个正方体的棱长分别是，则．……………⑤由，，得．……⑥……15分又当N*时，，所以eq\o(≡,∕)，eq\o(≡,∕)，eq\o(≡,∕).…⑦……………21分⑤式模,由⑥、⑦可知,．而，则．……24分因此为所求的最小值．注本题为2005年江苏预赛16题.这类与数论相联系的极值问题往往兼具组合构造与数论证明两大特点但鉴于本题组合味道并不太浓，建议选讲.假定100个人中的每一个人都知道一个消息，而且这100个消息都不相同。为了使所有的人都知道一切消息，他们一共至少要打多少个电话？198个。考虑一种特殊的通话过程：先由99人每人打一个电话给A，A再给99人每人打一个电话，这样一共打了198个电话，而且每人都知道了所有的消息。下面我们说明这是次数最少的。考虑一种能使所有人知道一切消息的通话过程中的关键性的一次通话，这次通话后，有一个接话人A知道了所有的消息，而在此之前还没有人知道所有的消息。除了A以外的99人每人在这个关键性的通话前，必须打出电话一次，否则A不可能知道所有的消息；又这99人每人在这个关键性的通话后，又至少收到一个电话，否则它们不可能知道所有的消息。注本题也是一道组合极值问题证明：设结论不真。则所给的3元子集要么不交，要么恰有两个公共元，如果子集A与B恰有两个公共元，则记。设A,B,C是三个子集。可以证明如果则，于是所有给定在（1）下，3元子集类恰由一个3元子集组成。在（2）下，子集类中至多有4个子集。考虑（3）设，则还有一个e，由，有。因此对子集类中任意子集D，由它包含a,b，于是类中子集个数比类中元素个数少2，于是，每个类中子集个数不超过元素个数，但是题中条件子集数大于元素个数，矛盾！注本题为一道美国竞赛题，有高等数学的背景设为大于等于2的某个确定的正整数，集合，其中诸，.作和，共有个和，其中有些可能是相同的.称为这些和中互不相同的数的个数．例如时，；时，．（Ⅰ）时，求（Ⅱ）当，且～恰构成，的等差数列时，求；表。若数表的对应位置上至少有一个不同，就说是两张不同的数表。则满足条件的不同的数表的张数为（A）144（B）192（C）216（D）576对于的一个排列，可以9个映射满足，而共有个排列，所以满足条件的数表共有张，故选C。注本题为2005年四川预赛题在正2006边形中，与所有边均不平行的对角线的条数为（C）。(A)2006(B)(C)(D).正2n边形，对角线共有条。计算与一边平行的对角线条数，因，与平行的对角线的端点只能取自2n-4个点，平行线共n-2条。故与某一边平行的对角线共n(n-2)条。由此可得与任何边都不平行的对角线共有n(2n-3)-n(n-2)=n(n-1)条。因此正确选项是C。注本题为2006浙江预赛题将n2个互不相等的数排成下表：a11a12a13…a21a22a23…an1an2an3…ann先取每行的最大数，得到n个数，其中最小数为x；再取每列的最小数，也得到n个数，其中最大数为y。试比较x和y的大小。先讨论n=3的情况，任取两表：137123256456894789左上表中x=6，y=4；右上表中x=3，y=3。两个表都满足x≥y，所以可以猜想x≥y。对一般情况，设x是第i行第j列的数a（i，j），y是第l行第m列的数a（l，m）。考虑x所在的行与y所在的列交叉的那个数，即第i行第m列的数a（i，m）。显然有a（i，j）≥a（i，m）≥数a（l，m），当i=l，j=m时等号成立，所以x≥y。给定大于2004的正整数n，将1、2、3、…、分别填入n×n棋盘（由n行n列方格构成）的方格中，使每个方格恰有一个数。如果一个方格中填的数大于它所在行至少2004个方格内所填的数，且大于它所在列至少2004个方格内所填的数，则称这个方格为“优格”。求棋盘中“优格”个数的最大值。为叙述方便，如果一个方格中填的数大于它所在行至少2004个方格中所填的数，则称此格为行优的。由于每一行中填较小的2004个数的格子不是行优的，所以每一行中有n－2004个行优的。一个方格为“优格”一定是行优的，所以棋盘中“优格”个数不大于。 另一方面，将棋盘的第i行，第（大于n时取模n的余数）列中的格子填入“*”。将1、2、3、…、2004n填入有“*”的格子，其余的数填入没有“*”的格子。没有“*”的格子中填的数大于有“*”的格子中任何一个数，所以棋盘上没有“*”的格子都为“优格”，共有个。 此时每行有2004个格子有“*”，每列也有2004个格子有“*”（如图）。实际上，当时，第i列的第1、2、…、i、n+i－2003、n+i－2002、...、n行中有“*”。当时，第i列的第i－2003、i－2002、...、i行中有“*”。所以每行有2004个格子有“*”，每列也有2004个格子有“*”（如图）************************所以棋盘中“优格”个数的最大值是。注本题为首届东南MO试题-4某中学某班48位同学来自全省各地，原来并不全部相识。（1）开学一星期后，每位同学都恰好认识了班上其他11位同学。是否一定存在这么5个人，他们之间两两都不相识？请证明你的结论；（2）开学一个月后，每位同学认识班上其他同学都超过36人。是否一定存在这么5个人，他们之间两两都相识？请证明你的结论。⑴不一定.下面给出一个反例：48位同学分别分在4个宿舍，每个宿舍12人。一星期后，同宿舍的同学相互相识，若每个人都不认⑵一定存在．设a是班上的同学，集合A是与a相识的同学组成的集合，则card(A)＞36，从中找一个同学b，集合B是与b相识的同学组成的集合，card(B)＞36，且card(A∩B)=card(A)+card(B)－card(A∪B)＞36+36-48=24；在集合A∩B中找一个同学c，集合C是与c相识的同学组成的集合，card(C)＞36，则card(A∩B∩C)=card(A∩B)+card(C)－card(A∩B∪C)＞24+36-48=12．在集合A∩B∩C中找一个同学d，集合D是与d相识的同学组成的集合，card(D)＞36，则card(A∩B∩C∩D)=card(A∩B∩C)+card(D)－card(A∩B∩C∪D)＞12+36-48=0；可以在集合A∩B∩C∩D中找一个同学e，这5个同学a，b，c，d，e相互都认识．已知，对于，定义为A中所有元素之和，问：T有多少个非空子集A，使得为3的倍数，但不是5的倍数？对于空集，定义.令.对于，令，则，因此，当且仅当.有以下几种情况：从而满足的非空子集A的个数为＝87.若，，则.由于，故满足，的的可能值为15，30.而15＝8＋7＝8＋6＋1＝8＋5＋2＝8＋4＋3＝8＋4＋2＋1＝7＋6＋2＝7＋5＋3＝7＋5＋2＋1＝7＋4＋3＋1＝6＋5＋4＝6＋5＋3+1＝6＋4＋3＋2＝5＋4＋3＋2＋1，36－30＝6＝5＋1＝4＋2＝3＋2＋1.故满足，，的A的个数为17.所以，所求的A的个数为87－17＝70.注本题为07CWMO-1设S={1,2,...,50},求最小正整数k，使S的任一k元子集中，都存在两个不同的数a和b，满足(a+b)整除ab.设a,b的最大公因数为d,a=a1d,b=b1d,则(a1,b1)=1.代入(a+b)|(ab)得到(a1+b1)|(a1b1d).由于(a1+b1,a1)=(a1+b1,b1)=(a1,b1)=1,故(a+b)|(ab)的充要条件是(a1+b1)|d.令d=k(a1+b1)得到满足条件的所有数组a=ka1(a1+b1),b=kb1(a1+b1).可设a1<b1≤6,列出S中所有23个(a,b)对:(a1,b1)(a,b)(1,2)(3,6),(6,12),(9,18),(12,24),(15,30),(18,36),(21,42),(24,48)(1,3)(4,12),(8,24),(12,36),(16,48)(2,3)(10,15),(20,30),(30,45)(1,4)(5,20),(10,40)(3,4)(21,28)(1,5)(6,30)(2,5)(14,35)(3,5)(24,40)(4,5)(36,45)(1,6)(7,42)现在以S为顶点集作关联图,图中有26个孤立点{1,2,11,13,17,19,22,23,25,26,27,29,31,32,33.34,37,38,39,41,43,44,46,47,49,50},其余24个点(23条棱)分为3个连通支(见上图).从图看出,可以选取38个点互不相邻:26个孤立点以及12个点{14,7,21,5,4,9,8,16,3,40,15,45}.因此k≥39.另一方面,任一39元子集中至少有13个点不是孤立点.它们分布在12个相邻对中:(14,35),(7,42),(