（运筹学与控制论专业论文）r完美（υkλ）md存在性进展.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 摘要：1 9 7 1 年n s m e n d e l s o h n 在区组设计中引入元素循环有序的概念【1 3 】他首先 应用n s t e i n e r - - 元系上对其概念进行了推广，这种新的三元系就是后来大家所熟 知的m e n d e l s o l m 三元系在对此研究的基础上1 9 7 7 i g 由m e n d e l s o h n 提出了完美循 环设计 1 4 1 的概念。许多学者在其后发表的文章中均对此类设计进行了进一步的 研究 令 与a 为正整数，彤为正整数集一个( t ，ka ) 一m e n d e l s o h n 设计( 简写为( 口，k a ) m d ) 是一个有序对( x ，_ 8 ) 其中，x 是一个钉元集合( 称之为点集) ，目是由x 中缸 子集( 称之为区组) 所组成的集合，区组所含元素是循环有序的，且区组的大小属 于k ，使得x 中任意有序对恰相邻出现在8 中的a 个区组中如果对于所有t = 1 ，2 ， 。r x 中任意有序对均恰以扛间隔的形式在8 中出现a 次，则称其为r 完美m e n - d e l s o n 设计，并且简记为r - 完美( t ，a ) m d 我们在本篇文章中研究r - 完美( v ，k ，a ) m d 的存在性r 完美( v ，k 。a ) m d 是 我们常见的完美m e n d e l s o n 设计( p m d ) 在概念上的推广。本文论述了作者在硕士 期间的工作，即当r 完美( y k ，a ) m e n d e l s o h n 设计中的彤取不同的整数集合时，在 现有结果的基础上所做的拓展 全文共分五章，本文中所用的全部符号均在第一章中说明 第一章，综述$ r - 完美( 弘k ，a ) m d 的研究背景，定义以及当前该领域的研究成 果同时，作为对随后证明的铺垫，还介绍了一些辅助设计及相关的已知结果，以 及在本文中所用到的构造方法 第二章，主要对k = 3 ，蠡) 时的2 - 完美( t ， 3 ，后 ，a ) 一m d 进行讨论，给出一些未 知阶数不存在的证明，其中k 4 ，5 ，6 ，7 ) 第三章，对k = 4 ，耐时的2 - 完美( ， 4 ，日，a ) 一m d 进行讨论，给出一些未知阶 数不存在性的证明，其中k 5 ，6 ，7 ) 第四章，对4 完美( ， 5 ，6 ) ，a ) 一m d 进行讨论，给出一些未知阶数不存在性的证 明 第五章，主要对( t ，8 ，a ) 一p m d 进行讨论，主要是利用直接构造与递归构造从而 得到一些新的结果 关键词：区组设计；完美的m e n d e l s o h n 设计；带洞的完美的m e n d e l s o h n 设计；不完 全的完美的m e n d e l s o h n 设计：r - 完美的m e n d e l j o h n 设计 分类号：0 1 5 7 2 北京交通大学硕士学位论文 英文摘要 英文摘要 a b s t r a c t ：n s m e n d e l s o h ni n t r o d u c e dt h ec o n c e p to fc y c l i c a l l yo r d e r i n gt h e e l e m e n t si nb l o c kd e s i g n si n1 9 7 1 h ef i r s tl o o k e da tt h en a t u r a lg e n e r a l i z a t i o n o fs t e i n e rt r i p l e 毋p s t e m b t h e s et r i p l es y s t e m sw e r ei n i t i a l l yc a l l e d “c y c l i ct r i p l e s y s t e m s ”。b u tw t f f el a t e rr e n a m e dm e n d e l s o h nt r i p l es y s t e m s ( m t s s ) t h en o t i o n o fa “p e d e c tc y c l i cd e s i g n ”w a sa l s oi n t r o d u c e db ym e n d e l s o h ni n1 9 7 7 a n dt h e c o n c e p tw a sf u r t h e rs t u d i e db ym a n yr e s e a r c h e r s l e t a n dab ep o s i t i v ei n t e g e r s a n dl e tkb eas e to fp o s i t i v ei n t e g e r s ，a ( 口，k ，a ) m e n d e l s o h nd e s i g n ，d e n o t e db y ( t ，j ta ) - m d ，i 88p a i r ( 】， 层) w h e r ex i 8a u - s e t ( o f 妒n u ) a n d 召i 8a c o l l e c t i o no fc y c l i c a l l yo r d e r e ds u b s e t so fx ( c a l l e d b l o c k s ) w i t hs i y a 撼i nt h es e tk s u c ht h a te v e r yo r d e r e dp a i ro fx 哪c o n s e c u t i v e i ne x a c t l yab l o c k so f 吕i ff o r8 1 lt = 1 ，2 ，e v e r yo r d e r e dp a i ro fp o i n t so f xa r et - a p a r ti ne x a c t l yab l o c k so fet h e nt h e ( ka ) - m dj sc a l l e d 龇r - f o l d p e r y e c td e s i g na n dd e n o t e db r i e f l yb ya nr - f o l d 彬( 口，ka ) - m d t h eo b j e c t 啪r e s e a r c h e di nt h i st h e s i si sr - f o l dp e r f e c t ( t ，ka ) 一m d ，w h i c h i sc l o s e l yr e l a t e dt o ( 口，七，a ) 一p m d ，s i n c e ( t ，k ，a ) - p m di sas p e c i a lc a s eo fr - f o l d p e r f e c t 似k ，a ) 一m d 耐t hk = 耐 t h e r ea r ef i v ec h a p t e r si nt h et h e s i s ： t h ef i r s tc h a p t e ri n t r o d u c e ss o m eb a s i cc o n c e p t sa n dt h eb a c k g r o u n do fr - f o l dp e r f e c t ( t ，ka ) - m d m e a n w h i l e ，w ea l s oi n t r o d u c es o m ea u x i l i a r yd e s i g n s a n dc o n s t r u c t i o nm e t h o d bt h a tw ew i l l1 1 8 ei nt h i st h e s i s i nt h es e c o n dc h a p t e r ，w ew i l lm a i n l yf o c u so nt h en o n e x i s t e n c eo f2 - f o l d p e r f e c t ( t ， 3 ，七 ，a ) 一m d ，w h e r ek 4 ，5 ，6 ，7 ) i nt h et h i r dc h a p t e r ，w ew i l lm a i n l yf o c u so nt h en o n e x i s t e n c eo f3 - f o l dp e r f e c t ( 4 ，毋，a ) - m d ，w h e r ek 5 ，6 ，7 i nt h ef o u r t hc h a p t e r ，w ew i l lm a j n l yf o c u s0 1 1t h en o n e x i s t e n c eo f4 - f o l d p e r f e c t ( ， 5 ，6 ) ，a ) 一m d i nt h ef i f t hc h a p t e r w ew i l lm a i n l yf o c u so nt h ee x i s t e n c eo f 扣，8 ，a ) - p m d ， u s i n gb o t hd i r e c tc o n s t r u c t i o n sa n dr e c u r s r ec o n s t r u c t i o n s k e y - w o r d s ：b l o c kd e s i g n ；p e r f e c tm e n d e l s o h nd e s i g n ；h o l e l yp e r f e c tm e n - d e l s o h nd e s i g n ；i n c o m p l e t ep e r f e c tm e n d e l s o h nd e s i g n ；r - f o l dp e r f e c tm e n d e l s u h n d e s i g n c l a s s n o ：0 】5 7 2 致谢 首先特别感谢导师常彦勋教授，本论文的各项工作都是在常老师的悉心指导 和亲切关怀下顺利完成的在这两年多的研究生期间。无论是在研究生课程学习过 程中还是在文章的选题、研究中，常老师自始至终都给予我大力的支持和无私的 关怀没有他的帮助，我根本不可能完成本文常老师严谨的治学态度，广博的知 识，精益求精的科研作风，敏锐的学术思想和忘我的工作精神极大的影响并鞭策了 我更重要的是使我学到了许多治学和做人的道理，跟随常老师求学的这段时间将 对我以后人生道路产生重大影响我将铭记常老师的教诲，努力工作，不断进取 此外，莸还要感谢郝荣陵教授，冯衍全教授，江中豪教授对我的悉心指导，这些 指导对我拓宽思路和解决难题都有极大的帮助感谢周君灵师姐，张晶师姐还有 冯原予、高晶晶、李坤朋、常相茂等师兄师姐师弟师妹对我学业的热情帮助谢谢 所有关心我的人 最后，诚谢各位专家和学者在百忙中审阅我的论文，诚恳接受您的宝贵意见 和建议，并期待您的批评和指导。 高源 e o o c , - 午h f l 于北京交通大学理学院 北京交通大学硕士学位论文1 绪论 1 1 研究背景 1 绪论 1 9 7 1 年n s m e n d e l s o h n 在区组设计中引入元素循环有序的概念 1 3 1 他首先 应用到s t e i n e r 一= 元系上对其概念进行了推广这种新的三元系就是后来大家所熟 知的m e n d e l s o h n 三元系在对此研究的基础上1 9 7 7 年m e n d e l 8 0 h n 又提出了完美循 环设计【1 4 】的概念，许多学者在其后发表的文章中均对此类设计进行了进一步的 研究 m e n d 吐址n 弓i 入的循环有序概念是这样的：设 d l ，n 2 ，n k ) 是由七个不同的元 素组成的集合，如果这个集合中的元素满足a l o a l ，均是存在，但是 - ：l l v = 6 并且天= 2 或者a 为奇数时候存在性未 知 定理1 2 5 【7 】对于( ，7 ， ) 一p m d 的存在的情况，即当一7 时，对 i - v 7 t l c a v ( v 一 1 ) 三0 ( r o o d7 ) 均是存在的，除去以下情况未知： 1 a = 1 并且口 1 4 ，1 5 ，2 1 ，2 2 ，2 8 ，3 5 ，3 6 ，4 2 ，7 0 ，8 4 ，8 5 ，9 8 ，9 9 ，1 0 6 ，1 2 6 ，1 4 0 ， 1 4 1 ，1 4 7 ，1 4 8 ，1 5 4 ，1 5 5 ，1 6 8 ，1 8 2 ，1 8 3 ，1 9 6 ，2 3 8 ，2 4 5 ，2 5 2 ，2 5 3 ，2 7 3 ，2 9 4 。 2 a 2 ，3 ，5 ，9 ) 并且 = 4 2 3 ，a = 7 并且= 1 8 定理1 2 6 9 1 1 当= 3 ，4 ) 或k = 3 ，5 ) 时，r t - i - e # 甬- v 3 均存在一个2 一完 美( 口，k ，1 ) - m d ，但除去t 【6 ，8 ) 时存在性未知 2 北京交通大学硕士学位论文1 绪论 2 当k = 3 ，4 ，7 ) 或k = 3 ，5 ，7 时，对于所有t j 3 均存在一个2 一完 美( 弘k1 ) m d ，但除去 一6 时存在性未知 定理1 2 7 9 1 对于所有整数t ，4 均存在一个3 完美( ”， 4 ，5 ) ，1 ) - m d ，但除去t ， 6 ，7 ，8 ，1 0 ，1 4 ，1 5 ，1 8 ，1 9 ，2 2 ，2 3 ，2 7 ) 时存在性未知 定理1 2 8 | 9 】对于所有整数口4 均存在一个3 一完美( 钉， 4 ，6 ) ，1 ) - m d ，但除去t ， 6 ，8 ，1 0 ，1 l ，1 4 ，1 5 ，1 8 ) 时存在性未知 定理1 2 9 1 9 1 对于所有整数 4 均存在一个3 一完美( u ， 4 ，7 ) ，1 ) - m d ，但除去 6 ，1 0 ，1 1 ，1 4 ，1 5 ，1 8 ，1 9 ) 时存在性未知 定理1 2 1 0 【9 】对于所有整数t ，5 均存在一个4 一完美( t ， 5 ，6 ，1 ) - m d ，但除 去t ， 6 ，8 ，9 ，i 0 ，1 2 ，1 4 ，1 5 ，1 4 ，1 5 ，1 7 ，1 8 ，2 0 ，2 2 ，2 3 ，2 4 ，2 7 2 9 ，3 3 ，4 8 ，5 2 ，5 4 ，6 2 ，6 4 , 6 9 ，7 2 ，7 4 ，8 2 ，9 2 ，1 0 8 ，1 1 8 ，1 2 2 ，1 2 4 ，1 3 2 ，1 3 4 ) 时存在性未知 1 3 辅助设计与构造方法 在这一节中，我们将定义一些术语以及一些在随后的构造中所需要的辅助设 计如果想要了解这些组合构型更多的信息，可以参考【1 2 】 令d k 。，。廿。表示一个点集为x = u 1 i k 的完全多部有向图，其中置( 1 h ) 两两互不相交，i 五f = m ，t ，= l 硌 啦z 和可是属于不同集合五和玛 中的两个点，使得恰好有一条从。到可的弧同时有一条从管到z 的弧 一个区组长为惫的带洞的完美m e n d e l s o h n 设计( h p m d ) 是一个有序对( 置棚， 其中4 是由被称为区组的有向七圈所组成的集合( 有向k 圈即后长的有向圈) ，其构成 了一个弧不相交的有向多部图的分解此分解满足这样的性质：对于任意的r ( 1 r o 均存在，除下列t 的取值时存在性未知：2 ，3 ， 4 ，5 ，7 ，1 1 ，1 2 ，1 5 ，2 0 ，2 1 ，2 2 ，2 4 ，2 7 ，3 1 ，3 2 ，3 哇，3 7 ，3 8 ，加，4 2 ，4 3 ，4 5 ， 4 7 ，5 0 ，5 2 ，5 3 ，5 6 ，6 0 ，6 1 ，6 2 ，6 7 ，6 8 ，7 5 ，7 6 ，8 4 ，9 2 ，9 4 ，9 6 ，1 0 2 ，1 3 2 ，1 7 4 ， 1 9 1 ，1 9 4 ，1 9 6 ，2 0 1 ，2 0 4 ，2 0 9 2 ( 7 2 t + 9 ，9 ，1 ) b i b d , 对于t o 均存在，除下列t 的取值时存在性未知：2 ，3 ， 4 ，5 ，1 2 ，1 3 ，1 4 ，1 8 ，2 0 ，2 2 ，2 3 ，2 5 ，2 6 ，2 7 ，2 8 ，3 1 ，3 3 ，3 4 ，3 8 ，4 0 ，4 l ，4 3 ， 4 6 ，4 7 ，4 8 ，5 2 ，5 9 ，6 0 ，6 1 ，6 2 ，6 7 ，6 8 ，7 6 ，8 5 ，9 3 ，9 4 ，1 0 2 ，1 0 3 ，1 4 8 ，1 7 4 ，1 8 3 ， 1 9 2 ，2 0 2 ，2 0 3 ，2 0 9 ，2 2 9 ， 为了在后面使用方便我们定义f 为：，= 扣：扣，9 ，1 ) 一b i b d 存在 可分组设计( g r o u pd i v i s i b l ed e s i g n 简写做g d d ) 是一个三元组( x ，g ，8 ) ，并且 满足下面的三个条件： lx 为点集，g 是x 的一个划分称之为组 2 召是由y 上若干缸子集( 称之为区组) 所组成的集合，其中七1 3 不同组中的任意点对均出现在唯一的一个区组中 横截设计( t r a n s v e r s a ld e s i g n 简写做t d ) ：一个t d ( k ，珏) 是一个组形为妒并且 区组长度为的g d d 定理1 3 3 f 4 】对于m 7 均存在一个t d ( 8 ，m ) 除以下情况未知? m ( 1 0 ，1 2 ，1 4 ，1 5 ，1 8 ，2 0 2 2 ，2 4 ，2 6 ，2 8 ，3 0 ，3 3 3 6 ，3 8 ，3 9 ，4 2 ，4 4 ，4 6 ，4 8 ，5 1 ， 5 2 ，5 4 ，5 5 ，5 8 ，6 0 ，6 2 ，6 6 ，鹋，7 4 , 7 5 ) 为了得到我们的主要结果。我们将运用如下的直接构造和递归构造方法 对于直接构造我们在后面用到的有如下的几个定理： 构造1 3 4 【7 】”= 矿是任意詹 2 的素数幂，如果k l ( v - 1 ) ，则存在一个( u ，七，1 ) 一p m d 构造1 3 5 【7 】t ，= 矿是任意的素数幂，如果，是廿一1 与k 的最大公因子，则存在一 个( u ，k ，k f ) 一p m d 4 北京交通大学硕士学位论文1 绪论 构造1 3 6 吲如果q 是一个形如q = k n + l 素数幂，则存在一个q + 1 ，k ，七) 一p m d 递归构造的方法有很多种，如填洞法和权重法等，在本文中主要讨论的是利 用填洞法来进行递归构造填洞法虽然简单，但却是非常常用而且很有效的办法 h p m d 和i p m d 的一个重要的作用就是可以将他们的洞填上，从而得到一个p m d 构造1 3 7 【7 】如果同时存在一个扣，仃，k ，1 ) 一i p m d 以及今( n ，k ，1 ) p m d ，则存在 一个( t ，k ，1 ) 一p m d 构造1 3 8 如果存在一个k - i p m d ( v ，九) 以及一个r - 完美( ，l ， 七，t ) ，1 ) 一m d 则存在一 个r - 完美( 弘 七，母，1 ) 一m d 构造1 3 9 f 7 】如果存在一个( t ，k ，1 ) p 曰d 以及对于所有的t k 都有0 ，k ，1 ) 一p m d 存在，则存在一个( t j ，k ，1 ) p m d 构造1 3 1 0 吲如果存在一个( t ，k ，a ) - p m d ，一个( u ，k ，a ) 一p m d 与个t d ( k ，“) ，则 存在一个( t ，t ，奄，a ) p m d 构造1 3 1 1 吲如果存在一个( t j ，k ，a 1 ) p m d 与一个( 奶k ，x 2 ) - p m d 则存在一个 扣，蠢，m 天1 + h a 2 ) - p m d m ，n 皆为非负整数) 5 2 2 - 完美( u ， 3 ，七) ，a ) 一m d 在这一章中，我们研究当k 为 3 k ) 时参完美( t 7 ， 3 ，耐，a ) 一m d 时的存在性的结 果的一些拓展当是取自不同的值是由不同的章节进行叙述。 2 1 k = 3 ，4 ) 根据定理1 2 6 ，对于所有t ，3 均存在一个2 - 完美( t ， 3 ，4 ) ，1 ) 一m d ，除t ， 6 ， 8 ) 情况未知所以对于k = 3 ，4 ) 的讨论，主要是确定t ， 6 ，8 ) 时2 - 完美( 口，t 3 ，4 ， 1 ) - m d 的存在性 引理2 1 1 令( 五日) 为一个2 一完美( 口， 3 ，4 ) ，1 ) - m d ，( o ，与( 6 ，口) 为x 中任意有序 对，则( 口，6 ) 与( 6 ，口) 罄同时以i 一闯隔的形式出现在相同长度的区组中，其中i 1 ，2 ) 证明：设( 口，6 c ) 为8 中任一3 长区组，则由此区组可以得到3 个1 一间隔的有序对： n 6 ，6 c ，以及3 个譬间隔的有序对，b a ，c b 假设有序对( 6 ，8 ) 以1 - 何隔的形式 出现在4 长的区组中，则( 口，矗) 无法以2 - 间隔的形式出现因为若( 口，妨以2 - 间隔出现 在3 长的区组中，则有序对( 6 ，n ) 将以1 间隔的形式出现2 次而如果( n ，b ) 以2 - 间隔的 形式出现在4 长区组中，则( 6 ，口) 将以参问隔的形式出现2 次此两种情况均与定义矛 盾，故( n ，与( 6 ，a ) 以1 一间隔的形式出现3 长区组中或4 长区组由于( 口，6 ) 与( 6 ，n ) 必 以1 间隔的形式出现3 长区组中，易得( 6 ，口) 与( o ，b ) 以2 - 问隔的形式出现3 长区组中 结论得证口 下面总假设衄代表长度为i 的区组个数 上面的引理是下面关于2 - 完美( 6 ， 3 ，4 ，1 ) m d 以及2 - 完美( 8 ， 3 ，4 ) ，1 ) 一m d 不 存在性证明的基础根据此引理可以得到这样的结论，6 3 2 r b 4 3 ，或者6 3 b 4 = o 这个结论的得到，是基于任意3 长或者4 长区组中所涉及的点组成的所有有序对 均以矗间隔的形式出现在区组中，其中i 1 ，2 引理2 1 2 2 - 完美( 6 ， 3 ，4 ) ，1 ) - m d - 不存在 证明：令( x ，b ) 为一2 完美( 6 ， 3 ，4 ) ，1 ) - m d ，通过计算召中区组所产生1 一间隔有 序对的个数( 2 - f 司隔的情况与1 一间隔相同) ，易得如下结论： 3 5 3 - t - 4 b 4 = 扣一1 ) 因此易知，对于t ，= 6 时共有三种情况存在，下面分别对这三种情况进行讨论： 情况一：5 3 = 2 ，k = 6 、 不妨设( n ，b ，c ) 为召中任意3 长区组，由引理2 1 1 以及6 3 = 2 ，不难得出( 6 ，a ，c ) 为 另一3 长区组，且n ，b ，c3 个点中任意2 个点不同时出现在任意4 长区组中而根据 定义知n ，b ，c 必分别与x 中另) b 3 个点以1 间隔的形式在区组中出现因此4 长的区 组个数至少为9 ，而b 4 = 6 o 时，均存在一个2 完：美( t ， 3 ，q ，a ) - m d ， 除 6 ，8 ) 且a = 1 时2 完美( t ， 3 ，4 ，1 ) m d 不存在 2 2 k = 3 ，5 同上一节对二完美( t ， 3 ，4 ) ，1 ) 一m d 的讨论一样，根据定理1 2 6 ，对于所有t ， 3 均存在一个善完美( 口， 3 ，5 ，1 ) 一m d ，除口 6 ，8 ) 不确定所以对于k = 3 ，5 ) 的 讨论，主要是确定 6 ，8 时参完美扣， 3 ，讣，1 ) m d 存在性 引理2 2 1 令( x ，8 ) 为一个2 一完美( t ， 3 ，h ，1 ) - m d ，其中七 4 ，5 ，6 ，订令( n ，6 ) 与( 6 ，n ) 为x 中任意有序对，则( 8 ，6 ) 以1 间隔的形式与( b ，8 ) 以2 间隔的形式盛出觋雇 相同长度的区组中 证明：设( a 0 ，0 1 ，0 2 ) 为任一3 长区组，则瓴，吩) 以1 - 间隔的形式与( 吩，啦) 以2 间隔 的形式出现在同一区组中，即相同长度的区组中，其中0 i ，j 2 ，i 歹因此，任 意有序对( n ，6 ) 以1 一间隔的形式出现在七长区组中时，其中后 4 ，5 ，6 ，7 则( 6 ，凸) 必 以2 - 闻隔的形式出现在相同长度的区组中若( 6 ，8 ) 不出现在相同长的区组中则必出 现在3 长区组中，导致( o ，6 ) 在区组中出现两次出现矛盾结论得证 口 引理2 2 2 令( x ，8 ) 为一个2 一完美( t ， 3 ，5 ) ，1 ) - m d ，则魄4 或6 3 6 5 = o ， 证明：当6 3 k = 0 时，显然成立下面考虑一下6 3 6 5 0 的情况设( 蛳，口l ，d 2 ，a 3 ， n 4 ) 为任一5 长区组，根据引理2 2 1 不妨设( 8 2 ，a o ，z ，可，z ) 为另一5 长区组因为讨论 的是6 5 的下界，所以取 z ，弘2 ) = m ，a a ，n 4 ，于是可以得到z = 口3 ，暑= 0 1 以 及z = a 4 对于区组，a o ，a s ，口l ，a 4 ) ，同样根据引理2 2 1 ，至少还需要一个5 长 区组来保证在区组( 砚，8 3 ，口l ，硒) 中以2 - 问隔出现的有序对( 口2 ，如) ，( 的，勋) 以1 一 间隔的形式出现在区组中因此，得到了第三个区组( 啦，啦，口l ，a o ，a 4 ) 同理，可 得( 1 ，a 3 ，a o ，o , 2 ，a 4 ) 是第四个区组所以在此情况下，5 长的区组至少是4 个，6 5 4 8 结论得证 口 引理2 2 3 2 一完美( 6 ， 3 ，5 ，1 ) - m d ；b 存在 证明：令( x ，聊为一个2 - 完美( 6 ，t 3 ，5 ) ，1 ) - m d ，通过计算b 中区组所产生1 一间隔 有序对的个数，易得如下结论： 3 6 3 + 4 6 5 = t ，p 1 ) 其中，醣4 或者b 6 5 = 0 因此，对于口= 6 共有两种情况，下面分别对这两种情 况进行讨论： 情况一：6 3 = o ，, 5 = 6 此情况下，二完美( 6 ， 3 ，5 ，1 ) 一m d 显然是一个( 6 ，5 ，1 ) - p m d 由定理1 2 3 可知 ( 6 ，5 ，1 ) 一p m d 不存在 情况二：6 3 = 1 0 ，6 5 0 此情况下，参完美( 6 ， 3 ，5 ) ，1 ) m d r 然是一个( 6 ，3 ，1 ) 一p m d 由定理1 2 1 a - i 知 ( 6 ，3 ，1 ) - p m d 不存在 综上两种情况，二完美( 6 ， 3 ，5 ) ，1 ) 一m d 不存在 口 引理2 2 4 2 - 完美( 8 ， 3 ，5 ，1 ) 一m d 不存在 i 正n r ：令( x ，功为一个二完美( 8 ， 3 ，5 ，1 ) 一m d ，通过计算艿中区组所产生1 - 间隔 有序对的个数，易得： 3 6 3 + 5 6 5 ；移扣一1 ) 其中，坛4 或者6 3 6 5 ；0 因此，对于口= 6 共有三种情况，下面分别对这三种情 况进行讨论： 情况一：如= 2 ，6 5 = 1 0 情况二：6 3 = 7 b s = 7 对上两种情况，结合引理2 2 1 利用计算机穷尽了所有情况后，发现其不存在， 情况三：6 3 = 1 2 ，b 5 = 4 由于6 5 = 4 以及引理2 2 2 ，此4 个5 长区组刚好构成一个( 5 ，5 ，1 ) 一p m d 则此5 个 点不再同时出现在3 长区组中，而根据定义此5 个点与另外3 个点以1 间隔的形式出 现在区组中故6 3 1 5 ，此与b a = 1 2 矛盾 综合上述三种情况，参完美( 8 ， 3 ，5 ) ，1 ) 一m d 不存在 口 下面讨论2 - 完美( t ， 3 ，5 ) ，2 ) 一m d ，根据定理1 2 6 ，对于所有t ，3 均存在一 个2 - 完美( t ， 3 ，5 ，1 ) - m d ，除秽 6 ，8 ) 由于对于己存在的2 - 完美( 口， 3 ，5 ，1 ) 一 m d ，只需将所有区组复制一遍，就可以得到一个二完美( t ， 3 ，5 ) ，2 ) 一m d 而由定 9 理1 2 3 知( 6 ，5 ，2 ) p m d 存在，所以二完美扣， 3 ，5 ) ，2 ) m d 对于所有t ，3 均存在， 除 = 8 不确定 二完美( 口， 3 ，5 ，3 ) m d 的情况与2 - 完美( 射， 3 ，5 ) ，2 ) m d 类似，也是只需将已 存在的器完美扣， 3 ，5 ) ，1 ) m d 中所有的区组复制三次，就可以得到一个参完美( 弘 3 ，5 ，3 ) m d 而由定理1 2 3 知( 6 ，5 ，3 ) 一p m d 与定理1 2 1 知( 8 ，3 ，3 ) p m d 存在，所 以二完美( t ， 3 ，5 ) ，3 ) 一m d 对于所有t ，3 均存在， 同样利用构造1 3 1 l 可以构造其他阶a 2 的参完美( t ，f 3 ，5 ) ，a ) m d 综上所 述： 定理2 25 当k = 3 ，5 ，。3 且a o 均存在一个2 一完美( 移， 3 ，5 ，a ) - m d 除 去以下情况： ( 1 ) 当a = = 1 ，t ， 6 ，8 时，( t ， 3 ，5 ) ，1 ) 一m d 不, i q - 在 ( 2 ) 当a 1 ，t ，= 8 j i - a 三l ，2 ( m o d3 ) 时，2 一完美( 8 ， 3 ，5 ) ，a ) - m d 存在性未知 2 3 k = 3 ，6 ) 引理2 3 1 对于所有口3 且t ，兰0 ，1 ( r o o d3 ) 均存在- - & 2 完美( 钉， 3 ，6 ) ，1 ) m d ， 除v = 6 时不确定 证明：根据定理1 2 1 ，可以得到t ，3 r v 三0 ，l ( r o o d3 ) 时均存在一个禾完 美( 口， 3 ，6 ，1 ) - m d ，除f = 6 时不确定，对于口三2 ( m o d3 ) 的情况，通过计算召中 区组所产生1 一间隔有序对的个数。易得： 3 6 3 + 6 = v ( v 一1 ) ( 2 3 1 ) 其中，6 b 代表3 长区组的个数，6 6 代表6 长区组的个数由于t ，i2 ( r o o d3 ) ， 故v ( v 一1 ) 三2 ( m o d3 ) ，而公式2 3 1 的左侧可以被3 整除故t ，兰2 ( r o o d3 ) 时，公 式( 2 3 1 ) 无解因此， 兰2 ( r o o d3 ) 时，2 - 完美( t ， 3 ，6 ) ，1 ) - m d 不存在结论得 证口 引理2 3 2 2 - 完美( 6 ， 3 ，6 ) ，1 ) m d 不存在 证明：令( x ，8 ) 为一个2 l 完美( 6 ， 3 ，6 ) ，1 ) m d ，通过计算b 中区组所产生1 间隔 有序对的个数，易得如下结论： 3 6 3 + 6 6 b = 秽扣一1 ) 当b = 1 0 r b 6 = o 时，也就是说当2 - 完美( 6 ， 3 ，6 ) ，1 ) - m d 是一个( 6 ，3 ，1 ) 一 p m d 时，由定理1 2 1 知，( 6 ，3 ，1 ) - p m d 不存在因此k 0 设( 知，口l ，o 2 ，0 , 3 ，a 4 ，a 5 ) 为 任意6 长区组，由引理2 2 i ，必有这样一个区组：( a 2 ，a o ，m ，a ，啦) ，其中托歹，k ，日= 1 0 1 ，3 ，4 ，5 ，经过计算，当遍历了所有可能以后得到这样的结论：形为( n 2 ，a e ，啦，吩， 鲰，n 1 ) 的区组不可能存在故二完美( 6 ， 3 ，6 ，1 ) 一m d 不存在 口 下面讨论2 - 完美( 口，f 3 ，6 ，2 ) - m d ，由引理2 3 1 和引理2 3 2 ，对于所有的t ，暑0 ，1 ( r o o d3 ) 且t ，3 ，均存在一个2 完美( t ， 3 ，6 ) ，1 ) 一m d ，除移= 6 时不存在由于对于 已存在的筘完美( ”， 3 ，6 ，1 ) 。m d ，只需将所有区组复制一遍，就可以得到一个2 - 完 美( t ， 3 ，6 ，2 ) - m d 而对于口三2 ( r o o d3 ) ，2 - 完美( 口， 3 ，6 ) ，2 ) 一m d 同样不存在，其 证明过程与引理2 3 1 类似根据定理1 2 1 我们知道存在( 6 ，3 ，2 ) - p m d 因此，对于 所有的t ，三0 ，1 ( m o d3 ) k v 3 ，均存在一个暑完美( 3 ，6 ，2 ) m d 对于t ，兰2 ( m o d3 ) 且当天兰0 ( r o o d3 ) 时由上面的证明和定理1 2 1 知，2 - 完 美( 3 ，6 ，a ) 一m d 存在，但a 兰1 ，2 ( r o o d 3 ) 时2 一完美( t ， 3 ，6 ) ，a ) 一m d 均不存在对 于t ，兰0 ，1 ( r o o d3 ) ，利用构造1 3 1 l 及文【7 】可知a l 的2 - 完美( 3 ，6 ) ，a ) 一m d 均 存在 定理2 3 3 当k = 3 ，6 ) ，t ，3 且a o 均存在- - + 2 一完美( 弘 3 ，6 ) ，a ) - m d 除 去以下抟况： ( 1 ) 当t ，= 6 且a = 1 时，2 - 完美( t ，t 3 ，6 ，1 ) 一m d 不存在 ( 2 ) 对于t ，三2 ( m o d3 ) 且a 兰1 ，2 ( m o d3 ) 时2 一完美( q 3 ，6 ，a ) 一m d 均不存在 2 4 k = 3 ，7 本节主要讨论当k = 3 ，7 时，譬完美( t ， 3 ，7 ，1 ) - m d 得存在性 引理2 4 1 当 5 ，6 ) 不存在2 - 完美( t ， 3 ，7 ) ，1 ) - m d 证明：我们不失一般性地任取( 0 ，m ，a 2 ，a 3 ，a 4 ，0 5 ，n 6 ) 为任意一个7 长区组，根据 引理2 2 1 ，我们不妨设另一个是( n 2 ，a o ，毛y ，z ，m ，p ) ，为了找出6 7 得下界，我们取伽，y ， z ，m ，p 为 8 1 ，0 , 3 ，0 , 4 ，( z 5 ，铂 ，然后继续利用引理2 2 1 ，我们可以得到如下5 个新的区 组：( a o ，a 2 ，a 4 ，a 6 ，a 1 ，a 3 ，a s ) ，( a o ，a 3 ，n 6 ，a 2 ，a 5 ，a 1 ，a 4 ) ，( a o ，a 4 ，n 1 ，a 5 ，o , 2 ，n 6 ，a 3 ) ， ( a o ，0 5 ，n 3 ，o l ，a 6 ，0 , 4 ，n 2 ) ，( a o ，a 6 ，奶，6 4 ，n 3 ，2 ，0 1 ) 且此6 个区组是可以相互推出的，所 以6 为最少的区组数故厶7 6 对于t ， 5 ，6 时得2 - 完美( 口， 3 ，7 ) ，1 ) 一m d 计算其 可能7 长区组数，即知其不存在 口 定理2 4 2 对于所有口均存在一个2 一完美( 口， 3 ，7 ，1 ) - m d ，除钉 5 ，6 时不存在， 以及” 1 1 1 4 时不确定 证明：由定理1 2 1 ，可以得到t ，三0 ，1 ( m o d3 ) 时均存在一个( ”，3 ，i ) - p m d ，除t ，= 6 时不存在根据定理1 3 1 ，知道对于所有t ，1 7 且t ，差2 ( r o o d3 ) 均存在一个孓 i p m d ( v ，8 ) 应用构造1 3 7 ，可以用( 8 ，7 ，1 ) 一p m d ( t 扫定理i 2 5 可知其存在) 填此8 长的洞从而得到想要的结果对于所有 1 7 且t ，兰2 ( r o o d3 ) 对于t ， 5 ，6 ，由 引理2 4 1 知其不存在教结论得证 口 当a 1 时候，文【2 】【7 】结合构造1 3 1 1 ，可知对于t ，3 r v 簪 5 ，6 ，1 1 ，1 4 时暑 完美似 3 ，7 ，a ) - m d 均存在当钉t 5 ，1 1 的时候，天 1 且a 三0 ( m o d3 ) 时候二 完美( t ， 3 ，7 ) ，a ) 一m d 存在当 6 ，1 4 时对于所有a 2 ，2 - 完美( 6 ， 3 ，7 ) ，a ) 一 m d 存在 定理2 4 3 当k = 3 ，7 ) ，列 i - v 3 耳- a o 均存在一个2 一完美( 3 ，n ，a ) - m d ， 除去以下情况： ( 1 ) 当a = 1 时j i 当t ， 5 ，6 ) 时2 一完美( 3 ，7 ，i ) - m d 并；存在 纯当 1 1 ，1 4 ) 时2 ，完美( t ， 3 ，7 ) ，x ) - m d 在性未知 ( 2 ) 但当t ， 5 ，1 1 的时候，a 1 且a 兰l ，2 ( r o o d3 ) 时2 一完美( t ， 3 ，7 ) ，a ) 一m d 存 在性未知 2 5 本章主要结论 本章主要探讨了二完美( t ， 3 ，耐，a ) - m d ，其中磨 4 ，5 ，6 ，7 ) 完全解决了 当k = 3 ，4 以及k = 3 ，6 ) 剩余的所有阶数，部分解决了k = 3 ，5 ) 并且对 新找出的x = 3 ，7 解决其部分阶数 另外对于二完美( 6 ， 3 ，4 ，7 ) ，1 ) 一m d 与2 完美( 6 ， 3 ，5 ，锯，1 ) 一m d 严格按照定义 编写计算机程序进行遍历后，其均不存在 3 3 - 完美( u ， o 均存在一个3 一完美( 口， 4 ，5 ，x ) - m d ，除了一 下情况： ( 1 ) 当a = 1 时，移 6 ，7 ，8 ，1 0 ) 不存在，以及 l a ，1 5 ，1 8 ，1 9 ，2 2 ，2 3 ，2 7 ) 不确定 ( 2 ) 当a 1 时， 7 ，1 4 ，1 8 ，1 9 ，2 2 ，2 3 ，2 7 时且 兰0 ( r o o d4 ) 或a 兰0 ( r o o d5 ) 时 存在。其他情况未知 3 2 k = 4 ，6 ) 根据定理1 2 8 ，对于所有口4 均存在一个3 _ 完美( t j ， 4 ，6 ) ，1 ) 一m d ，除了t ， 6 ，7 ，l o ，i i ，1 4 ，1 5 ，1 8 不确定。所以对于k = 4 ，6 的讨论，主要是确定咎 6 ，7 ， 1 0 ，1 1 ，1 4 ，1 5 ，i s 时3 _ 完美( t ， 4 ，6 ) ，1 ) 一p m d 存在性 引理3 2 1 令( x ，b ) 为一3 一完美( 静， 4 ，6 ，1 ) - m d ，( o ，6 ) 与慨口) 为x 中任意有序对， 则( 8 6 ) 与( 6 ，o ) 必同时e a i 一间隔的形式出现在相同长度的区组中，其中 = 1 ，2 ，3 证明：设( a o ，口l ，砚，f i t 3 ) 为任意4 长区组，对于1 间隔以及3 - 间隔的证明过程与引 理3 1 ，1 类似，不再重复两对于2 间隔，有序对( a o ，勖)