【4-组合】7.组合构造【讲师版】

1、 课程类型数学组合构造+组合复习”讲义编号：学员：年级：授课日期：讲师：授课方式（在线或线下）：（线下填）授课教学点：知识定位*组合构造虽然需要一定天分和幸运的成分，但也有规律可循。本节主要介绍两种构造方法。然后进行组合数学的习题课。知识梳理字典排序法在我小的时候，还没有手机这种东西（同学们听过传呼机么？），网络也并不发达和广泛。所以那时候我们遇到生字都要查字典。其实字典里将汉字排列是遵循一定规律的。我们知道英文字典排序都是按照权重abcd.z来排列的。汉语字典也是这样，首先按照拼音排序，当两个汉字拼音一样时，按照笔画多少排序，当笔画也一样时，就按照偏旁部首的下笔顺序来排列。在遇到数学问题时，

2、我们在做枚举举例时，同学们也可以按照这样的规律来进行枚举：将参与的元素赋予权重，然后按照权重来枚举，这样可以保证不重不漏。如将由A、B、C三个字符组成的全排列枚举出来：ABC、ACB、BAC、BCA、CAB、CBA轮换排序法轮换排序法特别适合有一定规律的枚举，将参与排序的元素按照轮换顺序转一圈，这种方法相对于字典排序法，优势在于枚举时省力气，但却不能有效保证不重不漏，需要枚举后加以验证。如将由A、B、C三个字符组成的全排列枚举出来：（ABC,BCA，CAB），（CBA，BAC，ACB）例1将7X7的点阵中的某些点染上红色，当由某四个顶点组成的底和高分别平行于点阵的底和高矩形四个顶点都是红色时，

3、我们称这个矩形为红点矩形。求：最多能将点阵中的都少个点染色，使得不存在红点矩形？【解答】21个首先证明至多21个红点。设第i行有x,个红点，设x+x+.+x=x为所求的红点数。i127我们把每行的每两个红点所在的列记成数对形式，如若某两个同行的红点所在的列分别为3、7，则记存在数对（3,7），显然同行红点组成的点对不同。则不存在红点矩阵等价于所有红点组成的点对没有重复的。又由17组成的点对共C2二21个，故有C2C2二21TOC o 1-5 h z7xi7i=1X2+X2+.+X2(x+X+.+X)1271271277故-X-420，解得14X21。接下来证明21个是可以的。这就涉及到构造方法

4、，首先我们用字典构造法轮换构造法：故21能取到，证毕。例2某乒乓球培训班共有n位学员，在班内双打训练赛期间，每两名学员都作为搭档恰好参加过一场双打比赛。试确定n的所有可能值并分别给出对应的一种安排比赛的方案。【解答】假设比赛了K场，那么由题目假设，一场比赛出现了2对队友，所以C2=2k，也就是说4k=n(n-l),那么得到nn=4l或者41+1,期中1eN,下边证明，对于任意的n=41,或者41+1,其中leN,都可以构造出满足要求的比赛：n=41+1,的时候，对于L使用数学归纳法：当L=1的时候，N=5，此时假设这5名选手为A,B,C,D,E,那么如下安排比赛即可，AB-CD,AC-BE,B

5、C-DE,AE-BD,AD-CE.设当L=M时结论成立，则L=M+1时，设4M+5选手为A,B,C,D,EF1,F2,F1,F2.,F1,F2,由归纳11222m2mF1,F2,F1,F2,F1,F2假设，可以安排E,11222m2m之间的比赛，使得他们之间每两位选手的作为队友恰好只参加F1,F2,F1,F2过一次比赛，还剩下A,B,C,D,E,相互的比赛和A,B,C,D与112m2m之间的比赛，A,B,C，D与112m2m之间的比赛安排如下：AF1与BF2,AF2与BF1,CF1与DF2,CF2与DF满足要求。LLLLLLLL最后将这些比赛总计起来，就是满足要求的4M+5位选手之间的的比赛了

