（应用数学专业论文）2×5格子区组设计的存在性.pdf

2 5 格子区组设计的存在性 摘要 我们用凰表示个顶点个数为”的完全图，用耳琏表示两个完全 图琢与的卡氏积图，其中的两个不同的点似，t ，) 与( ，t ，) 相邻当且仅当 或者= 或者口= t ，一个r c 格子区组设计( g r i d - b l o c kd e s i g n ) ，简记为 ( 弘r xc ，1 ) 一g b d 是一个二元组( 墨棚，其中x 为凰的顶点集，为凰的一 簇同构于墨x 疋的子图，叫做r c 格子区组，且4 中子图的边集形成凰 边集的一个划分h w a n g 等定义了这一概念并阐述了rxc 格子区组设计在 基因库筛选中的应用自此以来，rxc 格子区组的存在性问题吸引了诸多 学者的兴趣( ，2 2 ，1 ) - g b d 的存在性可由四圈系( 4 - c y c l es y s t e m ) 知道j e c a r t e r ，h l f u ，y m u t o h 等人解决了( r c ) ( 2 ，3 ) ，( 2 ，4 ) ，( 3 ，3 ) ) 时r xc 格子区组设计的存在性问题对于大参数的r ，c ，由于”cc 格子区组设 计结构复杂，构造困难，目前尚未见到有文献报道本文主要关注r = 2 ， c = 5 时( ”，r c 1 ) g b d 的存在性，证明此时r c 格子区组设计存在的必要 条件亦是充分的即( 口，2x5 ，1 ) - o b d 存在，当且仅当t ，；1 ( r o o d2 5 ) 关键词t 完全图瑶，积图玛xk o ，rx 岛1 ) 一g b d ，d n a 库筛选，存 在性 作者：李阳 导师：殷剑兴( 教授) t h e d s 皤c eo f2 5g r i d - b l o c kd e s i g n 英文摘要 t h ee x i s t e n c eo f2 5g r i d - b l o c kd e s i g n a b s t r a c t w eu s et h en o t a t i o n 虬t od e n o t et h ec o m p l e t eg r a p ho f 口v e r t i c e t h en o t a t i o n k txx e s t a n d sf o rt h ec a r t e r s i a np r o d u c to fk ra n dk ti nw h i c ht w od i s t i n c tv e r t i c e s ，口) a n d ( t ，t ，) a r e j t 匠n e d b y e x a c t l y o n e e d g e i f a n d o n l y i f u = n 7 0 r t ，= t ，a n r c g r i d - b l o c kd e s i g nd e n o t e db y ，r c 1 ) 一g b di s8p a i r 僻，棚，w h e r ex i st h ev e r t e x s e to fk - ，ai sac o n e c t i o no fs u b g r a p h eo fk 口，e a c hb e m gi s o m o r p h i ct ok rxk ca n d c a l l e dr cg r i d - b l o c k , w h i c hf o r map a r t i t i o no ft h ee d g es e to f 虬t h en o t i o no f r cg r i d - b l o c kd e s i g nw a si n t r o d u c e db yh w a n ga s s o c i a t e dw i t hi t sa p p l i c a t i o ni nt h e d n a l i b r a r ys c r e e a i n g s c i n e t h e n t h e p r o b l e m o f t h e e x i s t c e o f t h e r c g r i d - b l o c k d e s i g nh a sa t t r a c t e dc o n s i d e r a b l ea t t e n t i o n t h e 凼= t e n o fa 和，2 2 ，1 ) - g b di s k n o w ni nt e r m so fa4 - c y c l es y s t e m j e c a r t e r ，h l 地y m u t o ha n do t h e r s r e s o l v et h ep r o b l e m so ft h ee g 妇c eo fr cf i d - b l o c kd e s i g n s ，w h e 弛r ，ca r ei n ( 2 ，3 ) 。( 2 ，4 ) ，( 3 ，3 ) ) f o rl a r g ev a l u e so f ta n dc 棚t h es t m c t u r e sa l - ec o m p l e x , i ti sa d i m c u l tt a s kt oc o n s t r u c tt h ec o r r e s p o n d i n gr cg r i d - b l o c kd e s i g n s a n dt h e r ea r en o l i t e r a t u r e sr e p o r t e d i nt h i sp a p e r ，w ep a ya t t e n t i o nt ot h ec a s ef o rr = 2a n do = 5 ， a n dp r o v et h a tt h en e c e s s a r yc o n d i t i o n so ft h ee 。d s t e i l c eo ft h i sr cg r i d - b l o c kd e s i g n a r ea l s os u m c i e n t n a m e l y a 扣，2 5 ，1 ) 一g b de x i s t s ，i f a n do n l y i f 口i 1 ( r o o d2 5 ) k e y w o r d s ：t h ec o m p l e t eg r a p h 凰，c a r t e r s i a np r o d u c tg r a p h 蟛致， rxc ti ) - g b d ，d n al i b r a r ys c r e e n i n g ，d s t e n c e i i w r i t t e nb yl iy a n g s u p e r v i s e db yp r o f y i nj i a n x i n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含其他个 人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学或其它教 育机构的学位证书而使用过的材料。对本文的研究作出重要贡献的个人和 集体，均已在文中以明确方式标明本人承担本声明的法律责任。 研究生签名：纽日期：翟啦习动目 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合 作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文 档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布 ( 包括刊登) 授权苏州大学学位办办理。 研究生签名：细日期：翟1 2 墨堡毋伽日 导师签名碜日期；渺日 2 5 格子区组设计的存在性一 引言 1 1 定义和例子 第一章引言 我们用虬表示个有t ，个顶点的完全图，用记号坼疋表示两个完 全图厨与圪的加氏积，其中的任意两个不同的顶点扣，口) 和，t ，) 相邻当 且仅当“= 或者甜= t ，这里，涉及到的图论术语可见文献【1 】1 等 给定正整数1 0 ，r ，c ，设x = y ( 甄) 为完全图凰的顶点集，4 为 的族边不交的子图，其中每个子图与图坼凰同构，称为是 cc 格子区 组如果的边形成了凰边集曰( 凰) 的个划分，我们定义二元组( 五棚 为个rxc 格子区组设计( g r i d - b l o c kd e s i g n ) ，记作( ，r c 1 ) - g b d 由定义可见，rxc 格子区组设计本质上就是个完全图关于顶点分别 为r 和c 的两个完全图加氏积的分解( 定义可参见文献【2 3 】等) 下面给出个r c 格子区组设计的简单的倒子 设x = z 如，a 为由图一所示的5 个格子区组组成，则c 墨棚为一个 ( 1 0 ，2 3 ，1 ) - g b d 1 2 研究背景 r c 格子设计是h l h ，f k h w a n g 等人在文献( 4 】中引入的而 f k h 咖g 【5 】也提出了它在基因库筛选中的应用自此以来，r c 格子区 012 2 3 4 4 5 6 6 7 8 8 90 田田田田田 3585 7 0 7 9 291413 6 圈一t 个( ，2 5 ，1 ) - g b d 2 x 5 格子区粗设计的存在性一i l 言 组设计的存在性问题吸引了诸多学者的兴趣有关r c 格子区组设计与基 因库筛选的联系，进步的细节可以参看文献【4 ，5 ，6 ，7 ，8 ，9 】等 基因是即d n a 是由核酸单体聚合两成的聚合体，其的物质特性在于聚 合成核酸的核苷酸中的碱基，包括腺嘌呤( a ) ，鸟嘌呤( g ) ，胞嘧啶( c ) ， 胸腺嘧啶( t ) 基于某种性态，基因有着阴阳性之分，基因库筛选的目的在于 确定所给的基因样本中的所有阳性基因 时间和经济上的考虑，需要对这些基因进行分组测试每一组为个培 养皿( p 砝) 如果一个培养皿给出了一个阴性结果，则包含在该培养皿中的 所有基因都将是阴性的，从而可以节约实验的次数另一方面，如果一培养 皿呈阳性，则需要转入第二阶段对基因逐个进行测试，这种筛选的方法正是 一种非常流行的群试( g r o u po 喊i n g ) 方法，称为是二步法 在实际的检溯过程中，是有一些称为微量海定板的工具，基因棒本们将 成格子的形式被排在滴定板的小坑中接受检澍而其中所排阵中的行或列 自然地作为个培养皿，它们将在一次实验中同时被检测 在应用r c 格子区组设计于这种筛选时，r c 格子区组等同为顶点 ( 即基因) 的r c 阵，其中的坼或圮相当于行或列，一次实验中每个基因 被检测了两次 如图二中所示，如果一次实验中只包含一个阳性基因，或者更一般地， 只有个呈阳性的行或列，则可以判别出阳性的基因在阳性的行和列的交 000 、：阳性的培养皿 ：个阳性基因 图- s 群试的第一阶段 2 ，：阳性的培养皿 o ：可能的阳性基因 2 5 格子区组设计的存在性 一引言 点处，而不需要逐个去检验但是，旦实验中包含多于一个的阳性的行和 列，则不能判定呈阳性的行和列交点位置上的基因是否呈阳性 时间和经济的限制，我们要尽可能在第一阶段获得尽可能多的信息，因 此可以考虑允许对每个基因样本进行多于两次的检测这种情形下，经过分 析要求一个所谓的唯一线形条件( u n i q u ec o l l i n e a r i t yc o n d i t i o n ) 即要求两个不 同的基因样本在同行或列中至多出现一次b a r i l l o t ，l a c r o i x 及c o h e nf l o 提出了这一条件，b e r g e r ，m a n d e l l 及s u b r a h m a n y a 【1 1 】模拟并从理论上给予 了证明另方面，通过对要实验数目的期望的考察，也有个结论是要求 在第一阶段的实验中每个基因样本重复出现的次数要尽可能相同，即要满 足相同重复实验次数( t h ee q u a lr e p l i c a t i o nn u m b e ro ft e s t 8 ) 的条件 很显然，r c 格子区组设计满足唯一线形条件和相同重复数的要求，。 因此是有意义的 关于r c 格子区组设计本身的研究，实际上仍可向前追溯的，主要 是针对r c = 口时的特殊情形其中若r = c ，这种情况下被称为方格设计 a 础妇s q u a r ed e s i g n ) ，最早由y a t e 文献 1 2 】中提出，而r a g h a v a r a 1 3 在、，面 为奇素质数幂时给出了一些构作方法与之对应地，r c 时，称为是长格 设计洳捞娩r e c t a n g l ed e s i f f n ) ，h a r s h h a r g e r 1 4 对其做了相应的介绍 1 3 研究问题和结果 在应用rxc 格子区组设计进行基因库筛选，格子的大小总是要受到限 翩的，而点集通常又会很大一般地，假定r 扣或c 扣 给定个( 移，r x c , i ) - g b d ，由定义可知，每一点恰出现在扣一1 ) ( r + c 一2 ) 个r c 格子区组中，因此该设计包含”扣一1 ) i r c ( r c 一2 ) 个r c 格子区组， 由此导致似r c ，1 ) g b d 存在的必要条件： 引理1 3 1 【4 】若( 口，r c ，1 ) - g b d 存在，则有t 3 2 x5 格子区纽设计的存在性一引言 ( 1 ) ( r + c 一2 ) i ( 可一1 ) ； ( 2 ) r c ( r c 一2 ) 扣扣一1 ) 由文献可知当( r ，c ) e ( 2 ，2 ) ，( 2 ，3 ) ，( 2 ，4 ) ，( 3 ，3 ) ) 时r c 格子区组设计存在 的必要条件均已被证明也是充分的其中( ”，2 x 2 ) - g b d 的存在性可由四圈系 ( 细d e 町，s t i 哪) 【2 1 知道“2x2 ) - g b d 存在性的证明是由j e c a r t e r 1 5 在解 决将完全图虬分解成三次图问题时的给出的扣，2 x 3 ) - g b d 及扣，3 x 3 ) g b d 的存在性问题则分别是由h l f u 等人【4 】和y m u t o h 等人嘲解决的对于 大参数的r c ，由于r c 格子区组设计结构复杂，构造困难，目前尚未见到 有文献报道本文将对2 5 格子区组设计的存在性展开研氪由引理1 3 1 知，扣，2 5 x ) g b d 存在的必要条件为。 蛰毫1 2 5 ) 我们将证明此时的必要条件也是充分的，即本文得到以下结果t 定理1 , 3 2 设 为正整数 扣，2 5 ，1 ) - g b d 存在，当且仅当t ，兰1 ( m o d2 5 ) 4 2 5 格子区组设计的存在性 二构作方法 2 1 预备知识 二构作方法 为了建立本文的主要结果，我们需要一些设计理论中的术语和相关的结 果，本小节我们将对此做一些介绍我们以文献【2 】及【1 6 】作为的标准设计 理论的参考文献 设移为非负整数，k 为某些正整数的集合。一个阶数为移，指标为1 的 可分组设计( g r o u pd i v i s i a b l ed e s i g n ，记为g d d ) 是一个三元组，玩研，其 中： ( 1 ) x 为”元集，其中的元素称作为点( p o i n t ) ； ( 2 ) 9 为x 的划分，其中的子集称为是组( g r o u p ) ； ( 3 ) b 是x 中子集的类，其中的子集称为是区组( b l o c k ) ； ( 4 ) 对任意的区组b b 及任意的组g p ，有i b n g l 1 ； ( 5 ) x 中任意一对相异的点，恰同时出现在在艿中个区组中 如果对任意的区组b 8 ，有i b i k ，那么( 五g ，b ) 为个k - g d d 当k = h 时，我们将记号简为k - g d d 重集 i c i ：geg ) 叫作g d d 的组 型，记号聋皆是表示g d d 恰有坞个大小为t 的组，其中江1 ，8 文献中型为r 的k - g d d 通常称作成对平衡区组设计( p a i r w i s eb a l a n c e d b l o c kd e s i g n ) ，记为加，k1 ) - p b d 此时，由于组集9 等同于点集x ，为记 号上方便，我们从三元组瞵，g ，动中删去9 而简记为( 墨功一个扣，k ，1 ) - p b d 就是熟知的平衡不完全区组设计( b a b m c e di n c o m p l e t eb l o c kd e s i g n ) ，记为 ( 口，七，1 ) 一b i b d 型为铲韵k - g d d 被称为横截设计，用t d ( k ，幻来表示横截设计是设 计理论中一类重要的设计，它的存在性等价于k 一2 个t 阶互相正交的拉丁 5 2 5 格子区组设计的存在性二构作方法 方的存在性下文中，我们将多次运用以下已知( 例如，可见文献【2 】) 结果： 引理2 1 1 对于任意的素质数幂q ，t d ( q + 1 ，口) 存在 这里我们也列出一个对我们问题的非常有用的关于p b d s 的结果t 定理2 1 2 【1 7 1 设e = f 1 0 ，删u 2 2 ，2 4 1u 防，冽u 3 2 ，3 4 ，则对任意的正整数 射1 0 且移g e ，似 5 ，6 ，7 ，8 ，9 ) ，1 ) - p b d 存在 2 2f c 可分组格子区组设计 我们用虬，。，。表示一个顶点集为x = u 1 5 蛳墨的完全h 部图， 其中顶点类五含陇i ；啦个点，且五n 玛= 口( 1 i ) 任意两个顶 点z 和y 在。，。中相邻当且仅当z 与掣位予不同的顶点类中设分 = 墨，x 2 ， ，4 为蚝。的族子图，其中每个子图与图坼垃 同构，叫做rxc 格子区组若4 中子图的边集形成j 。，一。的边集的一 个划分，则我们将三元组( 墨玩棚叫做组型为t = n 。，砌，n 。) 的r c 可 分组格子区组设计( r cg r o u pd i v i s i a b l eg r i d - b l o c kd e s i g n ，简记为r c - g d d ) 这里组型t 为重集，类似于o d d ，我们将在下文中用指数形式表示它 由定义可见，型为1 - 的r c - g d d 等价于( t ，r c 1 ) - g b d 此时岔等同 于顶点集x 图三，个2 5 格子区组 6 2 5 格子区组设计的存在性二构作方法 行文的方便起见，我们以符号a = “l l ，d 1 2 ，一，d 1 。；a m ，a n ，口嬲；n r l ， a , 2 ，) 表示个r c 格子区组，其中q - ，嘞，d c 各点相邻，叼， 各点也相邻，这里i = 1 ，2 ，r ，i = 1 ，2 ，c ，但若i 1 赴且五杰，玛。j 1 与 a 蚰不相邻例如个2 x 5 - 格子区组a = ( 口1 1 ，d 1 2 ，a l s ，a 1 4 ，a 1 5 ；a 2 1 ，a - n ，吻，翰，a 2 5 ) 如图三所示 有关r c - g d d 的递归构作，我们可以从两个方面将设计理论中常用的 加权方法和w i l s o n 基本构作f 1 8 】加以变着：是以个g d d 为基础设计， 以，c - g d d 为输入设计；二是以个r c - g d d 为基础设计，以t d 8 为输 入设计特别地，我们有如下两个定理t 定理2 2 1 若存在个型为t = n t ，1 2 ，m ) 的k - g d d ，且对于任意的正 整数“k ，型为硝的r c - g d d 存在，则鎏【为m t = m n l ，m n 2 ，m n h 的，x c - g d d 存在 证明：可参见文献【4 】等 定理2 2 2 设为r ，c , t 整数，且r 己若型为t = 仇，n 2 ，锄) 的r x c - g d d 及t d ( c ，m ) 均存在，则型为m t = m n l ， 耽，m n h 的r x c - g d d 也存在 证明t 本定理的证明是通过对文献忉中定理1 9 做修改得到的 设( 墨譬，棚为一个型为t = n 1 ，t 1 2 ，锄 的rxc - g d d ，其中乒 置，为，甄 ，且阢i = f l ，t = 1 ，h 设是( v , w ，c ) 是点集v = 厶k 上，组为似) k ，j 厶 的个t d ( c , “t ) ，其中对任意正整数l ，标记五用来 表示集合 1 ，琅由中任意个区组a = ( d 1 1 ，毗，吼。；a 2 1 ，a n ，； ；a 1 ，锄，n - c ) 及c 中任意个区组c = t ( 1 ，霉1 ) ，( 2 ，z 2 ) ，( c ) ) 我们可 以构作出x k 上的个r c 格子区组a c = ( ( n 1 1 ，善1 ) ，( n 1 2 ，x 2 ) ，( o k ，硝； ( 口2 l ，勘) ，( o 船，勋) ，( 8 2 ( c 1 ) ，施) ，( d 勉，现) ；i “1 ，) ，( a r 2 ，珥+ 1 ) ，( n ”，缸，) ) 令y = xx 磊，绺 噩k ，x 2 乙，赫k ) ，拈 如，a c c 对于任意的( 毛u ) ，( f ，口) y ，若z ，f 在g 中不同的组中，显然 7 2 x5 格子区组设计的存在性 二构作方法 扛，让) ，( p ，t ，) 在且中不相邻若存在i ，j 使1 i j h ，且茹五，y e 局 则8 中有唯一的r c 格子区组使z ，f 在其中恰相邻，不妨设这一格子区 组为a = ( d 1 1 ，g 1 2 ，扛k ；d 牡，吻；，；虮，锄，此时，若z ，在 中的一个垃中相邻，即存在i ，矗杰i o 使茁= ，y = 对 任意正整数l ，若l = c ，规定i = l 。否则i = l c 由于( ! 鱼= ! ，u ) ， “+ j 2 一l ， ) 恰在上述的t d 中的个区组中同时出现，设这个r c 格子区 组为c ，则知即为日中唯一的个rxc 格子区组使扛，由，( 玑”) 在其中 相邻，同样对于霉= j ，寥= 8 泖，i 厶，五杰露的情形也有类似的 结论这样就证得( y , h ，功为一个型为 m n ，m n 2 ，册h ) 的r c - g d d 由于扣，k 1 ) - p b d 与型1 为r c - g d d 等同，作为定理2 2 1 的直接推 论，我们有t 定理2 2 3 若存在一个扣，k , 1 ) - p b d ，且对于任意的 k ，型为m - 的 r c - g d d 存在，则型为彬的r c - g d d 存在 借助于r c - g d d ，我们有如下简单且有效的递推方法，其证明可参见 文献【1 9 ，4 1 等事实上，这是特异积方法的一种，可见m u l l i n 等的早期文献， 如f 2 0 j 定理2 2 4若存在个型为t = n 1 ，1 2 ，) 的r c - g d d ，且对于任意 的 ，1s i h ，h + 1 ，r c ，1 ) 一g b d 均存在，则0 + 1 ，r xc 1 ) 一g b d 存在， 这里口= 啦 2 3 直接构作 本节中，我们将利用设计理论中b o s e 混差法【2 1 】的变着，构做若干小阶 数的r c 格子区组设计，它们是我们利用前面的递推方法的基础 8 2 x5 格子区组设计的存在性二枸作方法 像在文献中c 2 2 ，2 3 】描述的那样，个r c 格子区组设计可由某加法群 的子群生成我们用符号 表示磊的由z 生成的加法子群个2 x 5 格 子区组后若缀有( 托，m o d 。) 贝! l _ 表示将这个格子区组展开，产生了l 1 个 格子区组，并且它们是由该2x5 格子区组在模”的情况下循环地加入 中的元素得到的当卫= 1 时，( + z ，m o d t ) 被简写为( m o d ”) 需要指出的是，个2 5 格子区组( a l ，d 2 ，a s ，0 4 ，n 5 ；6 1 ，b ，6 3 ，b 4 ，嘲中的差 将被如下计算： 士( n 一q ) ，士( k b 9 ，士( o r k ) ：1 歹s 5 ，1 r 5 ) 下文的构作中我们采用了不同的自同构群 引理2 3 1t 为一正整数，若t 1 ，2 ，3 ，4 ) ，则( 2 乳+ 1 ，2 5 ，i ) - g b d 存在。 证明t 当t = 1 时，取z b 1 2 作为点集，构作的设计由以下2 5 格子区组 构成t ( ( o ，1 ) ，( o ，2 ) ，( i ，1 ) ，( 2 ，2 ) ，( 5 ，1 ) ；( 1 0 ，1 ) ，( 3 ，2 ) ，( 4 ，2 ) ，( 8 ，2 ) ，( 1 2 ，1 ) ) m o d ( 1 3 ，- - ) 当t 仫3 ，4 时，取2 k 蚪1 作为的点集，要构作的设计由以下2 x5 格 子区组构成， t2 5 格子区组 2 ： ( 0 ，1 ，3 ，7 ，1 7 ；2 6 ，1 3 ，1 8 ，3 7 ，4 6 )( m o d5 1 ) 3 ： ( 0 ，i ，3 ，7 ，1 8 ；1 0 ，3 1 ，2 3 ，5 0 ，5 5 ) ( m o d7 6 ) ( 0 ，9 ，2 3 ，3 5 ，5 1 ；4 7 ，3 8 ，6 1 ，1 3 ，7 3 )( “m o d7 6 ) ( 0 ，1 2 ，2 8 ，5 3 ，6 2 ；3 8 ，6 6 ，5 0 ，2 4 ，1 5 )( + 4m o d7 6 ) 4 ： ( o ，1 ，3 ，7 1 2 ；8 ，1 8 ，3 4 ，6 1 ，8 0 ) ( r o o d1 0 1 ) ( o ，1 3 , 3 6 , 5 1 ，7 3 ；3 0 ，4 8 ，9 7 ，7 2 , 1 6 ) ( r o o d1 0 1 ) 9 口 2 5 格子区组谖计的存在性 二构作方法 引理2 3 2t 为一正整数，若s 6 ，7 ，8 ，1 0 ，n ，则型为5 的2x5 - g d d 存 在 证明；当s 6 ，7 ，1 1 ) 时，我们以z 0 作为点集x ，以z k 中指数为5 的子 集 的加法陪集作为顶点类，所需的2 5 格子区组如下表所示t t2 5 格子区组 6 ( o ，1 ，2 ，5 ，1 0 ；1 1 ，2 2 ，9 ，1 9 ，2 6 ) ( + 2r o o d3 0 ) 7 ( o ，l ，2 ，3 ，4 ；5 ，1 1 ，1 7 ，2 3 ，卿( + 5r o o d3 5 ) ( 1 4 ，1 8 ，2 2 ，；l g ，8 ，3 2 ，2 1 ，1 0 )( + 5r o o d3 5 ) ( 7 ，1 6 ，2 4 ，2 5 ，3 3 ；1 2 ，3 1 ，9 ，1 5 ，2 8 )( + 5m o d3 5 ) 1 1 ( 0 ，1 ，3 ，8 ，1 8 ；6 ，2 0 ，3 3 ，2 9 ，4 9 )( m o d5 5 ) 当s = 8 时，我们以( 历u o o ) z 5 作为点集x ，以缸 x 磊，历u 为顶点类，所需的2 5 格子区组由以下初始2 5 格子区组保持无穷大点固 定，以第分量模7 展开得到 ( ( c o ，o ) ，( o ，1 ) ，( 1 ，2 ) ，( 2 ，3 ) ，( 6 ，4 ) ( 3 ，o ) ，( 4 ，1 ) ，( 0 ，2 ) ，( 5 ，3 ) ，( o 。，1 ) ) ( ( o o ，2 ) ，( o ，1 ) ，( 6 ，2 ) ( 3 ，3 ) ，( 2 ，4 ) ；( 6 ，o ) ，( 5 ，o ) ，( 1 ，2 ) ，( 4 ，2 ) ，( 3 ，4 ) ) ( ( o o ，3 ) ，( 0 ，1 ) ，( 4 2 ) ，( 6 ，3 ) ，( 1 ，4 ) ；( 0 ，o ) ，( 5 ，1 ) ，( 6 ，1 ) ，( 2 ，o ) ，( 3 ，4 ) ) ( ( o o ，4 ) ，( 0 ，1 ) ，( 2 ，2 ) ，( 5 ，3 ) ，( 3 ，4 ) ；( 5 ，o ) ，( 4 ，3 ) ，( 1 ，0 ) ，( 6 ，3 ) ，( o ，4 ) ) 当3 = 1 0 时，我们以z u o o o ，0 0 1 ，0 0 2 ，0 0 3 ，4 ) 作为点集x ，以 o ， o 。，o o ，3 ，。 及z 蛞中指数为9 的子集 的加法陪集作为顶点类，所 需的2 5 格子区组如下， ( ，0 ，1 ，4 ，3 8 ；4 2 ，2 3 ，2 9 ，4 4 ，9 ) ( r o o d4 5 ) 1 0 2 5 格子区组设计的存在性二构作方法 这里，对任意的z z 蚯， 如果z i i ( m o d5 ) 。 o o + 毒o o , 引理2 3 3 型为1 0 6 的2 5 - g d d 存在 证明；我们以z 南作为点集，以其1 0 阶子群 的加法陪集为顶点类， 所需2 5 区组如下： n ( o ，1 ，3 ，8 4 0 ；1 3 ，2 7 ，4 6 , 1 7 ，2 ) ( r o o d6 0 ) 口 引理2 3 4 型为5 1 3 2 0 1 的2 5 - g d d 存在 证明：我们以蜀骚u o ，i - 0 , i ，2 ，3 ，= o ，l ，2 ，3 ，4 ) 作为点集x ，以 蜘江 0 ，1 ，2 ，3 ，j = o ，i ，2 ，3 ，4 ) 及的5 阶子群 的加法陪集为顶点类，所 需的2 5 格子区组如下： ( o ，0 ，l ，3 ，9 ；7 ，2 , 5 ，1 1 ，5 3 ，1 ) ( m o d6 5 ) ( 0 0 2 ，i ，1 2 ，2 8 ，4 5 ；2 4 ，4 6 ，1 7 ，5 8 ，a ) ( r o o d6 5 ) 这里，对任意的z z 南， o o + $ = o o q ， 如果盘兰j ( m o d5 ) 弓l 理2 。3 5 对于8 = 5 或9 ，型为2 铲的2 5 g d d 存在 证明；对于该引理中的s ，我们以z 赢作为点集x 以其2 5 阶子群 的加法陪集为顶点类，要构作的设计的2 5 格子区组见下表t i i 2 5 格子区组设计的存在性二神作方法 t 2 x5 格子区组 5 ( 0 ，l ，3 ，7 ，1 9 ；8 ，5 5 ，6 4 ，1 0 1 ，4 2 )( m o d1 2 5 ) ( o ，l l ，4 4 ，7 3 ，8 7 ；4 2 ，1 1 0 , 8 3 ，6 ，s g ) ( m o d1 2 5 ) 9 ( 0 ，4 ，3 4 ，9 3 ，1 0 9 ；1 5 5 ，5 1 ，3 ，1 4 9 ，4 3 ) ( m o d2 2 5 ) ( 0 ，1 1 ，3 3 ，1 0 7 ，1 6 7 ；，4 8 ，6 2 ，1 4 8 ，2 1 6 ) ( r o o d2 2 5 ) ( 1 6 4 ，3 4 ，1 1 2 ，2 1 5 ，1 9 2 ；8 7 ，1 7 5 ，i i i ，0 ，1 4 9 ) ( m o d2 2 5 ) ( 2 0 9 ，6 6 ，2 0 6 ，1 1 2 ，1 6 7 ；9 9 ，1 1 9 ，1 0 4 ，s 7 , 1 0 6 ) ( m o d2 2 5 ) 口 2 5 格子区纽设计的存在性 三 主要结果的证研 三主要结果的证明 本节中，我们将给出定理1 3 2 的证明由引理1 3 i ，我们仅需考虑其 充分性下面我们将分步叙述 引理3 1 设f = f 1 2 ，2 0 u 陋，2 4 u 2 7 ，冽u 3 2 ，删，则对于任意的正整数t 5 且t g f ，型为2 5 t 的2 5 - g d d 存在 证明：当t = 5 ，9 时，型为2 5 t 的2 5 - g d d 已在引理2 3 5 中构作出 当t = 6 ，7 8 ，1 0 ，i i 时，由引理2 3 2 知型为5 t 的2 5 - g d d 存在再 由引理2 1 1 知t d ( 5 ，5 ) 存在因此可以在定理2 2 2 中取m = 5 ，r = 2 ，c = 5 ， 得到所要的型为2 5 t 的2 5 - g d d 当t a 5 ，6 ，7 , 8 ，9 ，1 0 ，1 1 时，由引理2 1 2 可知( t ， 5 ，6 ，7 ，8 ，9 ) ，1 ) p b d 存 在由定理2 2 3 及型为2 5 5 ，2 5 s ，2 5 v ，2 5 s ，2 5 9 的2 5 - g d d s 的存在性可知型 为2 5 ；i 的2 5 - g d d 存在口 引理3 2 设f = 【1 2 ，冽u 2 2 ，2 4 1 u 陟，2 9 1 u 【3 2 ，s 4 1 则对于任意的正整数t g f ， ( 2 5 t + 1 ，2 5 ，1 ) - g b d 存在 证明：当1 茎t 4 时，相应的( 2 5 t + 1 ，2 5 ，1 ) - g b d 已在引理2 3 1 中构做 出 当t 5 且tgf 时，由引理3 1 知型为2 5 t 的2x5 - g d d 存在由引理 2 2 4 及，2 5 ，1 ) - g b d 的存在性可知( 2 5 t + 1 ，2 5 ，1 ) g b d 存在 d 引理3 3 设t 为正整数，若t = 1 2 或1 7 ，则( 2 配+ 1 ，2 5 ，1 ) g b d 存在 证明，由引理2 3 3 知，当为t = 1 2 时，型为1 0 b 的2 5 - g d d 存在由引 理2 1 1 知t d ( s ，5 ) 存在在定理2 2 2 中取t t t , = 5 ，r = 2 ，c = 5 。可知型为 2 5 格子区组设计的存在性 三 主要结果的证明 5 0 6 的2 x 5 - g d d 存在然后利用定理2 2 4 及( 5 1 ，2 5 ，i ) - g b d 的存在性，知 ( 2 5 1 2 + l ，玛x 蚝，i ) g b d 存在 当t = 1 7 时的结论可类似得到，它是从引理2 3 4 中的型为5 1 3 2 0 l 的2 5 - g d d 出发，利用定理2 2 2 ( 其中取m = 5 ，r = 2 ，c = 5 ) 及定理2 2 4 得到 引理3 4 设t 为正整数，且t x s ，1 5 ，1 8 ，1 9 ，2 2 ，2 4 ，2 7 ，s 4 ，则( 2 5 t + 1 ，2 5 ，x ) - g b d 存在 证明：由 2 4 j 知，对于t e x s ，1 5 ，1 8 ，1 9 ，2 2 ，2 4 ，2 7 ，s 4 ，( 5 t + l ，6 ，1 ) - b i b d 存 在我们从个( 5 t + l ，6 ，1 ) 一b i b d 中删除掉一点，并以被截断的那些区组 为新的组就得到了个型为5 t 的6 - g d d 在定理2 2 1 中取仇= 5 ，并利用 引理2 3 2 中型为5 6 的2 5 - g d d 的存在性，知型为2 5 t 的2 5 - g d d 存在， 从而由定理2 2 4 及( 2 6 ，2 5 ，1 ) - g b d 的存在性可知( 2 5 t + 1 ，2 5 ，i ) - g b d 存 在d 引理3 5 设t 为正整数，若t = 1 4 或1 6 ，则( 2 5 t + 1 ，2 5 ，1 ) g b d 存在 证明：由引理2 1 1 知，t d ( 7 ，1 1 ) 及t d ( 8 ，1 1 ) 均存在 当t = 1 4 时，我们从一个t d ( 7 ，1 1 ) 中删除一个区组，得到一个型为 1 0 7 的 6 ，7 】- g d d 由引理2 3 2 知型为5 e 及5 7 的2 5 - g d d s 存在在定理 2 2 1 中取m = 5 就得到了一个型为5 0 7 的2 5 - g d d 然后由定理2 2 4 及 ( 5 1 ，2 5 ，1 ) - g b d 的存在性可知( 2 5 1 4 + l ，2 5 ，1 ) g b d 存在 当t = 1 6 时，我们从个t d ( 8 ，1 1 ) 中删除个区组，得到了个型为 1 0 8 的( 8 ，7 ) 一g d d 由引理2 3 2 知型为5 8 的飓k s - g d d 也存在用和t = 1 4 时同样的方法，可知( 2 5 1 6 + 1 ，2 x5 ，1 ) 一g b d 存在 引理3 6 设t 为正整数，若t 2 0 ，2 3 ，2 8 ，2 9 ，3 2 ，s s ，则( 2 5 t + 1 ，2 5 ，1 ) g b d 1 4 2x5 稿子区组设计的存在性 三 主要结果的证明 存在 证明：当t = 2 0 时，由引理2 1 1 知，t d ( 5 ，4 ) 存在由定理3 1 知，型为2 5 3 的2 x s g d d 存在利用定理2 2 1 ，知型为1 5 的2 5 - g d d 存在然后由 定理2 2 4 及( 1 0 1 ，2x5 ，1 ) - g b d 的存在性，可知( 2 5x2 0 + 1 ，2 5 ，1 ) - g b d 存 在 当t = 2 3 时，由引理2 1 1 知t d ( 1 l ，1 1 ) 存在从个t i ) ( 1 1 ，u ) 中删除 某一组中的个6 点，以该组中剩余的部分及过包含某被删除点的原区组截断 后的部分为新的组，可得到了一个型为1 0 “5 1 的- i x 0 ，x l 】- c d d 在定理2 2 1 中取m = 5 ，考虑到引理2 3 2 中型为5 l o 及5 “的2x5 - c d d s 的存在性， 得到了个型为5 0 1 1 2 5 x 的2 5 - g d d 再由定理2 2 ，4 及( 2 6 ，2 5 ，1 ) g b d ， ( 5 l ，2x5 ，1 ) - g b d 的存在性，可知( 2 5 t + l ，2 5 ，1 ) g b d 当t = 2 8 或2 9 时，设为e 正整数由引理3 1 知，型为2 铲及2 5 7 的 2x5 - c d d s 的存在由引理2 1 1 知，t d ( 6 ，5 ) 存在从个t d ( e ，5 ) 中的某 个组中删除5 一e 个点，得到个型为5 5 e 1 的 6 ，5 1 一g d d 利用这个g d d ，在 定理2 2 1 中取m = 2 5 ，得到个型为1 2 5 5 ( 2 5 e ) 1 的2 x 5 - g d d 当取e 3 ，4 ) 时，利用定理2 2 4 及( 7 6 ，2 ( 5 ，1 ) - g b d ，( 1 0 1 ，2 5 ，1 ) - g b d ，( 1 2 6 ，2 5 ，1 ) 一g b d 的存在性，可知( 2 5 t - 4 - 1 ，2 x5 ，1 ) 一c b d 存在 当t = 3 2 或3 3 时，设为e 正整数由定理2 3 2 知，型为5 e 和5 7 的 2x5 4 2 d d s 存在由引理2 1 1 知，t d ( 7 ，2 5 ) 存在从个 r d ( r ，2 , 5 ) 的某一 个组中删除2 5 一e 个点，得到个型为2 5 1 的 6 ，7 - ( a ) d 利用这个c d d ， 在定理2 2 1 中取m = 5 ，得到个型为1 2 5 6 ( 蚴1 的2 5 - c d d 当e r i o ，1 5 时，利用定理2 2 4 及( 1 2 6 ，2 x 5 ，1 ) 一c b d ，( 5 1 ，2 5 ，x ) - c b d ，( r e ，2 5 ，x ) - c b d 的存在性，可知( 撇+ l ，2 5 ，1 ) 一c b d 存在0 综合引理3 1 - 3 6 ，我们就得到了t 1 5 2 5 格子区组设计的存在性 三 主要结果的证明 定理3 7 设t 为正整数，则( 2 酏+ l ，2 5 ，1 ) - g b d 存在 至此，结合引理1 3 1 ，我们得到了所要的结论，即： 定