第七讲组合综合问题本讲概述在前六讲我们对组合数学中的不少专题进行了研究，本讲不再进行具体某个专题的学习，而是通过一些综合性的问题的探讨来寻找组合数学“解题的感觉”.本讲的题目与前面相比，综合性更强，难度在二试与冬令营之间，可能需要综合应用前面所学的多种组合知识乃至其它学科的知识来解决.事实上，组合与几何学、数论相联系形成的组合几何、组合数论问题往往难度较大，又能同时考察多个学科，是命题人青睐的对象，而在组合问题的探索过程中，特别是组合极值问题中，常常用到代数知识特别是数列与不等式知识.教师备注：本讲主要研究两大方面问题：（1）组合与其它学科相结合（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）如果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市甲队之外，其它各队已赛过场次依次为0,1,2,,29,30考场赛过30场和0场的队，经简单推理知此两队必为同城队；接下来依次配对（29,1），（28,2），…，（14,16）.只有15没有配对，这就是乙队. 于是乙队赛过15场.【例3】 20支足球队参加比赛，每两队至多赛一场.为了使任何三队中都有两队赛过，球赛组委会安排了m场比赛，试求m最小值.高一·联赛班·寒假第7讲·教师版2【解析】 设A 队赛过k 场，是所有队中赛过场次最少的.与A 队赛过的k 个队，各至少赛过k 场，没有与A 赛过的19-k 个队中的任何两队B,C 必赛过（否则就出现A,B,C 三队两两未赛过，矛盾！）.于是比赛场数()22191(1)990902k m k k C k -≥++=-+≥, 于是至少要赛90场.下面给出一种比赛方案，使得恰赛90场：把20支队分成两组，每组10个队，同组两两都赛，不同组不比赛，共安排2102C 场比赛. 显然这个方案合要求.注 本题为组合中最难的安排赛程表题型，也可以把它看成一个图论问题.比赛方案是受到论证过程的结果启发构造出来的.【例4】 设k ，n 为给定的整数，2n k >≥. 对任意n 元的数集P ，作P 的所有k 元子集的元素和，记这些和组成的集合为Q ，集合Q 中元素个数是Q C ，求Q C 的最大值.【解析】 Q C 的最大值为knC . 因P 共有kn C 个k 元子集，故显然有kQ nC C ≤. 下面我们指出，对集合2{2, 2,, 2}n P =，相应的Q C 等于knC ，即P 的任意两个不同的k 元子集的元素之和不相等. 从而Q C 的最大值为kn C .事实上，若上述的集合P 有两个不同的k 元子集12{2,2,,2}k r r r A =， 12{2,2,,2}k s s s B =，使得A 与B 的元素之和相等，则1212222222k k r s r r s s M+++=+++=（设）. ①因①可视为正整数M 的二进制表示，由于i r 互不相同，i s 互不相同，故由正整数的二进制表示的唯 一性，我们由①推出，集合12{,,,}k r r r 必须与12{,,,}k s s s 相同，从而子集A B =，矛盾.这就证明了我们的断言.注 本题为2009江苏赛区复赛题. 这是一道典型的组合极值问题，难度并不太大. 这种问题一般分为两部分：构造与论证，分别考察不同的数学能力，因此是近年来的命题热点.【例5】 (1) 若 (n n ∈ N *) 个棱长为正整数的正方体的体积之和等于 2005, 求 n 的 最小值, 并说明理由；(2) 若 (n n ∈ N *) 个棱长为正整数的正方体的体积之和等于 20022005, 求 n 的最小值, 并说明理由.【解析】 (1) 因为 3333101000,111331,121728,132197====, 3312200513<<， 故 1n ≠.因为 3333200517281251252712553=+++=+++，所以存在 4n =， 使min 4n ≤． ……………… 6分高一·联赛班·寒假第7讲·教师版3若 2n =，因 3310102005+<, 则最大的正方体边长只能为 11 或 12，计算33200511674,200512277-=-=，而 674 与 277 均不是完全立方数, 所以2n = 不可能是 n 的最小值. ……………… 9分若 3n =，设此三个正方体中最大一个的棱长为 x , 由 328320053⨯>≥x , 知最大的正方体棱长只能为 9、10、11 或 12.由于 3932005⨯<, 5479220053=⨯-, 0829200533>⨯--, 所以 9x ≠.由于 510220053=⨯-, 332005109276--=, 332005108493--=,07210200533>⨯--, 所以10x ≠.由于 332005118162--=, 332005117331--=, 06211200533>⨯--, 所以 11x ≠.由于 33200512661--=, 33320051251525--=>, 所以 12x ≠. 因此 3n = 不可能是 n 的最小值.综上所述，4n = 才是 n 的最小值. ……………… 12分 (2) 设 n 个正方体的棱长分别是 12,,,n x x x ， 则3332005122002n x x x +++=．…………… ⑤由 20024(mod9)≡， 341(mod9)≡，得20052005668313668200244(4)44(mod9)⨯+≡≡≡⨯≡．…… ⑥ …… 15分又当 x ∈N* 时，30,1(mod9)x ≡±，所以31x ≡∕4(mod 9)， 3312x x + ≡∕4(mod9)， 333123x x x ++ ≡∕4(mod9). … ⑦ …………… 21分⑤ 式模 9, 由 ⑥、⑦ 可知, 4n ≥．而 33332002101011=+++，则2005200433336683333320022002(101011)(2002)(101011)=⨯+++=⨯+++6683668366836683(200210)(200210)(2002)(2002)=⨯+⨯++．…… 24分因此 4n = 为所求的最小值．注 本题为2005年江苏预赛16题. 这类与数论相联系的极值问题往往兼具组合构造与数论证明两大特点 但鉴于本题组合味道并不太浓，建议选讲.高一·联赛班·寒假第7讲·教师版4【例6】 假定100个人中的每一个人都知道一个消息，而且这100个消息都不相同。
