不同指數(shù)的區(qū)組長為5的1-BSEC的存在性

黃晨悅， 劉秉瀚

(1. 交通銀行福建省分行, 福建 福州 350003; 2. 福州大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院, 福建 福州 350108)

0 引言

平衡樣本設(shè)計的存在性問題引起了許多數(shù)學(xué)家的關(guān)注. 它是抽取樣本調(diào)查的某種方案設(shè)計, 此抽樣方案在具有相同或者類似特征的相鄰樣本時會得到誤差十分大的結(jié)果， Hedayat等[1]提出不含鄰點的平衡樣本設(shè)計(BSEC) 來避免抽取相鄰的樣本， 在BSEC中任意兩個相鄰點都不會被同時選取， 所以相鄰樣本造成的誤差也就不存在了.

近幾年來, BSEC的研究已經(jīng)有了一系列的重要進展. Colbourn等[2]證明了1-BSEC(v, 3,λ) 的存在性. Colbourn等[3]證明了1-BSEC(v, 4,λ)的存在性. 李萌[4]基本解決了指數(shù)為4時1-BSEC(v, 5,λ)的存在性, 除了可能的例外v=213.

本研究主要介紹如何利用其它設(shè)計來構(gòu)造 1-BSEC(v,k,λ), 并利用所得到的遞歸構(gòu)造方法完全證明了指數(shù)為4時1-BSEC(v, 5,λ)的存在性, 并在指數(shù)為2, 5, 10時也得到了部分1-BSEC(v, 5,λ)的存在性.

1 相關(guān)已知結(jié)果和設(shè)計

設(shè)一個集合X={0, 1, …,v-1},X里的每個元都稱作點， 當(dāng)X上的一個圓排列C(X)=(x0,x1, …,xv-1)時, 把x0和xv-1,xi和xi+1(0≤i≤v-2)都稱作是相鄰點.

定義1[5]設(shè)一個集合X一共有v個元素且構(gòu)成了圓排列C(X),B是由該集合的一些k子集所得到的集簇, 那么B里的元就叫區(qū)組. 把(X,B)稱為一維不含鄰點的區(qū)組長為k的平衡樣本設(shè)計當(dāng)子(X,B)滿足以下兩個條件:

1) 集合X內(nèi)B的任意區(qū)組內(nèi)不出現(xiàn)任何兩個相鄰的點.

2) 集合X內(nèi)B的λ個區(qū)組內(nèi)都恰好出現(xiàn)任何兩個不相鄰的點.

此樣本設(shè)計簡記為1-BSEC(v,k,λ).

引理1[4]當(dāng)(X,B)是一個1-BSEC(v,k,λ)時, 則滿足以下兩個條件：

引理2若一個1-BSEC(v,k,λ)存在, 則須滿足:

1)λv(v-3)≡0(modk(k-1)).

2)λ(v-3)≡0(mod(k-1)) .

定義 2[6]記M,K為正整數(shù)集合, 且G為一個有限集合X上的分拆, 該有限集合X的某些子集構(gòu)成了集簇B, 則把三元組(X,G,B)稱為一個可分組設(shè)計GDD, 并且記作GDD[K,λ,M;v]. 當(dāng)滿足以下條件:

1) ?G∈G,G∈M,G里的元稱為組.

2)X=v，X里的每個元都稱作點.

3) ?B∈B， ?G∈G且B∈K，G∩B≤1,B里的元素稱作區(qū)組.

4) 集合X內(nèi)B的λ個區(qū)組里都恰有任意一對不在同一個組中的點出現(xiàn).

定理 1[7-9]

1) 記X={6, 10, 12}, 只要n≥5 且n?H， 就存在TD(6,n).

2) 記X={10, 14, 15, 20, 22, 26, 30, 34, 38, 46}, 只要n?H且n≥7, 就存在TD(7,n).

3) 當(dāng)n為素數(shù)冪并且n≥9, 就存在TD(9,n).

定理 2[7]

1)記λ≥2， 型為mn的(5,λ)-GDD存在當(dāng)且僅當(dāng):n≥5,λ(mn-m)≡0(mod 4),λmn(mn-m)≡0(mod 20)， 除了λ=2,n=15且m=9 或 (m, 15)=1這些可能例外.

