（应用数学专业论文）三元系的大集问题.pdf

摘要 一个v 阶a - f o l ds t e i n e r 三元系大集l s t s x ( v ) ，是由q 个。秒阶s t e i n e r 三元系( x ，b 1 ) ， ( x ，b 2 ) ，( x ，岛) 构成的族，使得x 中每个由不同元构成的无向三元组都恰好出现在 a 个s t s ( v ) 中一个l s t s , 、( v ) 称为不可分的，记为i d l s t s a ( 铷) ，如果对任意a 1 ) 存在i d l s t s a ( v ) ? 本文第一部分将利用可分的烛台系统( p c s ) 和v 阶a - f o l d 带洞s t e i n e r 三元系大集( h l s t s a ( v ) ) 作为辅助设计，采用递归构造方法研 究i d l s t s ：、( v ) ，并且给出结论：当a = 5 ，6 ，口三1 ，3 ( m o d6 ) 且口3 时存在i d l s t s x ( ) ， 唯一可能的例外值为i d l s t s a ( 7 ) 一个钉阶a - f o l dh y b r i d 三元系h t s ( v ，a ) = ( x ，召) ，指的是由u 元集x 上一些循环和 可迁三元组简称区组) 构成的集合8 ，使得x 中每个由不同元构成的有序对都恰好出现在 它的a 个区组中一个h y b r i d 三元系的超大集o l h t s ( v ，入) ；是指一个族 ( y 秒) ，a i ) i ， 其中y 为v 十1 元集，对于每个y ( y 可) ，a ) 是一个h t s ( v ，a ) ，并且所有a 形成y 中全部循环和可迁三元组的分拆本文第二部分讨论o l h t s ( v ，a ) 的存在性问题，并且给 出结论：存在o l h l l s ( v ，a ) 当且仅当a = 1 ，2 ，4 ，v 三0 ，1 ( m o d3 ) ，且v 4 关键词：s t e i n e r 三元系h y b r i d 三元系大集超大集烛台系统 i i i a b s t r a c t a c o l l e c t i o n ( x ，b 1 ) ，( x ，岛) ，( x ，岛) o f qs t s ( v ) si sa a - f o l dl a r g es e to f s 1 1 s ( v ) a n d d e n o t e db yl s t s ；( v 、i fe v e r y3 - s u b s e to fxi sc o n t a i n e di ne x a c t l yas t s ( v ) so ft h ec o l l e c t i o n i ti si n d e c o m p o s a b l ea n dd e n o t e db yi d l s t s a ( v ) i f t h e r ed o e sn o te x i s ta nl s t s x ，( v ) c o n t a i n e d i nt h ec o l l e c t i o nf o ra n y la n do r d e r s 移兰1o r3 ( m o d6 ) d ot h e r ee x i s ta ni d l s t s a ( v ) ? i nt h ef i r s tp a r t o ft h i sp a p e r ，w eu s ep a r t i t i o n a b l ec a n d e l a b r as y s t e m s ( p c s s ) a n dh o l e ya - f o l dl a r g es e to f s t s ( v ) ( h i 。s t s ( v ) ) a sa u x i l i a r yd e s i g n s t oe s t a b l i s har e c u r s i v ec o n s t r u c t i o nf o ri d i 。s t s a ( u ) i ts h o w st h a tt h e r ei sa ni d l s t s x ( v ) f o ra = 5 ，6 ，钉三lo r3 ( m o d 6 ) ，a n dv 3w i t ht h eo n l y p o s s i b l ee x c e p t i o ni d l s t s x ( 7 ) a h y b r i dt r i p l es y s t e mo fo r d e ruh t s ( v ，a ) = ( x ，屡) ，w h e r e 侈i sac o l l e c t i o no fc y c l e a n dt r a n s i t i v et r i p l e so fxs u c ht h a te v e r yo r d e r e dp a i ro fxb e l o n g st oat r i p l e so f8 a n o v e r l a r g es e to f + d i s j o i n th t s ( v ，a ) ，d e n o t e db yo l h t s ( v ，a ) ，i sac o l l e c t i o n ( y ) ，4 i ) ) i ， s u c ht h a tyi sa ( u + 1 ) - s e t ，e a c h ( y 可) ，a ) i sah t s ( v ，a ) a n da l la sf o r map a r t i t i o no f a l lc y c l ea n dt r a n s i t i v et r i p l e so fyi nt h el a s tp a r to ft h i sp a p e r , w es h a l ld i s c u s st h ee x i s t e n c e p r o b l e mo fo l h t s ( v ，a ) a n dg i v et h ef o l l o w i n gc o n c l u s i o n ：t h e r ee x i s t sa no l h t s ( v ，a ) i f a n do n l yi fa 一1 ，2 ，4 ，钉三0 ，l ( m o d3 ) ，a n dv 4 k e yw o r d s ：s t e i n e rt r i p l es y s t e m h y b r i dt r i p l es y s t e m l a r g es e to v e f l a r g es e t c a n d e l a b r as y s t e m i v 学位论文原创性声明 本人所提交的学位论文三元系的大集问题，是在导师的指导下，独立进行研究 工作所取得的原创性成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已 在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：钮灸湖 7 西年d 月伽1 7 一 指导教师确认( 签名) ：匀0 夕 如亨年孑月z o 日 学位论文版权使用授权书 本学位论文作者完全了解河北师范大学有权保留并向国家有关部门或机构送交学 位论文的复印件和磁盘，允许论文被查阅和借阅。本人授权河北师范大学可以将学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它复制手段保 存、汇编学位论文。 ( 保密的学位论文在年解密后适用本授权书) 论文作者( 签名) ：舞戛 孙富年3 月2 0 日 指导教师( 签名) ：1 习善岁 舻3 月汤目 i l 引言 本文共分为两个部分，第一部分研究了多重不可分的s t e i n e r 三元系大集的存在问题， 第二部分研究了h y b r i d 三元系超大集的存在问题 1 设x 为有限集一个u 阶s t e i n e r 三元系，记为s t s ( v ) ，是指一个序偶( x ，召) ，其中 召为x 中由不同元构成的无向三元组( 称为区组) 构成的集合，使得x 中每个无序对均恰 好出现在b 的a 个区组中文献 1 】中已经证明存在s t s ( v ) 号v 三1 ，3 ( m o d6 ) 相同集合上的两个s t s ( v ) ( x ，4 ) 与( x ，召) 称为不交的，如果4n 召= d v 一2 个 互不相交的7 3 阶s t e i n e r 三元系构成一个v 阶s t e i n e r 三元系大集，记为l s t s ( v ) 18 5 0 年， c a y l e y 在文献 2 中首先提出只存在两个不交的s t s ( 7 ) ，即不存在l s t s ( 7 ) 文献f 3 ，4 ，5 】 给出了l s t s ( v ) 的存在谱：u 兰1 ，3 ( r o o d6 ) ，u 7 2 0 0 5 年季利钧在文献【6 】中给出了 l s t s ( v ) 存在性的简化证明 一个v 阶a - f o l d s t e i n e r 三元系大集l s t s ；、( v ) ，是由口个v 阶s t e i n e r 三元系( x ，廖1 ) ，( x ， 饬) ，( x ，召。) 构成的族，使得x 中每个由不同元构成的无向三元组都恰好出现在a 个 s t s ( v ) 中当a = 1 时，l s t s i ( v ) 即是s t e i n e r 三元系大集l s t s ( v ) ，此时入可省略不写 1 9 9 5 年，g r i g g s 和r o s a 在文献【7 】中曾经提出一个问题：对怎样的v 兰l ，3 ( m o d6 ) ， 及a ( 1 ) 存在l s t s x ( v ) ，并且对任意a 7 上至少有5 个h t s ( v ) 于是x 可能出现的区组数【4 ( v + 1 ) 5 】( v 一1 ) = 4 v ( v 一1 ) 一( v 1 ) 上存在且仅存在4 个h t s ( v ) ( y 箩) ，b t ) ，j = 0 ，1 ，2 ，3 于是，o l h t s ( v ) 可记为 ( y 磐) ，豌) ：可k j = 0 ，l ，2 ，3 ) 定理o 5 【1 5 】当v 满足下列条件之一时，o l h t s ( v ) 存在： ( 1 ) v 三1 ，3 ( m o d6 ) ，v 7 ； ( 2 ) v 三0 ，4 ( m o d1 2 ) 设x 为w + l 元集，y 为v + w + l 元集如果存在一个o l h t s ( v + w ) = ( y 秒) ，心) ： y y ) j = 0 ，1 ，2 ，3 ) ，且存在一个o l h t s ( w ) = ( x z ) ，毽) ：z x ，j = 0 ，1 ，2 ，3 ) 满 2 足：( i ) x 】厂；( i i ) 对任意z x 及j = 0 ，1 ，2 ，3 ，硬鸽则称此o l h t s ( w ) 为 o l h t s ( v + w ) 的一个子系，记为o l h t s ( v ；叫) 当w = 0 ，1 时 记碑= 谚 本文第二部分将通过直接或递归的构造方法，给出o l h t s ( v ) 的存在谱在2 1 节中 给出一些辅助设计和递归构造在2 2 节中讨论o l h t s ( v ) 的存在性在2 3 节中给出结 论 3 1 1 一些小设计 1 i d l s t s a ( v ) 的存在问题 本节利用直接构造的方法给出一些小设计定义点集x = 磊一2t o n ，6 ) 磊一2 为模 口一2 的剩余类加群磊一2 上所有三元组在这个群的作用下可分拆为轨道d 1 ，0 2 ，d n ， 其中佗= ( 秽一3 ) ( 一4 ) 6 当v 一2 兰5 ( m o d6 ) 时 所有的轨道均为全轨，当v 一2 三 1 ( m o d6 ) 时，存在一个( u 一2 ) 3 长的短轨 对三元组b = o ，b ，c ) ，记b + d = 口+ d ，b + d ，c + d ) ( m o d 一2 ) 如果b 1 ，岛属于 同一个轨道，b l 和b 2 之间的循环距离定义为c d ( b 1 ，b 2 ) = m i n d 1 ，d 2 ) ，其中b 1 + d 1 = 岛，岛+ d 2 = b 1 如果b l ，b 2 属于不同轨道，不定义c d ( b 1 ，b 2 ) 引理1 1 存在i d l s t s 5 ( 口) ，其中u 9 ，1 3 ，1 5 ) 证明：在点集磊一2u o ，6 上构造所需设计，其中钞1 9 ，1 3 ，1 5 根据定义，它应包含 5 ( 可一2 ) 个s t s ( u ) 对于给定的l s t s a ( v ) 证明其是不可分的，只需对1 a 【害j 说明 它不包含l s t s x ，( 秽) 即可 ( 1 ) v = 9 首先构造5 个s t s ( 9 ) ，区组集础，瑶，稀定义如下 懿 瑶 魂瑶 罐 d 1 056 016234 012456 0 2 346 045045013235 o a 126356046126134 0 4 125036145036125 0 5 02413 51352 46o24 0 6 23a5 6a3 4n56a0lo d 7 02a13a46a 02o 35a o a 03a25n14a14a26n 0 9 45b01b23b 34b 23b o l o 16b24b05b05b16b d 1 1 26b14b03b25b 36 b 0 1 26ab 5aboab1nb4ab 令群= b + i ：b 瑶) ，i 历，j = 1 ，2 ，5 则可以得到3 5 个s w s ( 9 ) ，它们构成 l s t s s ( 9 ) 下面验证它是不可分的 如果存在诸目( i z 7 ，1 j 5 ) 中的7 个可以构成l s t s ( 9 ) ，那么历u o 6 ) 中所 5 有三元组均出现1 次x 寸i z 7 ，设它们是个磅，x j = 7 ，而诸磷与瑶中所含区组在 j = l 4 各轨道中的分布数是同样的令诸瑞的区组出现在所有1 2 个轨道( 0 1 , ，克= 1 ，2 ，1 2 ) 中的个数序列为b ( 歹) = ( 6 i ，醒，6 2 ) ，则 b ( 1 ) = ( 1 ，1 ，1 ，o ，2 ，0 ，0 ，3 ，3 ，0 ，0 ，1 ) ， b ( 2 ) = ( 2 ，1 ，1 ，1 ，0 ，0 ，3 ，0 ，0 ，0 ，3 ，1 ) ， b ( 3 ) = ( 1 ，1 ，0 ，1 ，2 ，2 ，o ，1 ，1 ，1 ，1 ，1 ) ，b ( 4 ) = ( 0 ，2 ，2 ，1 ，0 ，2 ，1 ，0 ，0 ，2 ，1 ，1 ) ， b ( 5 ) = ( 1 ，0 ，1 ，2 ，1 ，1 ，1 ，1 ，1 ，2 ，0 ，1 ) 不难看出存在i 。s l s ( 9 ) 的必要条件是方程组巧6 ；= l o k l = 7 ，i 历，1 j 5 ，有整 数解，但计算表明此方程组没有整数解，即不存在t s t s ( 9 ) 如果存在诸霹( i 历，1 j 5 ) 中的1 4 个可以组成i 。s a s 2 ( 9 ) ，那么z tu 【o ，6 ) 中 所有三元组均出现2 次设它们是协个研不难看出存在l s t s 2 ( 9 ) 的必要条件是方程组 协醒= 2 i o 七i = 1 4 ，i 历，1 歹5 ，有整数解，但计算表明此方程组没有整数解，即不 存在l s a s 2 ( 9 ) ( 2 ) 秽= 1 3 时，首先构造5 个s r s ( 1 3 ) ，区组集础，瑶，罐如下注意到瑶第一行 的5 个区组属于同一个轨道，( 对应的轨道为 z ，i + 1 ，i + 3 ) ：i z 1 1 ) ) 锐：067 9 026 o 91 0 17n278l8b 37b 047161 029o3 8949 b21 0b 058481 045n0nb 56b31 0n 1595 71 068o 瑶：012 14 60 91 018 口26b6 89 o3 417 9361 03 9o3 8b0o6 05 625 9471 04 5o49b21 0o 07823 75 81 06 7n57611 06 13 5248 魂：01 21460 91 018a2 6b689 0 3417 93 81 036 口39b0ob 0 56 23 74 51 049o4 7b21 0 口 0 782486 71 057a5 8611 06 135259 瑶：014 13 6171 009 口19 b478 0 232 67341 0 18o24 b7ob 0 572 89581 035n38 621 0o 5 0 683 796 91 04 6a56b01 0b 125459 磁：015 24 5081 006a0 7b579 0 2926 7161 017a13b4ab 03 436 9351 023a56 b 91 0a 128378471 058a89b21 0b 149468 令毽= b + i ：b 弼) ，i z n ，j = 1 ，2 ，5 则可以得到5 5 个s t s ( 1 3 ) ，它们构成 l s t s s ( 1 3 ) 注意到轨道“i ，i + 1 ，i + 3 ) ：i 五1 ) 的区组全部分布在 科：i z l l 中，因 此不难证明l s t s s ( 1 3 ) 是不可分的 ( 3 ) v = 1 5 时，首先构造5 个s t s ( 1 5 ) ，区组集魂，瑶，蠕如下注意到魂第一行 的5 个区组属于同一个轨道，( 对应的轨道为 i ，i + 1 ，i + 3 ) ：i 五3 ) ) 瑶： o13124235346679 02 6091 03 9a11 1a271 15 7b 04 5171 04 7a21 2a381 l0ab o 782 81 058a61 0a51 01 111 2b 1563 71 229b 31 0b01 11 2 491 1 189591 2 48b 61 1b41 01 2681 2 s o ：012 091 0281 22 9a11 1a179 03 4181 04 71 25 7a31 2a2 36 o5 6 271 0 691 268a41 0a2 45 07 84 81 151 01 249 b11 2b3 89 13 53 71 1o1 11 258b21 1b0ab 14 65 91 161 01 167b 31 0b 懿：012 0 91 0381 23 9a11 2a179 0 34181 0471 25 7a21 1a2 36 o 56271 0691 268a41 0a24 5 0 78371 101 11 258 b11 1b289 135481 151 01 249 b21 2b0ab l4 6591 l61 01 167 b31 0b 6 鹾：0l5 171 0671 119a21 0a28 9 0 233 81 0241 237al1 2b 2 5 7 o 466 91 0361 248a21 1b1 11 2a o 780 91 1581 256a51 0b41 01 1 126l81 1791 2 39668 b01 01 2 13 43 51 145 9 4760ab 磁：015 0 71 047l l 08a71 2a368 02 4131 0061 216a91 0a391 2 17 9481 0141 223a51 0b4 69 2 560 31 121 01 245a81 2b5 89 27 8181 l51 11 2 09b34b1 1ab 35 72 91 161 01 112b67 b 令霹= b + i ：b 瑶) ，i z 1 3 ，j = 1 ，2 ，5 则可以得到6 5 个s t s ( 1 5 ) ，它们构成 l s t s s ( 1 5 ) 注意到轨道 i ，i + 1 ，i + 3 ) ：i z 1 3 ) 的区组全部分布在 魂：i z 1 3 中，因 此不难证明l s t s 5 ( 1 5 ) 是不可分的 口 引理1 2 存在i d l s t s 6 ( v ) ，其中钉 9 ，1 3 ，1 5 ) 证明：在点集磊一2ua ，6 ) 上构造所需设计，其中钞 9 ，1 3 ，1 5 根据定义，它应包含 6 ( v 一2 ) 个s t s ( v ) ( 1 ) v = 9 时，首先构造6 个s t s ( 9 ) ，区组集魂，瑶，瑶如下注意到硪，瑶，瑶第 一行的两个区组均属于同一个轨道，距离为1 雠：024 1 35 羔垒堡016 03b0 5a12b23a 25 63 4645b6a6 瑶：024 1 35 l 垒卫0l6 0 360 5a12 623a 25b34b45 66ab 瑶：024 135 1 垒鱼01b 03 60 5n12 62 3a 25b 34b 45 66ab 魂：m 出0 1204 60 5b 】3b15623 624 b34 56ab 7 磁：013 026o 5o046 l2 口14 5 l6625b2 344 6o35638b 磁：015 o260341243 5623n 45o16 口13b4662560ob 令霹= b + i ：b 瑶) ，i 历，j = 1 ，2 ，6 则可以得到4 2 个s a s ( 9 ) ，它们构成 l s t s 6 ( 9 ) 下面证明此设计中不包含i 。s a s ( 9 ) ，l s t s 2 ( 9 ) 和i 。s 1 s 3 ( 9 ) ( a ) 不包含i 。s 1 s ( 9 ) 因为轨道 i ，i + 2 ，i + 4 ) ：i 历) 的区组成对出现在 磁：i 历) ，歹= 1 ，2 ，3 中，所以此设计中不包含7 个s t s ( 9 ) 可以构成l s t s ( 9 ) ( b ) 不包含l s t s 2 ( 9 ) 因为轨道 i ，i + 2 ，i + 4 ：i 历) 的区组成对出现在 霹： i 历) ，j = 1 ，2 ，3 中，所以在 霹：i 历) ，歹= 1 ，2 ，3 中应选取7 个小集，这时轨道 i ，i + 3 ，n ) ：i 历) 的区组已出现7 次而这个轨道余下的区组只在 研：i 历】- 中 出现，并且三个一起出现所以此设计中不包含1 4 个s t s ( 9 ) 可以构成l s t s 2 ( 9 ) ( c ) 不包含l s t s 3 ( 9 ) 因为轨道 i ，i + 2 ，i + 4 ) ：i 历) 的区组成对出现在 霹： i 历) ，j = 1 ，2 ，3 中，所以此设计中不包含2 1 个s t s ( 9 ) 可以构成l s t s 3 ( 9 ) ( 2 ) u = 1 3 时，首先构造6 个s t s ( 1 3 ) ，区组集魂，瑶，瑶如下注意到饿第一行 的6 个区组属于同一个轨道，( 对应的轨道为 i ，i + l ，i + 3 ) ：i z 1 1 ) ) 磷：013 12423 53 46457 679 026071 016o19658o38 9 04 8l51 027n2 8b56631 0o o5 9291 049o3 7b0 口641 0b 17 8681 0 瑶：01 2146091 018o26b68 9 0 34 179361 0 3 9o3 8b21 0o 0 56 23 7 471 04 5a4 9b11 0b o 7824 8581 06 7n5 7b0 口b l3525 9 魂：012 14 60 91 0l8 口2666 89 034 1793 61 0 39o38 6 21 0n 05 623 74 71 045d49 b11 0b 07 824 8581 067 口57b0nb 135259 8 鹾：01 214 60 91 018o29b4 59 0 34179251 024n36b31 0 口 05623 74 81 05 7n47b 11 0b 07 826 86 71 06 9o58b0 口b 13 538 9 磷：01 413 70 81 015o19 b 4 89 0 232 59161 02 7o26 b 91 0n o 563 58241 03 4o45 b 31 0b 0 79369571 068n7860 口b 12846 7 锑：01 513 70 71 014o19b578 0 2924 7161 03 5o23 b21 0 口 0 382 56341 06 8o4 5b81 0b 0 463 69591 079o6 7b0ob 1284 89 令目= b + i ：b 弼) ，i z l l ，歹= 1 ，2 ，6 则可以得到6 6 个s t s ( 1 3 ) ，它们构成 l s t s 6 ( 1 3 ) 注意到轨道 t ，i + 1 ，i + 3 】：i z 1 1 ) 的区组全部分布在 科：i z n 中，因 此不难证明l s t s 6 ( 1 3 ) 是不可分的 ( 3 ) = 1 5 时，首先构造6 个s a s ( 1 5 ) ，区组集魂，瑶，懿如下 魂：013 l24235346 679 0 260 91 001 11 239o11 1o371 2 0 45171 041 01 247 口21 2n681 2 078 2 81 05l o1 158o61 0 口576 15 62 71 14 91 1 29b11 2b 61 16 189381 1591 2 48b31 060nb 锑：01 2091 061 01 129n11 1o179 03 4 181 0 591 1 57o31 2o2 36 05 6271 001 11 268n41 0n2 45 078371 1281 2 49b11 2b389 135481 1471 258b21 1b0o6 146691 2 51 01 2 6 7b31 06 9 魂：01 2o 91 061 01 129n11 1o179 o34l81 0591 157o31 2 口236 0562 71 001 11 268o41 0o245 07 83 71 1 281 2 49b11 263 89 13 5481 14 71 258b21 lb0ob 146691 251 01 26 7631 06 磁：015 171 0 4l o1 1 l9o21 0n25 7 0 23381 0671 137n11 2b289 0466 91 001 01 2 48o21 16 459 0 78o 91 1241 256o51 0b791 2 126181 l3 61 2476 68b0ob 13 43 51 15 81 239b1 11 2o 磁：0l5 o 71 04 71 1o8n71 2 口368 02 4131 0061 2l6 凸91 0o469 l79 481 0 391 2 23o81 2b 5 89 256031 161 01 14 5o51 06141 2 278181 121 01 2 0 963 461 1 凸b 35 7291 151 11 21266 7b 魂：0l 2261 0161 213o01 2n2 37 0 34391 0351 228o71 1o245 0 574 71 0791 246n51 0o48 9 06 9081 181 01 214b 01 0b568 1593 61 141 11 2 38b21 2b9o6 178291 l 11 01 167b51 1b 令联= b + i ：b 瑞) ，i z 1 3 ，j = 1 ，2 ，6 则可以得到7 8 个s 1 s ( 1 5 ) ，它们构成 t s r r s 6 ( 1 5 ) 下面证明此设计中不包含i s r s ( 1 5 ) ，l s t s 2 ( 1 5 ) 和t s l s 3 ( 1 5 ) 因为轨道 i ，i + 1 ，i + 3 ) ：i z 1 3 的区组只在 斟：i z x 3 ) 和 群：i z 1 3 中出现，且在 研：i z 1 3 中出现5 次，在 研：i z 1 3 中出现1 次假设从 磁：i z 1 3 中取z 个小集，从 霹：i z 1 3 中取y 个小集 ( a ) 不包含l s l s ( 1 5 ) 若要使轨道 i ，i + 1 ，i + 3 ) ：i z x 3 的区组均恰好出现一次， 需满足5 z + 可= 1 3 ，其有三组解( 1 ) 3 7 = 0 ，秒= 1 3 ，即从 霹：i z t 3 中取1 3 个小集，而 1 0 此时轨道 i ，i + 6 ，i + 7 ) ：i 历3 ) 的区组重复；( 2 ) z = 1 ，剪= 8 ，即从 研：i z 1 3 中 取1 个小集，从 礴：i z 1 3 中取8 个小集，而此时轨道 i ，i + 6 ，i + 7 ) ：i z 1 3 ) 的区 组重复；( 3 ) z = 2 ，夕= 3 ，即从 磁：i z x 3 中取2 个小集，从 霹：i z 1 3 ) 中取3 个小 集，而此时轨道 i ，i + 1 ，i + 3 ) ：i z x 3 ) 的区组重复矛盾 ( b ) 不包含i 。s l s 2 ( 1 5 ) 若要使轨道 i ，i + 1 ，i + 3 ) ：i z 1 3 ) 的区组均恰好出现两次， 需满足5 z + y = 2 6 ，并且要求z ，秒1 3 ，其有三组解( 1 ) z = 3 ，可= 1 1 ，即从 磁：i z 1 3 ) 中取3 个小集，从 霹：i 五3 ) 中取1 1 个小集，注意到轨道 ，i + 3 ，6 ) ：i z 1 3 的 区组在 研：i z 1 3 ) 中出现3 次，此时此轨道的区组出现次数已为3x1 1 = 3 3 矛 盾；( 2 ) z = 4 ，y = 6 ，即从 磷：i z 1 3 中取4 个小集，从 霹：i z 1 3 ) 中取6 个小 集，注意到轨道 i ，i + 2 ，a ) ：i z 1 3 的区组在 霹：i z 1 3 ) ，j = 2 ，3 ，6 中各出现2 次，若要使这个轨道的区组均恰好出现两次，则还需从 群：i z x 3 ) 和 霹：i z l s ) 中共取7 个小集注意到轨道 i ，i + 3 ，6 ) ：i z 1 3 的区组在 群：i z 1 3 中出现 3 次，在 群：i z 1 3 ) ，歹= 2 ，3 ，4 中各出现1 次，若要使这个轨道的区组均恰好出现两 次，则还需从( 研：i z 1 3 ) 中取1 个小集而轨道( i ，i + 4 ，o ) ：i z 1 3 的区组在 1 目：i 历3 ，j = 1 ，2 ，3 ，6 中各出现1 次，在 研：i z l a 中出现2 次，按照如上取法，此 轨道区组数为1 4 + 1 7 + 2x1 + 1 6 = 1 9 矛盾；( 3 ) z = 5 ，= 1 ，即从 科：i z 1 3 中取5 个小集，从 研：i 历3 ) 中取1 个小集，注意到轨道 i ，i + 3 ，口) ：i z 1 3 的区组 在 磁：i z 1 3 ) 中出现4 次，在 群：i z 1 3 和 霹：i z 1 3 中各出现1 次，若要使 这个轨道的区组均恰好出现两次，则还需从 群：i z 1 3 ) 和 霹：i z l a 中共取6 个小 集而轨道 ，i + 2 ，n ) ：i 历3 ) 的区组在 霹：i z 1 3 ，j = 2 ，3 ，6 中各出现2 次，按照 如上取法，此轨道区组数为2x6 + 2 1 = 1 4 矛盾 ( c ) 不包含l s t s 3 ( 1 5 ) 若要使轨道 i ，i + l ，i + 3 ) ：i 磊3 ) 的区组均恰好出现三次， 需满足5 z + 秒= 3 9 ，并且要求z ，1 3 ，其有两组解( 1 ) z = 6 ，! ，= 9 ，即从 磁：i z a 3 】 中取6 个小集，从 磅：i 历3 ) 中取9 个小集注意到轨道 i ，i + 3 ，口 ：i z 1 3 的区组 在_ 研：i z 1 3 中出现4 次，在 群：i z a 3 和 群：i z 1 3 中各出现1 次，若要使 这个轨道的区组均恰好出现三次，则还需从 研：i z 1 3 和 研：i z 1 3 中共取1 5 个 小集按照如上取法，轨道 i ，i + 2 ，o ) ：i z l a 的区组出现次数为2 1 5 + 2x 9 = 4 8 矛盾；( 2 ) z = 7 ，可= 4 ，即从 斟：i z 1 3 ) 中取7 个小集，从 霹：i z t 3 中取4 个小集注意到轨道 t ，i + 3 ，n ) ：i z 1 3 的区组在 科：i 历3 ) 中出现4 次，在 研：i z l a ) 和 霹：i z 1 3 中各出现1 次，若要使这个轨道的区组均恰好出现三 次，则还需从 群：i 历3 ，和 霹：i z t 3 中共取1 1 个小集按照如上取法，轨道 i ，i + 2 ，d ：i z 1 3 ) 的区组出现次数为2 1 1 + 2x4 = 3 0 矛盾 口 1 2 递归构造 在这一节，首先介绍烛台t 设计的定义，然后给出几个有用的构造 设v ，8 是非负整数，t 为正整数，k 为一些正整数构成的集合一个阶数为v 的烛台形 t 设计( 或亡c s1 1 6 1 ) ，是一个四元组( x ，s ，多，4 ) ，它满足以下条件： ( 1 ) x 是一个v 元集； ( 2 ) s 为x 的一个8 元子集，称作柄； ( 3 ) 9 = g 1 ，g 2 ) 是由x 的一些非空子集构成的集合，且划分x s 9 的元素称 为组或分支； ( 4 ) 4 是由x 的一些子集构成的集合，称其元素为区组，区组长度属于k ； ( 5 ) 对于x 的每个t 元子集t ，若对每个i 都满足i tn ( s og i ) i t ，那么t 恰包含于 4 的一个区组中而对于任意i ，sug i 的任意t 元子集都不包含于4 的任何区组中 通常把这样的设计记为c s ( t ，k ，钉) 一个t c s ( x ，s ，9 ，4 ) 的组型常记为( 引g i ：g 乡) ： l s l ) 如果乡包含他个大小为g i 的组( 1 z r ) ，并且柄的大小为8 ，则称此c s 的型为 ( 贫1 鳢2 卵r ：s ) 当k = 七) ，简记k 为k 当t = 3 ，k = 1 4 时，这样的烛台设计称为 烛台四元系，记作c q s ( g ? 1 夕多2 够r ：8 ) 【1 7 i 引理1 3 1 1 8 】存在c q s ( 9 3 ：s ) ，其中8 为偶数，9 兰0 ，8 ( m o d6 ) 并且夕8 在本文中，只考虑t = 3 和k = 3 ) 的烛台设计为方便，简记为c s ( g ? 1 夕；2 9 7 r ：s ) 一个v 阶s t e i n e r 可分组t 设计是一个三元组( x ，9 ，8 ) ，其中x 为w 元点集，乡是x 的分拆( 其元素称为组) ，召为x 的一些子集( 称为区组) 构成的集合，使得对任意b b 与任意g 9 都有l bng l 1 ，并且x 中任意由不同组元素构成的t 子集都恰好出 现在召的一个区组中当区组长度取自正整数集合k 时，记其为g d d ( t ，k ，秽) ，其型为 t = i c i ：g 9 ) 一个g d d ( t ，k ， ) 有n i 个绑( 1 i r ) 长组时，其组型记为 计1 鳢2 鳄当k = 七) ，简记k 为k 一个c s ( 夕? 1 鳢2 鳄：8 ) ( x ，s9 ，4 ) ，8 2 称为可分的，记作p c s ( g ? 1 夕；2 簖r ： s ) ，如果区组集4 可以分拆为m x ( z g ，g 9 ) 和4 1 ，4 2 ，4 。一2 ，使得这些子集满足 如下性质： ( i ) 对任意z g ，g 夕，凡是型为1 e ，t ra i g i i g i ( 1 g i + s ) 1 的g d d ( 2 ，3 ，e 1 t ，o i 仇+ 8 ) 的区组集，其长组为gus ； ( i i ) 对任意1 i 8 2 ，( x s ，9 ，a ) 是型为卯1 鳢2 鳄的g d d ( 2 ，3 ，e l ，a i g i ) 如果区组集凡( z g ，g 够) 和a 1 ，a 2 ，a 一2 同时满足上面两个条件，并且互 不相交，则通过计算可知( x ，s ，9 ，( u x e x s a z ) u ( u l i 3 ，则存在p c s ( 9 3 ：s 一1 ) 为利用p c s 来构造i d l s t s a ( v ) ，需要给出a f o l d 的的带洞大集的定义 令x 为幻元集，y 为x 的伽元子集，伽2 在点集x 上，一个洞为y 的s t s ( v ，a ) 带洞大集，简记作h l s t s x ( v ，伽) ，为a x ( 3 ) a y ( 3 ) 的分拆a l ，a 2 ，a ( 口一2 ) ，满足以下条 件：( 1 ) 1 i a ( 一叫) ，每个( x ，a ) 是一个s t s ( v ) ；( 2 ) a ( v 一叫) + 1 i a ( u 一2 ) ，每 个a t 是一个型为1 ”叫叫1 的g d d ( 2 ，3 ，v ) 的区组集，长组为y 这里x ( 3 ) 和y ( 3 ) 分别表示 x 和y 中所有三元组当a = l 时，简记作h l s t s ( v ，w ) 引理1 5 ( 填洞) 如果存在p c s ( 9 3 贫1 鲮2 鳄r 则存在h l s t s x ( 1 t ra i g i + g o + s ，g o + s ) i d l s t s x ( 1 衙a i g i + g o + s ) ：s ) ，8 2 和h l s t s x ( g i + s ，s ) ，1 i r ， 进一步，如果存在i d l s t s a ( g o + s ) ，则存在 证明：令a o = 1 ，( x ，s ，9 ，a ) 为给定的p c s ( g o g l 1 夕；2 鳄：s )