6、。由数学归纳法得证，N=4L时，对L使用数学归纳法，可以类似方法证明(略)综上所述，N的所有可能取值是N=4L或4L+1，其中LeN.例3能否将正整数集合N+分划为两个不相交的集合A和B,满足:A中任意三个数不成等差数列不能由B中的元素组成一个非常数的无穷等差数列【解答】1t1!*2*3)r则A中任意三个数不国难的为了使B=M”1满足条件(灯反冲=*4r.p-y-“T-；坷为若二4)及Ii=-丸满广成等差数列则“一C故只要口tP:威茅差数列*耍构造这样的A是只要满足对任意宀dEI等差至少有_项属于A*I解法一将首项为s公差为的无穷等差数列用心表示易将所有总数无穷等差数列(非常数列厂排序如下：(

7、1(匚2).(2,1).1.;2,2).(3-!)*-排序的规律是:先看&+的大小+小者排肘-口-山卜的心较小的排前申按下列方式构造数列血、如，设4=X如血，H.4已瑕出侧在第+i个等差数列中取大于汕的某一顼为卄B令八=a2，知人则因2a,r(n=I*2+)故A中任阿个数不成等差数列再令B=N+A则因为任何正整数的非常数列的无卜是饭列都有一项属F儿故B中没育非常数列的无穷等差数列于是存在満足题H条件的集合A和乩llfl$分析二同分析知易构造满足条件的儿为门吏JBwNA潇足条件只须满足对任意-dEN-无穷等塗数列厶+哼崟2*中老1闪witUR研*th*前UL$只娶af1阳个数【q成比=曲斗口的降

8、式使1次取列心的fdiL存亦棊个筹寸f-m1町沁4tocrtz*Nh氏门尢1?r,魁任意d的怙蹴这只要A中皆有无骑多个形如|&为尤穷尊蛊数a的它!的数即氐存（ll.lM-k山td取玛解袪二1111札州IM：UU几UJ（:中几M!小6!1+1JtA：r!+h氓卜讣（我中Hi.tr(h1Jf.乃=A,则将数从小01大排列时从第二项趙*誓一坝大于前面一项的2倍.故A中任彳数彳成等挖数列丫其次卅中粒有非常数列的无穷辱差数列.,:则胡！4汕；弋lZ足中_个非常数列的无穷等普数fftA的构造知存在无穷多令mt打匚*jtfktfi筋*町见存在薦足条件门M2的集合A与鱼试题演练1）证明：能将不同的完全平方数填

9、满mn的矩形方格表中的每一个小方格，使得每行、每列的和也是完全平方数。【答案】2）对任意正整数n在平面内是否存在n个不在同一直线上的点，使得任意两点间的距离都为正整数?【答案】3）对任意正整数n,平面内是否存在一个有限点集M,使得对任一点pM，在M中恰有n个到p的距离都等于1的点。【答案】科=I时取M为长度等于1的线段的两个端点符合要求设軒=缸弍(I在有限点集/VL使对任意PCM,M中恰有k个到p的距离等于1的点.那时.以M中处个点为圆心J为半桂作同*再将顶I心耳该圜上的每卜工占连一线段以及在M中每两点连一线段由于所连线段数有限故平血内存4丿向f与上述所连的每一条线段都不平行将点集沿/方向平移一个怕位氏得到直集“*凤!门血=0于墨对任意p：MJMf在MJMf中恰有昏十1个点到P的胆鸨等于1故n-k+1时MUM满足题目要求*驶对也种历*存住满足题目要球的点集必讲师评价知识点课后掌握情况所需习题编号是否需要课时加强课后掌握情况评分：1对本知识点毫无所知，闻所未闻。2了解该知识点，能完成简单的识记题。3理解该知识点，能运用其分析解答简单问题。4把握知识的意义，但缺乏练习与手感，解答稍难的题目速度慢。5深刻了解知识