2)B(5,λ;v)存在的充分必要條件是v≥5,λ(v-1)≡0(mod 4)且λv(v-1)≡0(mod 20), 除了B(5, 2; 15)這例外情況以外.

推論1如果v≡1(mod 4) 且v≥5, 就存在型為2v的(5, 5)-GDD和B(5, 5;v) .

定義3[8]設(shè)Y是X的一個子集且G是集合X上的分拆, 集合X一共有v個元素. 該有限集合X的某些子集構(gòu)成了集簇B, 把四元組(X,Y,G,B) 稱為一個不完全可分組設(shè)計(IGDD)當(dāng)滿足以下條件:

1) ?B∈B， ?G∈G，G∩B≤1,G中的元稱作組且B中的元稱為區(qū)組.

2) 任何區(qū)組里都不出現(xiàn)Y中的任意兩個點.

3) 任何一對不都屬于Y且不在同一個組里的點剛好在B的λ個區(qū)組里出現(xiàn).

當(dāng)不完全可分組設(shè)計有ui個vi長組, 每個vi長組與洞Y有Hi個相交的點i=1, 2, …,s, 且它的每個區(qū)組長都屬于K, 那么這個不完全可分組設(shè)計記作型為(v1,H1)u1, (v2,H2)u2， …， (vs,Hs)us的(k,λ)-IGDD. 當(dāng)K={k}時, 簡記K為k. 可以看出, 每個IGDD都為缺少一個 GDD作子設(shè)計的可分組設(shè)計. 如果洞Y是空集, 此(k,λ)-IGDD就為 (k,λ)-GDD. 如果λ=1, 則記為K-IGDD.

型如(v,h)k的(k,λ)-IGDD稱作不完全橫截設(shè)計, 并被記作ITDλ(k,v;h). 當(dāng)λ=1時就記為ITD(k,v;h).

2 1-BSEC(v, k, λ) 的遞歸構(gòu)造和結(jié)論

給出1-BSEC 的直接構(gòu)造和遞歸構(gòu)造, 利用所得到的遞歸構(gòu)造方法完全證明了1-BSEC(v, 5, 4) 存在的充分必要條件, 并在指數(shù)為2, 5時給出了1-BSEC(v, 5, λ)的構(gòu)造方法和幾個無窮類的存在性, 在指數(shù)為10時給出了使得1-BSEC(v, 5,λ) 存在的充分必要條件所差的階數(shù).

定理31) 存在1-BSEC(143, 5, 1).

證明 其基區(qū)組為:

{0, 9, 48, 62, 103} {0, 21, 32, 38, 110} {0, 16, 52, 83, 96} {0, 23, 93, 108, 136}

{0, 4, 24, 29, 121} {0, 2, 12, 68, 86} {0, 3, 37, 45, 64}

由文[10]知:

2) 當(dāng)v∈{19, 27, 31, 35, 39, 47, 51, 55, 59, 67, 71, 75, 79, 87, 91, 99}時, 存在1-BSEC(v, 5, 5).

3) 當(dāng)v∈{17, 21, 29, 37, 41, 49, 57, 61, 69, 77, 81, 89, 97, 101} 時, 存在1-BSEC(v, 5, 10).

定理5記m≥7,m?{10, 22}, 2≤x≤2m且x是一個整數(shù). 如果1-BSEC(2m, 5, 4)和1-BSEC(x, 5, 4)都存在, 那么1-BSEC(10m+x, 5, 4)也一定存在 .

證明 首先在Z10∪{∞}作一個型為2511的(5, 4)-GDD, 然后以{0, 5}, {1, 6}, {2, 7}, {3, 8}, {4, 9} 和{∞} 當(dāng)作組, 兩個基區(qū)組分別為{0, 2, 3, 9, ∞} 與 {0, 2, 3, 4, 6}, 區(qū)組則以基區(qū)組+1(mod 10)生成.

定理61-BSEC(v, 5, 4) 存在的充分必要條件是v≡0, 3(mod 5) 且v≥18.

