(组合数学)第5章 区间设计.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2011.11.09,*,组合数学第二部分,讲课老师：张承钿,2011.11.09,1,第,5,章区组设计,2011.11.09,2,内容,问题的提出,拉丁方与正交的拉丁方,域的概念,Galois,域,GF(p,),正交拉丁方的构造,正交拉丁方的应用举例,均衡不完全的区组设计,区组设计的构成方法,Steiner,三元素,Kirkman,女生问题,2011.11.09,3,问题的提出,有一块梯田种植,3,种不同的农产品,A,、,B,、,C,。由于高度、方位不同，所有其自,然条件有差异。按图,5-1,的,(a),种植，每种产品只在同层出现；而按图,5-1,的,(b),种植，则每种产品只在同一方位出现；按图,5-2,种植，则每种产品即在同层出,现，又同一方位出现。显然，按图,5-2,种植，实验结果较准确。,测试,4,种轮胎，同一牌子在汽车不同位置磨损程度不同，所以每种不能只测试,一个轮胎，用,4,辆小汽车,A,、,B,、,C,、,D,参加测试，如右,图所示。,这个测试的特点是，每一种品牌的轮胎都在不同的汽车,和不同的位置作了安排。每种轮胎都用了,4,次。,测试的次数也均衡，其中,A,、,B,、,C,、,D,是汽车的代号，,矩阵的元素是轮胎的品牌代号。,2011.11.09,4,问题的提出,再论梯田种植问题,农作物类：、,梯田高度：高、中、低,日照方向：东、南、西,进一步的问题：,种子是买来的，三家种子公司都提供这些种子，价钱差不多,三种农作物的出售价格也差不多，只是播种方式不一样,实验的目的是比较出哪家公司的种子质量好，哪种作物产量高。,？怎样安排实验,分析一：下面方法是否可行,如果把上面每块地（共九块）再分成三小块，每小块种上一家公司的作物,问题：每个小块的面积太小的话，无法判别产量,分成三次播种季节，每个季节种一家作物,问题：分三个季节的话，时间太长,分析二：下面结论是否成立,种子公司生产水平高，它的种子质量好，即公司,X,比公司,Y,好，则,X,的种子,A,、,B,、,C,应该比,Y,的种子,A,、,B,、,C,都相应的质量好。,农作物的产量不依赖于公司，即作物,A,比,B,产量高，则每家公司的作物,A,比,B,产量都高。,2011.11.09,5,问题的提出,重新描述梯田种植问题,农作物类：、,梯田高度：高、中、低,日照方向：东、南、西,种子公司：、,假如各个公司的实际产量如下：,即：公司,X,的,A,作物产量最高,？：有没有办法，只在一个,季节内种植后，就能判,别出结果？,2011.11.09,6,问题的提出,重新描述梯田种植问题,农作物类：、,梯田高度：高、中、低,日照方向：东、南、西,种子公司：、,在九块田分别种植三家公司的三种农作物，寻找如下方案的解：,每行（梯田高度）包含三个公司，及三种作物,每列（日照方向）包含三个公司，及三种作物,例如下图方案：具体产量：正交拉丁方：,各个作物的产量：各个公司的产量：,2011.11.09,7,拉丁方与正交拉丁方,拉丁方的定义：,由数,1,2,.,n,构成的,nn,矩阵：,如果数,1,2,.,n,中的每个都在每行和每列各出现一次，则称其为,n,阶拉丁方。,前面的,4,阶矩阵是拉丁方。如果把图,5-2,中的,A,、,B,、,C,用,1,、,2,、,3,代替，则我们,得到一个,3,阶的拉丁方。,36,军官问题,有,6,个不同地区的,6,种不同军衔的军官各一名，共,36,名。现要将他们排成,66,的一个方阵，要求做到：,(a),每行、每列都有军官来自,6,个地区；,(b),每行、每列都有,6,种军衔的军官,每个军官都有二个标志，即军衔和地区。我们把军衔按,1,至,6,编号，把地区也,按,1,至,6,编号，用,(,i,j,),表示某军官的来自,i,号地区，其军衔是,j,号。,如果我们不考虑军衔，只寻找满足条件,(a),的矩阵，则问题是求,66,的拉丁方。,同样，不考虑地区，只寻找满足条件,(b),的矩阵，则也是求,6,阶拉丁方。,当我们把,66,方阵中的军官用其军衔号,i,和地区号,j,组成的数偶,(,i,j,),替代后，组,成的方阵就满足：数偶,(,i,j,),的第一个数组成一个,6,阶拉丁方，第二个数也组成,一个,6,阶拉丁方，且数偶,(,i,j,),是唯一的。,2011.11.09,8,拉丁方与正交拉丁方,正交拉丁方的定义：,中的,nn,个数偶互不相同，则称,A,和,B,是互相正交的拉丁方。,例子,5-1,矩阵,都是,3,阶拉丁方，而方阵,中的,9,对数偶不同，故,A,和,B,是正交的。,36,名军官问题实际上就是求一对,6,阶,的正交拉丁方。并不是任意的,n,阶都有正交拉丁方。,36,名军官问题就是没有,解的。,2011.11.09,9,拉丁方与正交拉丁方,正交拉丁方的应用,正交拉丁方问题有实际的应用，例如测试药物：,有三种治发烧的药和三种治感冒的药配合起来给三位病人进行医疗实验，,要求在三天内每人都服过这几种药，要试验出哪种退烧药和感冒药配合起,来的疗效最佳。,用上述的二个,3,阶正交拉丁方，就可解决这个问题。,假设第,h,行、第,k,列的元素是,(,i,j,),，我们就在第,h,天让第,k,号病人服用第,i,种的,治发烧的药和第种的治感冒的药。,具体例子就是，在第二行、第三列是数偶,(1,3),，则在第二天三号病人服用,第一种治发烧的药和第三种的治感冒的药。,引理,5-1,设,A,是拉丁方，则,A,的转置,A,仍是拉丁方。,引理,5-2,设,A,是拉丁方，则通过置换,p,得到的方阵仍是拉丁方。,引理,5-3,设,A,是拉丁方，则存在置换,p,，使得通过它得到规范拉丁方，即,A,的第一行（或第一列）是,1,2,.,n,。,例子：,2011.11.09,10,正交拉丁方及其性质,一阶、二阶、三阶正交拉丁方,一阶拉丁方只有一个：,1,。也无所谓正交不正交。,二阶拉丁方只有二个：,它们不是正交。,三阶正交拉丁方至少有一个，就是前面的列,5-1,：,引理,5-4,设,A,和,B,是正交拉丁方，,p,是对换，,A,是,A,经过,p,置换后的拉丁方，,则,A,和,B,仍是正交拉丁方。,引理,5-5,设,A,和,B,是正交拉丁方，,p,是置换，,A,是,A,经过,p,置换后的拉丁方，,则,A,和,B,仍是正交拉丁方。,引理,5-6,设,A,和,B,是正交拉丁方，,A,是,A,的行规范方，,B,是,B,的行规范方，,则,A,和,B,仍是正交拉丁方。对于都是列规范的情况也成立。,这里附带说明一下，二个行规范的正交拉丁方，其第一行组成的数偶是：,(1,1),(2,2),.,(,n,n,),所有从第二行开始，它们没有相同的元素，即：，如果,i1,。,2011.11.09,11,正交拉丁方及其性质,定理,5-1,若存在,r(1),个,n,阶拉丁方两两互相正交，则：,r(n-1),。按,引理,5-6,，不妨设其都是行规范的。考察它们的第,二第一列的元素，共有,r,个。这些元素满足：,首先，都不能是,1,，即它们只能是,2,.,n,（共,n-1,个数）中的数；,其次，由于,r(n-1),，故至少有二个元素相等；,即有二个行规范的正交拉丁方，它们在,(2,1),这个位置是相等的，这就与,引理,5-6,相矛盾。故尔只能是：,r n,。,例子：三个四阶正交拉丁方：,2011.11.09,12,怎样构造正交拉丁方？,构造阶乘是素数的正交拉丁方,整数同余类,集合,M(m,r)=x|x Z,，,xr,mod(m,),，,r=0,(m-1),称为模,m,的一个同余类。,M(m,)=M(m,0),M(m,m-1)=0,1,(m-1),例子：,M(7)=0,1,6=,周日、周一、,、周六,同余加法和乘法：例如在,M(7),中,加法：,5+4=9 2 mod(7),，即周五的过,4,天后是周二,乘法：,5*4=20 6 mod(7),构造拉丁方的公式：,A,k,=(,a(k),ij,),nn,，,k=1,2,(n-1),，这里的,n,为素数,其中,a(k),ij,=,a,k,*,a,i,+,a,j,，这里,a,k,、,a,i,、,a,j,分别是,k,、,i,、,j,模,n,，,或者,a(k),ij,=(k*,i+j,),mod(n,),。,然后把,0,用,n,替换，就是拉丁方，且共有,(n-1),个拉丁方，它们,两两互相正交,2011.11.09,13,怎样构造正交拉丁方？,构造阶乘是素数的正交拉丁方,例子：求,5,阶的正交拉丁方,M(5),的同余加法和乘法,第一个拉丁方，即,k=1,时：,a(1)=(i+j)mod(5),2011.11.09,14,怎样构造正交拉丁方？,构造阶乘是素数的正交拉丁方,例子：求,5,阶的正交拉丁方,第一个拉丁方，即,k=2,时：,a(1)=(2*i+j)mod(5),对应的拉丁方阵就是：,2011.11.09,15,域的概念,群的定义：,设集合,G=,a,b,c,上有二元运算“”，并满足如下四个条件：,(1),封闭性：对任意,a,bG,，恒有,abG,(2),结合律：对任意,a,b,cG,，恒有,(,ab)c,=,a(bc,),(3),单位元：存在,eG,，使得对任意,aG,，恒有,ae,=,ea,=a,(4),逆元素：对任意,aG,，恒有,bG,使得,ab,=,ba,=e=,单位元,则称,G,在运算之下是一个群，简称,G,是群。,当一个群的元素是有限的，则称其为有限群。,交换群的定义：,如果集合,G,在运算之下是一个群，且进一步满足下面条件：,(5),交换律：对任意,a,bG,，恒有,ab,=,ba,则称,G,在运算之下是一个交换群（,Abel Group,），简称,G,是交换群。,域的定义：,设集合,F,至少含有二个元素，在,F,上有二种运算“”和“,”,，且满足下面条件：,(1)F,在“”下是交换群，其单位元记为“,0”,；,(2)F0,在“,”,下是交换群，其单位元记为“,1”,；,(3),分配律：对任意,a,b,cG,，恒有,(a,b)c,=(,ac,),(,bc,),；,则称代数系统,为域，简称,F,为域。,同样，当一个域的元素是有限的，则称其为有限域。,2011.11.09,16,域的概念,群的例子：置换群,集合,P,是,n,的全排列，它在下述运算下是交换群：,若,p,qP,，,p,在第,i,个位置的值是,pi,，而,q,在第,i,个位置的值是,qi,，,p,和,q,在运算的结果是,r,（即,r=,pq,），则,rpi,=,qpi,。,同余类：,两个整数,a,和,b,，若它们除以整数,m,所得的余数相等，则称,a,和,b,对于模,m,同余，,记为,ab(mod,m),，称为,a,同余于,b,模,m,。,集合,0,1,m-1,称为模,m,的同余类，记为,mod(m,),。,同余加法：在集合,mod(m,),中定义“”如下：,若,a,b,cmod(m,),，且,c(a+b)(mod,m),，则,a,b=c,其中“,+”,代表正常的加法，而“”代表同余加法。,同余乘法,：在集合,mod(m,),中定义“,”,如下：,若,a,b,cmod(m,),，且,c(a,*,b)(mod,m),，则,ab,=c,其中“*,”,代表正常的乘法，而“,”,代表同余乘法。,群的例子：同余类,同余类是在同余加法下的交换群，其单位元是,0,。,2011.11.09,17,域的概念,域的例子：素数同余类,设,p,是素数，则由上面知：,mod(p,)=0,1,p-1,是同余加法下的交换群，其单,位是,0,。如果我们能证明集合,mod(p)0=1,p-1,是同余乘法下的交换群，,则集合,0,1,p-1,就是域，且是,p,个元素的域。,我们只需要证明：,1,、封闭性：若,a,bmod(p)0,，则恒有,abmod(p)0,；,2,、单位元：,mod(p)0,在同余乘法下的单位元是,1,；,若,c=,ab,，则显然,cmod(p,),，且存在整数,n,使得：,a*b=n*p+c,因为,p,是素数，及,a,和,b,都小于,p,，所以,c0,，即,cmod(p)0,，封闭性得证。,由于,p,和,a,的最大公因数是,1,，所以根据数论定理（或用辗转相除法）知，存在,唯一的整数,b,和,c,使得：,a*b=c*p+1,或,a*b1(mod p),用同余乘法表示就是,ab,=1,，或,b,是,a,的逆元素。证毕。,素数,p,的同余类在同余加法,和同余乘法下的域用,GF(p,),表示，称为,p,阶,Galois,域。,右边是,p=5,时的同余加法表,和同余乘法表：,2011.11.09,18,Galois,域,GF(p,),整系数多项式：,大写字母,Z,表示所有整数的集合：,Z=01,2,3,-1,-2,-3,。,系数在,Z,中的一元多项式，称为整系数多项式。,用,Zx,表示所有整系数多项式的集合，显然我们有：,和项式：若,p(x),q(x)Zx,，则,(,p(x)+q(x)Zx,称其为和项式。,差项式：若,p(x),q(x)Zx,，则,(,p(x)-q(x)Zx,称其为差项式。,积项式：若,p(x),q(x)Zx,，则,(,p(x,)*,q(x)Zx,称其为积项式。,商项式：若,p(x),q(x),t(x)Zx,，且使得,p(x,)*,q(x,)=,t(x,),，则称,p(x,),是,t(x,),除以,q(x,),之商，记为：,p(x,)=,t(x,)/,q(x,),；,余项式：若,p(x),q(x),r(x),s(x)Zx,，,r(x,),的次数低于,q(x,),，且下式成立：,p(x,)=,s(x,)*,q(x,)+,r(x,),则称,r(x,),是,p(x,),除以,q(x,),的余，记为：,p(x)r(x)(mod,q(x,),GFp,x,用,GFp,x,表示系数在域,GF(p,),（其中,p,是素数）中的一元多项式的集合。,显然,GFp,x,是,Zx,的一个子集，进一步地，上面所述的和、差、积、商、余,的概念仍然成立。,不可约：若,p(x)GFp,x,不能用在,GFp,x,中的至少为一次的二个次数低,于它的积来表示，则称其为不可约的。它类似素数。,2011.11.09,19,Galois,域,GF(p,),若,p(x)GFp,x,是可约的，即有次方,0,的二个多项式,s(x),t(x)GFp,x,，使得：,p(x,)=,s(x,)*,t(x,),则称,s(x,),和,t(x,),是,p(x,),的因子。,公因子：若,p(x),q(x)GFp,x,，且有相同的因子，则称此因子是公因子。,互素的：若,p(x),q(x)GFp,x,无公因子，则称它们是互素的。,引理,5-7,若,p(x),q(x)GFp,x,是互素的，则存在,a(x),b(x)GFp,x,，使得：,p(x,)*,a(x,)=,q(x,)*,b(x,)+1,引理,5-8,若,p(x),q(x)GFp,x,，且,p(x,),的次方大于,q(x,),的次方，则存在二个多,项式,r(x),s(x)GFp,x,，使得下式成立,p(x,)=,s(x,)*,q(x,)+,r(x,),其中,r(x,),的次方小于。,同余类：,设,p(x),q(x),r(x),m(x)GFp,x,，且,r(x,),的次方小于,m(x,),的次方。若下述成立：,p(x)r(x)(mod,m(x,),，,q(x)r(x)(mod,m(x,),则称,p(x,),和,q(x,),是关于,m(x,),的同余类，记为,p(x)q(x)(mod,m(x,),。,域,GF(p,),设,m(x)GFp,x,是不可约的,n,次多项式，,GFp,x,可化为关于,m(x,),的一些同余,类，记为,GF(p,),，它是,GFp,x,中所有次方小于,n,的多项式的集合，其元素个数,个数是,p,，它和,n,位,p,进制数是一一对应。,2011.11.09,20,Galois,域,GF(p,),例子：,p=2,n=2,GFp,x,=,0,1,x,1+x,x,1+x,x+x,1+x+x,x,。,直接计算可以验证多项式,m(x,),=,1+x+x,是二次不可约的。,而,GFp,x,关于,m(x,),的同余类为,GF(,2,)=,0,1,x,1+x,，在其上的同余加法和,同余乘法如下：,2011.11.09,21,Galois,域,GF(p,),例子：,GF(,2,)=,0,1,x,1+x,关于,m(x,),=,1+x+x,的同余加法和乘法,把,x,用,2,替换，,1+x,用,3,替换，就得：,用前面的公式,a(k),ij,=k*,i+j,对,k=1,2,3,进行计算可得：,把,0,用,4,替换，就得到,3,个,4,阶的正交拉丁方：,2011.11.09,22,Galois,域,GF(p,),定理,5-2,若,u,是,GFp,m(x,),的非零元素，则：,pow(u,k)1,，其中,k=p-1,这表明非零元素的逆元素总存在。,定理,5-3,若,GFp,m(x,)=a,0,a,1,a,2,a,k,，其中,a,0,=0,k=p-1,，则有：,(x-a,0,)(x-a,1,)(x-a,2,)(,x-a,k,)=,x(pow(x,k,)1),这是多项式根与系数的关系的一种表达式。,正交拉丁方的构造,定理,5-4,设,m=p 2,（且,p,是素数及,n0,）。则存在,(m-1),个互相正交的拉丁方。,证明的过程就是就是构造的过程。设,GFp,m(x,)=a0,a1,a2,am,，其中,a0=0,m=p,。构造,(m-1),个,mxm,矩阵,A1,A2,如下：,第,k,个矩阵,Ak,=(,Ak(i,j,),，,k=1,m-1,，在,(,i,j,),处的元素是,Ak(i,j,)=,ak,*,ai,+,aj,i=0,1,m-1,j=0,1,m-1,再用同余加法和同余乘法就可验证。,定理,5-5,设,n1,的素数幂（因子）分解式是,n=pow(p1,a1)pow(p2,a2),pow(pk,ak,),若,m=min(pow(p1,a1),pow(pk,ak)-1,则有,r,个,n,阶的正交拉丁方。,从,定理,5-4,可知对于,n=3,4,5,都有,(n-1),个正交拉丁方。但当,n=6,时，我们不能从上,面定理中判断是否有正交拉丁方。,2011.11.09,23,正交拉丁方的构造,欧拉猜想：不存在,6,阶的正交拉丁方。直到,1900,年才获得证明。,定理,5-6,设,A1,A2,Ak,是,n,阶正交拉丁方，,B1,B2,Bk,是,m,阶正交拉丁方。,则按下述方法构造的,k,个,nxm,阶矩阵也是正交拉丁方：,Cr=(,Cr(i,j,),r=1,k,，在位置,(,i,j,),的值是,Cr(i,j,)=(Ar(s,t)-1)*n+(Br(u,v)-1)*m+1,r=1,k,其中角标,(,i,j,),和,(,s,t),(u,v,),之间的关系是：,i=(s-1)*m+u,j=(t-1)*m+v,例子：,2011.11.09,24,正交拉丁方的应用举例,前面我们讨论了四种品牌的轮胎的测试问题，用四辆汽车进行测试，从而引进,了四节拉丁方：,若同时考察四种不同的刹车车闸对轮胎的磨损，则需满足下面测试安排：,每种牌子的轮胎在每辆汽车出现一次,轮胎在四个不同的位置上各出现一次,不同牌子的轮胎和车闸恰好配合一次,四种车闸在四辆车的四个不同位置分别出现一次。,下面二个拉丁方，第一个是轮胎的测试安排，第二个是车闸的测试安排：,2011.11.09,25,正交拉丁方的应用,下面的方阵是车轮与车闸的配合测试：,这个方阵是正交的，所有没有重复的一对数出现，即每种轮胎和每种车闸都恰,好配合一次。,假定有四种感冒药、四种退烧药和四种止咳药，试验它们的配合效果，找四位,病人，在四天内进行试验。如果只考虑一种感冒药的试验，可用四阶拉丁方：,其中,A,B,C,D,是病人代号，而,I,II,III,IV,是日期。如果考虑二种药的配合，则需,要一对四阶的正交拉丁方，而三种药都考虑的话，则需要三个四阶正交的拉丁,方。,2011.11.09,26,均衡不完全的区间设计,基本概念,刚才我们讨论了四种品牌的轮胎，用四种汽车进行测试，每辆汽车上各种轮胎,一个，每辆汽车的被测试的轮胎称为一个区组。如果参加测试的轮胎有五个品,牌，但是汽车（一个区组）只有四个轮胎，每次只能测试四个轮胎，这样的测,试称为不完全的区组设计。我们可以用五辆汽车对五种轮胎按下面方式测试：,每一区组只包含四种轮胎，所以是不完全的，每种品牌都作了四次试验。,(,b,v,r,k,)-,设计,设,X=x,1,x,2,x,v,是试验对象的集合，它包含,v,个元素。,所谓均衡不完全的区组，是指由,X,中的子集构成区组的集合。,b,为区组的个数，,即为,B,1,B,2,B,b,。每组包含,X,的,k,个元素，且满足下面条件：,(1)X,中的每一个元素在,b,组中正好出现,r,次；,(2),任意一对属于,X,的元素在,b,组中正好同时出现,次；,(3)k v,；,满足上面条件的,BIBD(Balanced,Imcomplete,Block Design),记为,(,b,v,r,k,)-,设,计。,2011.11.09,27,均衡不完全的区间设计,例子：,X=x,1,x,2,x,7,，分组如下：,B,1,=x,1,x,2,x,4,；,B,2,=x,2,x,3,x,5,；,B,3,=x,3,x,4,x,6,；,B,4,=x,4,x,5,x,7,；,B,5,=x,5,x,6,x,1,；,B,6,=x,6,x,7,x,2,；,B,7,=x,7,x,1,x,3,;,它是,7,7,3,3,1-,设计。,为了讨论方便且不引起混乱，有时把,x,i,简写为,i,，如上例可写为：,B,1,:1 2 4,；,B,2,:2 3 5,；,B,3,:3 4 6,；,B,4,:4 5 7;,B,5,:5 6 1,；,B,6,:6 7 2,；,B,7,:7 1 3,；,定理,5-8,(,b,v,r,k,)-,设计满足：,bk,=,vr,，,r(k-1)=(v-1),证明：,(1),每组,k,个元素，共,b,组，,bk,是元素出现的总次数；另外，集合,X,中的,v,个元素，每个在,b,组中都出现,r,次，故,vr,也是元素出现的总次数，,所以它们相等：,bk,=,vr,。,(2),集合,X,中某个元素,x,出现在,r,个组中，把,x,从这,r,个组中除去，则还剩下,r(k-1),个元素；又,x,与其他,(v-1),个元素成对地出现在这,r,个组中，而且,每对出现,次，故其它,(v-1),个元素出现在这,r,个组中的次数就是,(v-1),，所以我们有：,r(k-1)=(v-1),。,2011.11.09,28,均衡不完全的区间设计,区组矩阵,v,个元素出现在,b,个组中，我们可以用,0-1,矩阵来描述，即,A=,A(i,j,),i1,b,j1,b,矩阵在,(,i,j,),的位置的取值是：,A(i,j,)=1,如果第,i,个元素在第,j,个组里,否则：,A(i,j,)=0,对于刚才的例子我们有：,定理,5-8,对于,(,b,v,r,k,)-,设计，下列等式成立：,AA =(r),I,+,J,其中,I,是,v,v,的单位矩阵，,J,是所有元素均为,1,的,v,v,矩阵。,证明：矩阵,AA,在位置,(,i,j,),值就是,A,的第,i,行与第,j,行之积。按照矩阵,A,的定义就是,i,号元素和,j,号元素在这二组中同时出现的次数。,2011.11.09,29,均衡不完全的区间设计,当,i,j,时，是,i,号元素在,b,组中出现的次数，也就是,r,次；,当,ij,时，是,i,号元素和,j,号元素同时在,b,组中出现的次数，也就是,次；,总结起来就是：,=(r,),I,+,J,证毕,引理,5-9,det(AA,)=(r+(v-1)pow(r-v,v-1)0,。,对其使用消元法，可以很容易证明上面等式。,定理,5-10,对于,(,b,v,r,k,)-,设计，恒有,bv,。,证明：用反证法，若不然，即,bv,，矩阵,A,的行多于列，增加,(,v-b,),列到,A,里，,且新增元素全取值,0,，记新矩阵为,B,。因为,A,中二行的内积和,B,一样，,所以：,det(AA,)=,det(BB,),。,因为,B,的新列都是,0,，故上式右边为,0,，但按,引理,5-9,上式左边不是,0,。,这个矛盾反证了本定理。,2011.11.09,30,均衡不完全的区间设计,对称的,BIBD,：,当,b=v,时的,BIBD,称为对称,BIBD,。因,bk,=,vr,，故有,k=r,。,对称的,BIBD,记为,(,v,k,)-,设计。,定理,5-11,对称的,BIBD,的任意二组都正好有,个共同元素。,区组设计的构成方法,定理,5-12,若,B,1,B,2,B,v,是集合,X=x,1,x,2,x,v,的对称,BIBD,，则,(v-1),个区组,B,2,B,1,B,3,B,1,B,v,B,1,构成一个关于集合,XB,1,的,BIBD,。,证明：显然若,x,属于某个,B,i,B,1,，则它也属于,XB,1,。同时，若,x,属于,XB,1,，则,它仍然出现在,k,组中，,XB,1,中的每对元素仍然同时出现,次。最后，,由前一个定理可知，,B,2,B,v,中每个区组与,B,1,有,个元素相同，这就,证明了,B,2,B,1,B,v,B,1,组成,(v-1),(v-k),k,(k-),)-,设计。,2011.11.09,31,区组设计的构成方法,定理,5-13,若,B,1,B,2,B,v,是集合,X=x,1,x,2,x,v,的对称,BIBD,，则,(v-1),个区组,B,2,B,1,B,3,B,1,B,v,B,1,构成一个关于集合,XB,1,的,BIBD,。,证明：显然若,x,属于某个,B,i,B,1,，则它也属于,B,1,，所以,x,在,B,2,B,3,B,v,中的（,k-1,）组出现，即,x,在,B,2,B,1,B,3,B,1,B,v,B,1,中的（,k-1,）组出现,B,1,中的任意一对元素，在这（,v-1,）个组中同时出现（,-1,）次。,同时，每个组,BiB,1,中有,个元素相同，这就证明了,B,2,B,1,B,3,B,1,B,v,B,1,组成,(v-1),k,k-1,-1),的,BIBD,。,从结论中，可以看到,必须大于,1,。,例子：,b=v=15,r=k=7,=3,B,1,：,1,2,3,4,5,6,7,B,2,：,1,2,3,8,9,10,11B,3,：,1,2,3,12,13,14,15,B,4,：,1,4,5,8,9,12,13,B,5,：,1,4,5,10,11,14,15B,6,：,1,6,7,8,9,14,15,B,7,：,1,6,7,10,11,12,13,B,8,：,2,4,6,8,10,12,14B,9,：,2,4,7,8,11,13,15,B,10,：,2,5,6,9,11,12,15,B,11,：,2,5,7,9,10,13,14B,12,：,3,4,6,9,11,13,14,B,13,：,3,4,7,9,10,12,15,B,14,：,3,5,6,8,10,13,15B,15,：,3,5,7,8,11,12,14,2011.11.09,32,区组设计的构成方法,前面的（,15,7,3,）对称,BIBD,，其区组矩阵为：,2011.11.09,33,区组设计的构成方法,这个矩阵的下面部分就是,B,2,B,1,B,15,B,1,：,2011.11.09,34,区组设计的构成方法,这个矩阵的上面部分就是,B,2,B,1,B,15,B,1,：,2011.11.09,35,Steiner,三元系,k=3,的区组设计称为三元系，（,b,v,r,3,l,)-,设计存在的必要条件是：,3b=,rv,和,2r=,l,(v-1),bk,=,rv,r(k-1)=,l,(v-1),或改写为,r=,l,(v-1)/2,和,b=rv/3=,l,v(v-1)/6,。,因为,r,和,b,都是整数，所以,l,(v-1),是偶数，,l,v(v-1),是,6,的倍数，即,l,(v-1)0 mod(2),和,l,v(v-1),0 mod(6),定义：,l,=1,的,三元系称为斯梯纳（,Steiner,）三元系。,定理（科克曼,Kirkman,）：,v,个元素的斯梯纳三元系的必要条件是：,v=6n+1,或,v=6n+3,证明：从前面式子，当,l,=1,得,v,必须满足：,(v-1)0 mod(2),和,v(v-1),0 mod(6),(5.9-1),即,v,是奇数，故,v,能用下面式子表达：,v=6n+1,或,v=6n+3,或,v=6n+5,在前面二种情况下，,v,(v-1),都是,6,的倍数，所以,v,满足,(5.9-1),。,在第三种情况下：,v,(v-1)=6(6n,+9n+3)+2,2 mod(6),，,这与,v,必须满足,上面的式子,(5.9-1),相矛盾。,2011.11.09,36,Steiner,三元系,定理：设,S,1,是关于,X=x,1,x,m,的斯梯纳三元系，,S,2,是关于,Y=y,1,y,n,的斯梯纳,三元系，则存在一个关于,m,n,个元素的三元系：,Z=,z,ij,，,=x,i,y,j,，,i=1,m,j=1,n,证明：我们构造区组,S,，其一组,(,z,ir,z,js,z,kt,),是如下之一：,(1)(,z,ir,z,is,z,it,),其中,i=1,.,m,r=1,.,n,s=1,.,n,t=1,.,n,(2)(,z,ir,z,jr,z,kr,),其中,i=1,.,m,j=1,.,m,k=1,.,m,r=1,.,n,(3)(,z,ir,z,js,z,kt,),其中,i=1,.,m,j=1,.,m,k=1,.,m,且,i,j,k,中至少二个不同,r=1,.,n s=1,.,n,t=1,.,n,且,r,s,t,中至少二个不同,且,(x,i,x,j,x,k,)S,1,，,(y,r,y,s,y,t,)S,2,。,下面我们只证明任意一对元素,z,ir,z,js,都只在上面中的一组中出现。用反证法，即,假设有,z,kt,z,lu,使得,(,z,ir,z,js,z,kt,),和,(,z,ir,z,js,z,lu,),都在,S,中，从而引出矛盾。,1.,若：,i,j,k,l,，则,(y,r,y,s,y,t,),和,(y,r,y,s,y,u,),都在,S,2,中，与,S,2,是斯梯纳三元系矛盾；,2.,若：,i,j,kl,，则,(y,r,y,s,y,t,),和,(y,r,y,s,y,u,),都在,S,2,中，与,S,2,是斯梯纳三元系矛盾；,、,如此可将所有情况排除，最后证明结果。,2011.11.09,37,科克曼（,Kirkman,）女生问题,这是组合数学的古典问题：,一个班有,15,个女生，每天排队出来散步；,15,个人分成,5,行，每行,3,人；,要求在一周（,7,天）里，每个女生和其他女生在一组（一行）里，且仅一次；,分析：,1,、每组（每行）有,3,人：是三元系，即,k=3,；,2,、每天有,5,组（,5,行），一周（,7,天）共组成,57=35,个三元组，即,b=35,；,3,、每人和其他人在一组仅仅一次：斯梯纳三元系，即,l,=1,；,4,、每人在每天出现一次，一周共出现,7,次，即,r=7,；,5,、共有,15,个女生，即,v=15,；,问题就是求（,35,15,7,3,1,）的区间设计，或斯梯纳三元系。,第五章结束,2011.11.09,38,