组合优化与组合构造讲义.doc

组合优化与组合构造讲义 林 常 1.概 述一.组合数学题型1.计数2.存在性3.构造4.最值二.主要方法1.递推与归纳.(1).I型归纳法.定跨度:起点个数等于跨度.不定跨度:起点个数等于1.递推关系的阶数与初始条件.(2).II型归纳法(最小数原理).设P(n)是关于正整数的命题.若由P(n)不成立可推出存在正整数n1可推出P(n1)成立.则P(n)对一切正整数成立.(4).乘积归纳法.若P(n)对全体素数成立,且由P(m)及P(n)成立可推出P(mn)成立.则P(n)对一切大于1的正整数成立.若P(n)对全体素数幂成立,且由P(m),P(n)成立及(m,n)=1可推出P(mn)成立.则P(n)对一切大于1的正整数成立.2.调整法(向较优目标逼近).设 : SR有最大(小)值(例如,当(S)为有限集或在紧集S上连续时).若S的子集A满足:对任一xSA,都有xS使得(x)(x2x10,将它们沿圆周顺时针排成a1,a10使S=(a11=a1).最小.不妨设a1=x1,a20,与S最小矛盾.故a2=x10.同样,若a10=xi (i8), aj=x9(3j9).将顺时针aj,a10段反序,其它不变,得到新的排列,二者和数之差 SS=aj-1x9+xix1aj-1xix9x1=(x1aj-1)(xix9)0,矛盾.故a10=x9.2).一般,可以用同样的整段反序调整法证明:将x1xk排成y1,yk使得ay1+y1y2+yk-1yk+ykb最小,则当abx1时必y1= xk, yk=xk-1,而当xkba时必y1=x1,yk=x2.从而得到上述结论. 最后,对于和为1995的不同分拆,S的最小值在xi=11i (2i10)时达到.事实上,反设k是使此式不成立的最大i,即xk11k,而ik时有xi=11i,将x1,xk分别改为x1+1, xk1,所得各数仍两两不同.由于x1的两个相邻数(x10,x9)是最小的两数,故调整后S变小,矛盾. 因此,和数最小的数组是1950,1,9,3,7,5,6,4,8,2.最小值是 1950+9+27+21+35+30+24+32+16+3900=6044.一般,给定正整数k,n (k4,n).互不相同的正整数a1,a2,ak之和为n,则和数S=(ak+1=a1)在(a1,a2,ak)=(n,1,k1,3,k3, k4,4,k2,2) 时最小.*若要求S最大,x1x2xk的排列应是x1x2x4x5x3.其中x1,x2,xk=x+u,x,k-3,.,k-4,k-2 u=1或2 .un(mod 2),x=.2.设M=1,2,3,1995,A是M的子集且满足条件:当时,A中元素的个数最多是多少?. 解.=133,=8.对于9133这125个数中的每个k,k与15k不能同属于A.因此|A|1995125=1870. 另一方面,取A=1,2,8134,135,1995,则|A|=1870.对于任一xA,当1x8时1515x120,x134时15x2010都不属于A. 因此A中元素个数的最大值是1870.一般,给定整数m,n(nm1).S=1,2,n的子集A满足:当时,A中元素个数的最大值为n,其中Tm(n)是n的m进制数码的交替代数和,设n=, 则Tm(n)=a0a1+a2+(1)kak.证明.记ni=,则有ni=,故mnini-1n或mxB,符合条件,故这个上界可达到. 与此相近的整除链问题.正整数a1a2ak称为一条整除链,如果对1i1,n2k-1),集合S=1,2,n的子集A不含长为k的整除链,则A的元素个数的最大值为n. 证明.对1中的任一奇数b,有唯一的正整数i=i(b)使b2i-11,故k97. 另一方面,由于后3行只有75格而全表有100行,故必有一行xr,j (j=1,2,25)重排后全部在前97行.因此i97时恒有yi,jxr,j(j=1,2,25),1.因此k的最小值是97. *对一般的mn表(mn2),令m=qn+r (1rn).在原表的r个列中放q+1个0,nr个列中放q个0,并使任2个0不在同一行,其它方格中全部放.此时每行之和都是1.重排后前mq1行的和都是1,故kmq. 另一方面,由于后q行只有qn格而全表有mqn行,故必有一行xr,j (j=1,2,n)重排后全部在前mq行.故imq时恒有yi,jxr,j(j=1,2,n),1.因此k的最小值是mq= m.4.对于正整数a,n, 定义Fn(a)=q+r,其中q,r为非负整数,a=qn+r, 且0rn.求最大的正整数A, 使得存在正整数n1,n2,n3,n4,n5,n6, 对于任意的正整数aA,都有 =1. 解.将满足如下条件的最大正整数B记为xk: “存在正整数n1,n2,nk,使得只要正整数aB,就有=1.”.显然,xk+1xk,且本题所求的最大正整数A即是x6.(1).由于F2(1)=F2(2)=1,故x12.又因F1(2)=F2(3)=2,且n13时=2,故x11,q0. 于是1qn11 xk+1, =q1+n11xk.从而有 xk+1xk+()2xk+()2=+.由于xk为偶数,故为整数(实际上它还是偶数),因此xk+1.另一方面,取n1=+2,由于=n1+,对于每个a,令a= qn1+r,那么或者q=,r;或者q1,rn11+1.两种情况下都有q+rxk.因此xk+1=.最后由x1=2逐次推出x2=4,x3=10,x4=40,x5=460,x6=53590.于是所求的最大正整数A=53590.5.对于整数4,求出最小的整数,使得对于任何正整数,集合的任一个元子集中,均有至少3个两两互素的元素. 解.取m=2,由容斥原理,集合2,3,n+1中被2或3整除的数的个数为 .这些数中的任意3个或有2个同被2整除,或有2个同被3整除,不会两两互素.因此f(n)+1.记+1=kn.下证对任何正整数,集合的任一kn元子集中,均有至少3个两两互素的元素.从而得出f(n)=+1. (1).首尾为奇数的3个接连整数2u+1,2u+2,2u+3两两互素;因此,4个接连整数中必有3个两两互素. (2).a,a+1,a+5的任一5元子集A中必有3个元素两两互素.事实上,若不属于A的数b是a,a+1,a+4,a+5之一,则A中有4个接连整数;若b为a+2,a+3中的偶数,则A中有首尾为奇数的3个接连整数.若b=a+2为奇数,则a为奇数,(a,a+4)=(a,a+1)=(a+3,a+4)=1,又(a,a+3)=(a,3)和(a+1,a+4)=(a+1,3)等于1或3且二者不能同时等于3,故(a,a+1,a+4)和(a,a+3,a+4)中至少有一组两两互素.同理当b=a+3为奇数时(a+1,a+2,a+5)和(a+1,a+4,a+5)中至少有一组两两互素. (3).设n=6q+r,任意n个接连整数可分为q个接连6数段Ii和一个接连r数段R(r=0时此段为空).列出r=0,1,5时对应的kn值:r012345kn4q+14q+24q+34q+44q+44q+5由此可知,任一kn元子集或者含有某个段Ii中的5个数,或者含有段R中的4个接连数,由(2),其中必有3个元素两两互素.6.设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).可设a1k2kt,即从左到右为接连k1k2个1,k2k3个0,k3k4个1,.t=1时,n=1, f(n)=1+ f(0)=.t=2时,n=, f(n)=n+f(1)= n+1=.设段数为t时f(n)=,则段数为t+1时 f(n)= n+f(n*), n*的段数为t,故f(n)= n+= n+=. 因此,m(n)=1+,其中t是n的二进制数码段数. *若将题目条件改为任何两个取出的不同数之和不是2的方幂,类似的分析可得 g(2k+r)=r+1+g(2kr1), m(n)=1+8.试求不小于9的最小正整数n,满足:对任给的n个整数(可以相同)a1,a2,an,总存在9个数(1i1i2i9n)及bi4,7(i=1,2,9),使得为9的倍数.解.取12个数:8个0,2个3,2个1.其中任选9个x1,x9,若含有1,则 b1x1+b9x91或2(mod 3), 不能被9整除.若不含1,则必含3, b1x1+b9x93或6(mod 9),也不被9整除. 故n13. 引理.任意5个整数中必可选出3个,其和被3整除.(证略) 由此推出,任意3k+2个整数中可选出3k个,其和被3整除. 任给13个整数a1,a13.若其中有11个是3的倍数,设为a1=3x1,a11=3x11.则由x1,x11中可选出9个xi,其和被3整除.相应的9个4ai之和被9整除. 若a1,a13中3的倍数不多于10个,则至少有3个不被3整除,设是a11,a12,a13.由引理,a9,a10,a11,a12,a13中可选出3个(记作u,v1,v2),其和被3整除,且其中必有一个与3互素(设是u).再从a1,a8中选出6个(记作v3,v4,v8),其和被3整除.记v=v1+v2+v8,则这9个数之和 u+v=3r.如3|r,则9|(4u+4v1+4v2+4v8),已合要求.如3r,由于3|(u+v)且u与3互素,故u,v(mod 3)一个为1一个为2,即必有一个r(mod 3).当ur(mod 3)时7u+4v1+4v2+4v8=9r+3(r+u)被9整除,vr(mod 3)时4u+7v1+7v2+7v8=9r+3(r+v)被9整除.9.将边长为正整数mn的矩形分割成若干边长均为正整数的正方形,每个正方形的边均平行于矩形的相应边.试求这些正方形边长之和的最小值解.记所求最小值为f (m,n).显然f(m,m)=m. (1)对m归纳证明存在一种合乎题意的分法,所得正方形边长之和恰为mn(m，n).当m1时,命题显然成立.AA1BCD1Dmn 假设当mk时结论成立(k1).当mk1时,若nk1,则命题显然成立.若nk1,从矩形ABCD中切去正方形AA1D1D(如图),由归纳假设矩形A1BCD1有一种分法使得所得正方形边长之和恰为mnn(mn，n)m(m，n),从而原矩形ABCD有一种分法使得所得正方形边长之和为mn(m，n). (2)对m归纳证明f(m,n)mn(m，n). 当m1时n1,显然f(1,1)=1=1+1(1,1).假设对任意1nmk有f (m,n)mn(m，n). 若mk1,当nk1时显然f (m,n)k1mn(m，n) 当1nk时,设矩形ABCD按要求分成了p个正方形,其边长分别为a1a2ap.显然或者a1n或者a1n 若a1n,则在AD与BC之间的与AD平行的任一直线至少穿过二个分成的正方形(或沿其边界).于是a1a2ap不小于AB+CD=2mmn(m，n). 若a1n,则一个边长分别为mn和n的矩形可按题目要求分成边长分别为a2，ap的正方形,由归纳假设, a2apmnn(mn，n)m(m，n),从而a1a2ap mn(m，n). 于是当mk1时也有f (m，n)mn(m，n). 结合(1),(2)可知f (m，n)mn(m，n).10.地面上有10只小鸟在啄食，其中任意5只小鸟中至少有4只在一个圆上，问有鸟最多的圆上最少有几只鸟？ 解.依题意,小鸟看成平面上的点.任意5点取一共圆4点组,共个,每个4点组至多属于104=6个5点组,故不同的共圆4点组不少于=42个,总点数为168.必有一点A至少属于=17个4点组.每组除A外还有3点,共51点.另外9点中必有一点B至少属于其中=6组.每组除A,B外还有2点,共12点.另外8点中有一点C至少属于其中=2组.这2组的第四点D,E不同.由于A,B, C三点确定一个圆,故这2组的圆重合,即A,B,C,D,E五点共圆,记为圆周S. 下面证明另外5点中至少有4点在S上.反设有2点M,N都不在S上.A,B,C,M,N中有4点共圆,但这个圆不能含A,B,C三点(否则M,N中有一点在S=(A,B,C)上),设是S1=(M,N,A,B).由C,D,E,M,N同理可设有圆S2=(M,N,C,D).最后由A,C,E,M,N得到有圆 S3= (M,N,A,C), ( M,N,A,E),(M,N,C,E)之一.由于(M,N,A),(M,N,C)分别确定圆S1,S2,故S3=S1或S2,即S3上含有S的3个点,从而S3=S,矛盾.因此,有鸟最多的圆上最少有9只鸟.11.某乒乓俱乐部组织交流活动，安排符合以下规则的双打赛程表，规则为：(1).每个参赛者至多属于两个对子; (2).任意两个不同对子之间至多进行一次双打；(3).凡表中同属一对的两人就不在任何双打中作为对手相遇.统计各人参加的双打次数，约定将所有不同的次数组成的集合为“赛次集”.给定由不同的正整数组成的集合A=a1,a2,，ak,其中每个数都能被6整除.试问至少必须有多少人参加活动，才可以安排符合上述规则的赛程表，使得相应的赛次集恰为A，请证明你的结论. 解.设a1a2ak.考虑赛次为ak的人A,若他只属于一个对子(A,B),则与之比赛的ak对互不相同,由于每人至多属于2对,这ak对至少有= ak人,都不同于A,B.故总人数不少于ak +2.若A属于2个对子(A,B),(A,C),则至少有另外的对与其中之一比赛,这些队的至少人不同于A,B,C.故总人数不少于+3(ak +2).因此总人数恒不少于+3.为了证明存在符合要求的+3人赛程表,先证引理任给正整数集S=b1b2bk,存在bk+1点的简单图,其顶点的度集(即所有不同的度组成的集合)恰为S.证.对k归纳.引入符号:Kn(n点完全图,每点度为n1),On(n个孤立点图,每点度为0),两个图之和G1+G2(合并,每点度不变,点数相加),之积G1G2(合并后添加所有V1-V2间的棱,G1每点的度增加|G2|,G2每点的度增加|G1|.点数相加).|G|表示图G的点数.k=1时符合要求. k=2时符合要求.设度集为k元正整数集c1c2ck的ck+1点简单图为H(c1,c2,ck).则对任一k+2元正整数集 b1b2bk+11时,上述8个三角形的面积都大于.故只有2个好三角形.于是好三角形个数的最小值是2.13.某市有n所中学,第i所中学派出Ci名(1Ci39,1in)学生来到体育馆观看球赛,全部学生总数为=1990.看台上每一横排有199个座位,要求同一学校的学生必须坐在同一横排.问体育馆最少要安排多少个横排才能保证全部学生都能坐下? 解.199+1=258,1990=7925+15.取n=80,其中79所各25人,1所15人.由于每排最多坐7所25人校,故排数不小于=12. 另一方面,逐个整校地将前5排占满(每排的最后一校有人暂时无座位),总共不少于5200=1000人.各排最后一校的总人数不多于539=195,可在第6排就坐.因此无论各校人数如何分布,6排必可坐下不少于1000人.12排必可坐下不少于2000人.故保证全部学生都能坐下的最少排数是12.14.设A=1，2，3，17，对于映射设从A到A的一一映射f满足条件:存在正整数M，使得： 试对满足上述条件的一切f，求所对应的M的最大可能值，并证明你的结论. 解.将A等同于Z17(17=0),对于满足条件的任一f,作凸17边形,其顶点依次为0,1,2,16.对于每个i A和每个正整数mn)时得到或者 fm-n(i)=j, fm-n(i+1)=j+1,或者 fm-n(i)=j+1, fm-n(i+1)=j.从而fm-n(i+1)fm-n(i)=1,也矛盾.因此,不同的(m,i)对应的对角线不同.(m,i)的个数17(M1)不大于对角线的条数.故M8.另一方面,考虑A上的映射f(i)3i(mod 17).由于3与17互素,f是一一映射.fm(i)=3mi.因此fm(i+1)fm(i)=1当且仅当3m1 (mod 17).直接计算余数m123456783m(mod 17)39745261由表看出M=8.因此,M的最大值是8.15.某次考试有5道选择题，每题都有4个不同答案供选择，每人每题恰选1个答案，在2000份答卷中发现存在一个n，使得任何n份答卷中都存在4份，其中每两份的答案都至多3题相同.求n的最小可能值. 解.第14题的不同答案共有44=256种,2000=7256+208.任意2000份答卷中必有8份的14题答案全同,记为A组.余下1992份答卷中又有8份的14题答案全同,记为B组.余下1984份中还有8份的14题答案全同,记为C组.ABC这24份答卷的任何4份中都有2份属于同一组,其14题答案全同,不合要求.因此n25.下证存在答卷的一种分布使得n=25符合要求.记每题的答案为1,2,3,4.则每份答卷是一个5元数组(a1,a2,a3,a4,a5),ai1,2,3,4.满足4|(a1+a2+a3+a4+a5)的所有不同答案,共有44=256种(a1,a2,a3,a4可任取,取定后a5唯一确定).每2种不同的答案都至多3题相同(若有4题相同,第5题也相同).任取其中250种,每种8份,共得2000份答卷.这2000份答卷的任何25份中都有4份的答案互不相同,从而每两份的答案都至多3题相同. 因此, n的最小可能值是25.16.设X是一个56元集合,求最小的正整数n,使得对X的任意15个子集,只要它们中任何7个的并的元素个数都不少于n,则这15个子集中一定存在3个,它们的交非空解.首先证明.将X的元素排成78表(每格1个元素).每行Ai (1i7),每列Bj (1j8)各作为一个子集,|Ai|=8,|Bj|=7,不同的Ai之间及不同的Bj之间交集为空,因此这15个子集中任意3个的交为空(必有2个同为行或同为列).于是必有7个的并的元素个数少于n.设这7个中k个为Ai,由| AiBj|=1得到 8k+7(7k)k(7k)n. n1+k26k+49=(k3)2+4141.次证合乎条件.反设存在X的15个子集,其中任何7个的并不少于41个元素,而任何3个的交都为空集.因每个元素至多属于2个子集,不妨设每个元素恰好属于2个子集(否则在一些子集中添加一些元素,上述条件仍然成立),由抽屉原理,必有一个子集(设为A),至少含有8个元素,又设其它14个子集为.不含A的任何7个子集都对应X中的41个元素,所有不含A的7子集组一共至少对应个元素.另一方面,对于元素a,若,则中有2个含有a,于是a被计算了次;若,则中有一个含有a,于是a被计算了次.因此，由此可得.矛盾综上所述, n的最小值为41*设P是一个2009元集合，使得对P的任m个子集，只要它们中任41个并的元素个数都不少于1409，则这m个子集中一定存在三个，它们的交集非空，求m的最小值。解.若m90,将P的元素排成4149表,每行,每列各作为一个子集,共90个.其中任意3个之交集为空.设任意41个中k个为行子集,则它们之并集的元素个数 49k+41(41k)k(41k)=k233k+4124121617=1409,矛盾.故m91.反设有P的91个子集,其中任意41个之并集的元素个数都不少于1409,而任意3个之交集都为空.可设P的每个元素恰属于2个子集.于是有 14092009(), 140990912009(90914950),即164853164738,矛盾. 因此满足条件的m的最小值是91.3.组合构造(设计)一.构造(设计)方法1.直接构造.利用特征量或模型.利用对称性(循环生成,马步生成)2.分步,分块构造.调整法.3.递推构造.4.证明所作的设计符合要求.二.例题选讲1.平面直角坐标系中,纵,横坐标都是整数的点称为整点.请设计一种方法将所有的整点染色,每一个整点染成白色,红色或黑色中的一种颜色,使得 (1).每一种颜色出现在无穷多条平行于横轴的直线上无穷多次; (2).对任意白点A,红点B和黑点C,总可以找到一个红点D,使得ABCD为一平行四边形.证明你设计的方法符合上述要求.解.按坐标(x,y)的奇偶性染色: x+y为偶数(即x与y同奇偶)时染红色; x奇y偶时染白色; x偶y奇时染黑色.此时 (1).每条水平直线y=k(kZ)上都有无穷多个红色点,每条y=2k(kZ)上有无穷多个白色点,每条y=2k+1(kZ)上有无穷多个黑色点. (2).设A(x1,y1),B(x2,y2),C(x3,y3) (x1,y3为奇数,y1,x3及x2+y2为偶数).则D=A+CB=(x1+x3x2,y1+y3y2).由于x1+x3x2+y1+y3y2= (x1+y3)+(y1+x3)(x2+y2)为偶数,故D是红色点.只要证明A,B,C不共线,ABCD就是个平行四边形. 反设A,B,C共线,则(x2x1)(y3y1)=(x3x1)(y2y1).但y3y1与x3x1为奇数,故x2x1与y2y1同奇偶.可是x2x1+y2y1=(x2+y2)(x1+y1)为奇数,矛盾. 因此上述染色方案符合要求.2. n支球队参加单循环赛(每两队赛1场),每队每天至多赛1场.全部比赛最少要历时多少天?解.每天能安排的比赛不多于场,共有=场比赛.故比赛天数不少于 =. n为偶数时n个队标号为0,1,2,n1,取一个圆,圆心记为0,圆周的n1等分点依次记为1,2,n1.第i天安排0与i以及所有关于直径0i对称的两队比赛.共历时n1天.显然每队每天都赛1场,共赛场.为了证明这样的安排符合要求,还要说明任何两队都赛且只赛过1场.显然 0与1,2, n1赛过.而对任意的1i1)的数称为方幂数.证明,存在公差大于0的2007项等差数列,它的每一项都是方幂数,而且任意多个不同项的算术平均值也都是方幂数.证.显然,i2007! (1i2007)中任意多个不同数的算术平均值都是整数.而且每个数同乘上x时相应的平均值也乘上x.记上述2007个数及其所有算术平均值构成的集合为M,只要证明: 对任一正整数集M=a1,a2,an,可找到正整数x,使得xa1,xa2,xan都是方幂数. 设所有ai的全部素因子为p1,p2,pm .每个ai含这些素因子的方次为ki(1),ki(2),ki(m).取n个不同的素数q1,q2,qn.考虑m个同余式组(1jm) j k1(j)(modq1)k2(j)(modq2)kn(j)(modqn) . 由孙子定理,它们有非负整数解1, 2, m.令x=,则对每个ai=,由于j+ ki(j) 0(modqi),可记j+ ki(j)=qiri(j) (ri(j)为非负整数).于是xai=是qi次方幂数. 因此xi2007! |1i2007为所求的数列.7.求所有正整数n,使得集合1,2,3,3n可以划分为n个三元子集ai,bi,ci,满足条件: 对每个i(1in),ai+bi=ci .解.(1).先解辅助问题:求所有正整数n,使得集合1,2,3,2n可以划分为n个二元子集ai,bi,满足条件bi = ai +i.整体求和,=2+, 2|, n0,1(mod4) .将两个等长的相邻整数段(ak,ak+1,a)与(b,b+1,b+k)反序配对,产生公差为2的差值段ba,ba+2,ba+4,ba+2k.用这一方法加上适当的尝试调整给出所需的配对.n=4k时 ,