證明 當(dāng)m=19,x=23時, 由文[4]可知， 1-BSEC(v, 5, 4)存在的必要條件為v≥15且v≡0, 3(mod 5)也是充分的， 除了v=213這個不確定的例外點, 那么可得1-BSEC(38, 5, 4)和1-BSEC(23, 5, 4)是存在的. 又根據(jù)定理5, 取 2m=38,x=23即可證明存在1-BSEC(213, 5, 4) 這個不確定的例外情況, 所以也就證明了該定理.

定理7v≡1, 5(mod 10),v≥5且v≠15時, 如果存在ITD(5,m; 2)和1-BSEC(m, 5, 2), 則1-BSEC(mv, 5, 2)存在.

證明 1) 當(dāng)v≡1, 5(mod 10),v≥5且v≠15時, 由文[4]知, 存在B(5, 2;v), 對X中的所有點加權(quán)m, 如果存在ITD(5,m; 2), 那么我們在B中所有區(qū)組上構(gòu)造型是(m, 2)5的(5, 1)-IGDD, 就可得到型是(m, 2)v的(5, 2)-IGDD.

2) 對于洞, 由文[4]知型是25的(5, 2)-GDD存在.

3) 由定理4可證, 如果存在1-BSEC(m, 5, 2), 那么也存在1-BSEC(mv, 5, 2).

定理8當(dāng)v≡23, 115(mod 230)時， 存在1-BSEC(v, 5, 2).

證明 當(dāng)v≡23(mod 230)時, 設(shè)v=230t+23=23(10t+1), 其中t≥0. 由文[7]可知, 存在ITD(5, 23; 2). 且由文[4]可知, 存在1-BSEC(23, 5, 2), 根據(jù)定理7可得, 1-BSEC(23(10t+1), 5, 2)存在. 同理可證, 當(dāng)v≡115(mod 230)時, 1-BSEC(23(10t+5), 5, 2)也存在.

定理9當(dāng)m是素數(shù)冪,m≥9, 且x是一個整數(shù)并且滿足x∈[3m, 7m-4]4. 如果1-BSEC(3m, 5, 5) 和1-BSEC(x, 5, 5)都存在, 那么1-BSEC(24m+x, 5, 5)也一定存在.

證明 首先構(gòu)作型是3871的(5, 1)-GDD, 再根據(jù)文[11]可得 RGD[4, 1, 3; 24] 是存在的, 它有7個平行類, 設(shè)為Pi(1≤i≤7). 接著在每個平行類Pi中, 對任何區(qū)組里都加點∞i(1≤i≤7), 然后把 {∞1, ∞2, …, ∞7} 當(dāng)成是新的組, 就能構(gòu)造出型是3871的(5, 1)-GDD.

2) 對于洞, 由定理3可知， 1-BSEC(27, 5, 5) 存在.

3) 最后由定理4同理可證， 如果1-BSEC(3m, 5, 5) 和 1-BSEC(x, 5, 5)都存在, 那么也存在1-BSEC(24m+x, 5, 5).

定理10記H1=[19, 103]4,H2=[243, 275]4,H3=[351, 399]4,H4={123, 143, 459, 463, 467, 471, 475, 479, 483, 487, 491, 495, 499, 503, 507, 511, 515, 523}, 當(dāng)H=H1∪H2∪H3∪H4, 如果v∈H， 則存在1-BSEC(v, 5, 5) .

證明 1) 記A={20i+3:1≤i≤7}, 如果v∈A時, 由文[4]和定理3可知, 存在1-BSEC(v, 5, 1) . 因此通過重復(fù)區(qū)組就可以證明1-BSEC(v, 5, 5)的存在性.

2) 由定理 3可知, 1-BSEC(19, 5, 5)存在, 再由定理 4可得1-BSEC(95, 5, 5)也存在. 同理可證明H1中其余的點存在. 當(dāng)X=(H1A)∪{123, 143} 且v∈X時, 存在1-BSEC(v, 5, 5) .

3) 記m∈{9, 13, 17},x=[27, 115]4且x?{107, 111}, 根據(jù)定理9 和定理 3 分別取點對(m,x)， 滿足條件x∈[3m, 7m-4]4, 并且滿足1-BSEC(3m, 5, 5)和1-BSEC(x, 5, 5)都存在, 則可得1-BSEC(24m+x, 5, 5)也存在. 即 1-BSEC(v, 5, 5) 存在.

