黃晨悅， 劉秉瀚

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

0 引言

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

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

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

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

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

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

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

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

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

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

引理2若一個(gè)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為一個(gè)有限集合X上的分拆, 該有限集合X的某些子集構(gòu)成了集簇B, 則把三元組(X,G,B)稱為一個(gè)可分組設(shè)計(jì)GDD, 并且記作GDD[K,λ,M;v]. 當(dāng)滿足以下條件:

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

2)X=v，X里的每個(gè)元都稱作點(diǎn).

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

4) 集合X內(nèi)B的λ個(gè)區(qū)組里都恰有任意一對不在同一個(gè)組中的點(diǎn)出現(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為素?cái)?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è)子集且G是集合X上的分拆, 集合X一共有v個(gè)元素. 該有限集合X的某些子集構(gòu)成了集簇B, 把四元組(X,Y,G,B) 稱為一個(gè)不完全可分組設(shè)計(jì)(IGDD)當(dāng)滿足以下條件:

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

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

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

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

型如(v,h)k的(k,λ)-IGDD稱作不完全橫截設(shè)計(jì), 并被記作ITDλ(k,v;h). 當(dāng)λ=1時(shí)就記為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時(shí)給出了1-BSEC(v, 5, λ)的構(gòu)造方法和幾個(gè)無窮類的存在性, 在指數(shù)為10時(shí)給出了使得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}時(shí), 存在1-BSEC(v, 5, 5).

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

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

證明 首先在Z10∪{∞}作一個(gè)型為2511的(5, 4)-GDD, 然后以{0, 5}, {1, 6}, {2, 7}, {3, 8}, {4, 9} 和{∞} 當(dāng)作組, 兩個(gè)基區(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時(shí), 由文[4]可知， 1-BSEC(v, 5, 4)存在的必要條件為v≥15且v≡0, 3(mod 5)也是充分的， 除了v=213這個(gè)不確定的例外點(diǎn), 那么可得1-BSEC(38, 5, 4)和1-BSEC(23, 5, 4)是存在的. 又根據(jù)定理5, 取 2m=38,x=23即可證明存在1-BSEC(213, 5, 4) 這個(gè)不確定的例外情況, 所以也就證明了該定理.

定理7v≡1, 5(mod 10),v≥5且v≠15時(shí), 如果存在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時(shí), 由文[4]知, 存在B(5, 2;v), 對X中的所有點(diǎn)加權(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)時(shí)， 存在1-BSEC(v, 5, 2).

證明 當(dāng)v≡23(mod 230)時(shí), 設(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)時(shí), 1-BSEC(23(10t+5), 5, 2)也存在.

定理9當(dāng)m是素?cái)?shù)冪,m≥9, 且x是一個(gè)整數(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個(gè)平行類, 設(shè)為Pi(1≤i≤7). 接著在每個(gè)平行類Pi中, 對任何區(qū)組里都加點(diǎn)∞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時(shí), 由文[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中其余的點(diǎn)存在. 當(dāng)X=(H1A)∪{123, 143} 且v∈X時(shí), 存在1-BSEC(v, 5, 5) .

3) 記m∈{9, 13, 17},x=[27, 115]4且x?{107, 111}, 根據(jù)定理9 和定理 3 分別取點(diǎn)對(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)時(shí)， 存在1-BSEC (v, 5, 5).

證明 1) 當(dāng)v≡1(mod 4)且v≥5時(shí), 由文[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í), 設(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時(shí), 70t+35≥62t+97, 此時(shí)前面的點(diǎn)已經(jīng)可以覆蓋住后面的點(diǎn). 當(dāng)t=8 時(shí),vt=[531, 595]2. 記A=[17, 529]2, 即若對任意v∈A都存在1-BSEC(v, 5, 10), 則對大等于529之后的所有v點(diǎn)都存在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時(shí)存在1-BSEC(v, 5, 10), 且當(dāng)v≡5(mod 10) 且v≥25 時(shí), 存在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時(shí)各vt的存在區(qū)間, 再結(jié)合定理10 已知存在1-BSEC(v, 5, 5)的小階數(shù)重復(fù)區(qū)組, 并利用文[10]的構(gòu)造方法取點(diǎn)對(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時(shí)均存在1-BSEC(v, 5, 10). 則當(dāng)v∈H時(shí)若1-BSEC(v, 5, 10)也存在, 可得1-BSEC(v, 5, 10)存在的充分必要條件就為v≡1(mod 2)且v≥17.