定理11當(dāng)v≡23(mod 92)時， 存在1-BSEC (v, 5, 5).

證明 1) 當(dāng)v≡1(mod 4)且v≥5時, 由文[7]可知存在B(5, 5;v)且對于洞存在型為25的(5, 5)-GDD. 那么同定理7構(gòu)造方法一樣即可證得， 如果存在 ITD(5,m; 2)和1-BSEC(m, 5, 5), 則1-BSEC(mv, 5, 5)也存在.

2) 當(dāng)v≡23(mod 92)時, 設(shè)v=92t+23=23(4t+1), 其中t≥0. 由文[7]可知存在ITD(5, 23; 5), 且由定理3可得1-BSEC(23, 5, 5) 存在, 則可得1-BSEC(23(4t+1), 5, 5) 存在, 即1-BSEC(v, 5, 5)存在.

定理12令H1={10i+1:i={11, 12, 13, 14, 15, 18, 19, 20, 28, 32, 33, 40, 46, 50, 52}}，

H2={10i+3:i={16, 17, 18, 19, 21, 22, 28, 39, 40}}，

H3={10i+7:i={10, 11, 12, 13, 14, 15, 16, 17, 19, 21, 25, 27, 31, 32, 33, 39, 45, 49, 52}}，

H4={10i+9:i={10, 12, 13, 14, 15, 16, 17, 18, 19, 21, 24, 26, 31, 33, 38, 48, 50, 51}}， 且令H=H1∪H2∪H3∪H4, 若對任意v∈H都存在1-BSEC(v, 5, 10), 則1-BSEC(v, 5, 10)存在的充分必要條件就是v≡1(mod 2)且v≥17.

證明 1) 由文[10]知, 當(dāng)m是大于等于7的奇數(shù)且m≠15,x∈[m+4, 5m]2. 如果存在1-BSEC(5m, 5, 10) 和1-BSEC(x, 5, 10), 則1-BSEC(30m+x, 5, 10)也存在. 記v=30m+x≡1(mod 2),x≡1(mod 2)且x是大等于17的奇數(shù)且x∈[m+4, 5m]2, 接著設(shè)m=2t+1, 則可推出v=60t+30+x和x∈[2t+5, 10t+5]2, 即vt+1=[62t+97, 70t+105]2,vt=[62t+35, 70t+35]2, 當(dāng)t≥8時, 70t+35≥62t+97, 此時前面的點已經(jīng)可以覆蓋住后面的點. 當(dāng)t=8 時,vt=[531, 595]2. 記A=[17, 529]2, 即若對任意v∈A都存在1-BSEC(v, 5, 10), 則對大等于529之后的所有v點都存在1-BSEC(v, 5, 10).

2) 記A1=[17, 105]2,A2={113, 115, 123, 125, 133, 143, 145, 153, 155},A3={10i+3:i={20, 25, 27, 32, 33, 34, 47, 49, 51}, 令A(yù)=A1∪A2∪A3. 由文[10]可知, 當(dāng)v∈A時存在1-BSEC(v, 5, 10), 且當(dāng)v≡5(mod 10) 且v≥25 時, 存在1-BSEC(v, 5, 10). 同條件1), 設(shè)m=2t+1,vt=[62t+35, 70t+35]2, 由條件1) 知m是大于等于7的奇數(shù)且m≠15, 則可知t≥3且t≠7. 算出3≤t≤8且t≠7時各vt的存在區(qū)間, 再結(jié)合定理10 已知存在1-BSEC(v, 5, 5)的小階數(shù)重復(fù)區(qū)組, 并利用文[10]的構(gòu)造方法取點對(m,x)滿足條件x∈[m+4, 5m]2且滿足1-BSEC(5m, 5, 10)和1-BSEC(x, 5, 10)都存在, 則1-BSEC(30m+x, 5, 10)存在. 令A(yù)=[17, 529]2,B=AH, 能得到當(dāng)v∈B時均存在1-BSEC(v, 5, 10). 則當(dāng)v∈H時若1-BSEC(v, 5, 10)也存在, 可得1-BSEC(v, 5, 10)存在的充分必要條件就為v≡1(mod 2)且v≥17.