不同指数的区组长为5的1-BSEC的存在性

黄晨悦， 刘秉瀚

(1. 交通银行福建省分行, 福建 福州 350003; 2. 福州大学数学与计算机科学学院, 福建 福州 350108)

0 引言

平衡样本设计的存在性问题引起了许多数学家的关注. 它是抽取样本调查的某种方案设计, 此抽样方案在具有相同或者类似特征的相邻样本时会得到误差十分大的结果， Hedayat等[1]提出不含邻点的平衡样本设计(BSEC) 来避免抽取相邻的样本， 在BSEC中任意两个相邻点都不会被同时选取， 所以相邻样本造成的误差也就不存在了.

近几年来, BSEC的研究已经有了一系列的重要进展. Colbourn等[2]证明了1-BSEC(v, 3,λ) 的存在性. Colbourn等[3]证明了1-BSEC(v, 4,λ)的存在性. 李萌[4]基本解决了指数为4时1-BSEC(v, 5,λ)的存在性, 除了可能的例外v=213.

本研究主要介绍如何利用其它设计来构造 1-BSEC(v,k,λ), 并利用所得到的递归构造方法完全证明了指数为4时1-BSEC(v, 5,λ)的存在性, 并在指数为2, 5, 10时也得到了部分1-BSEC(v, 5,λ)的存在性.

1 相关已知结果和设计

设一个集合X={0, 1, …,v-1},X里的每个元都称作点， 当X上的一个圆排列C(X)=(x0,x1, …,xv-1)时, 把x0和xv-1,xi和xi+1(0≤i≤v-2)都称作是相邻点.

定义1[5]设一个集合X一共有v个元素且构成了圆排列C(X),B是由该集合的一些k子集所得到的集簇, 那么B里的元就叫区组. 把(X,B)称为一维不含邻点的区组长为k的平衡样本设计当子(X,B)满足以下两个条件:

1) 集合X内B的任意区组内不出现任何两个相邻的点.

2) 集合X内B的λ个区组内都恰好出现任何两个不相邻的点.

此样本设计简记为1-BSEC(v,k,λ).

引理1[4]当(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为正整数集合, 且G为一个有限集合X上的分拆, 该有限集合X的某些子集构成了集簇B, 则把三元组(X,G,B)称为一个可分组设计GDD, 并且记作GDD[K,λ,M;v]. 当满足以下条件:

1) ∀G∈G,G∈M,G里的元称为组.

2)X=v，X里的每个元都称作点.

3) ∀B∈B， ∀G∈G且B∈K，G∩B≤1,B里的元素称作区组.

4) 集合X内B的λ个区组里都恰有任意一对不在同一个组中的点出现.

定理 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) 当n为素数幂并且n≥9, 就存在TD(9,n).

定理 2[7]

1)记λ≥2， 型为mn的(5,λ)-GDD存在当且仅当: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]设Y是X的一个子集且G是集合X上的分拆, 集合X一共有v个元素. 该有限集合X的某些子集构成了集簇B, 把四元组(X,Y,G,B) 称为一个不完全可分组设计(IGDD)当满足以下条件:

1) ∀B∈B， ∀G∈G，G∩B≤1,G中的元称作组且B中的元称为区组.

2) 任何区组里都不出现Y中的任意两个点.

3) 任何一对不都属于Y且不在同一个组里的点刚好在B的λ个区组里出现.

当不完全可分组设计有ui个vi长组, 每个vi长组与洞Y有Hi个相交的点i=1, 2, …,s, 且它的每个区组长都属于K, 那么这个不完全可分组设计记作型为(v1,H1)u1, (v2,H2)u2， …， (vs,Hs)us的(k,λ)-IGDD. 当K={k}时, 简记K为k. 可以看出, 每个IGDD都为缺少一个 GDD作子设计的可分组设计. 如果洞Y是空集, 此(k,λ)-IGDD就为 (k,λ)-GDD. 如果λ=1, 则记为K-IGDD.

型如(v,h)k的(k,λ)-IGDD称作不完全横截设计, 并被记作ITDλ(k,v;h). 当λ=1时就记为ITD(k,v;h).

2 1-BSEC(v, k, λ) 的递归构造和结论

给出1-BSEC 的直接构造和递归构造, 利用所得到的递归构造方法完全证明了1-BSEC(v, 5, 4) 存在的充分必要条件, 并在指数为2, 5时给出了1-BSEC(v, 5, λ)的构造方法和几个无穷类的存在性, 在指数为10时给出了使得1-BSEC(v, 5,λ) 存在的充分必要条件所差的阶数.

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

证明 其基区组为:

{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) 当v∈{19, 27, 31, 35, 39, 47, 51, 55, 59, 67, 71, 75, 79, 87, 91, 99}时, 存在1-BSEC(v, 5, 5).

3) 当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是一个整数. 如果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} 和{∞} 当作组, 两个基区组分别为{0, 2, 3, 9, ∞} 与 {0, 2, 3, 4, 6}, 区组则以基区组+1(mod 10)生成.

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

证明 当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)是存在的. 又根据定理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) 当v≡1, 5(mod 10),v≥5且v≠15时, 由文[4]知, 存在B(5, 2;v), 对X中的所有点加权m, 如果存在ITD(5,m; 2), 那么我们在B中所有区组上构造型是(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当v≡23, 115(mod 230)时， 存在1-BSEC(v, 5, 2).

证明 当v≡23(mod 230)时, 设v=230t+23=23(10t+1), 其中t≥0. 由文[7]可知, 存在ITD(5, 23; 2). 且由文[4]可知, 存在1-BSEC(23, 5, 2), 根据定理7可得, 1-BSEC(23(10t+1), 5, 2)存在. 同理可证, 当v≡115(mod 230)时, 1-BSEC(23(10t+5), 5, 2)也存在.

定理9当m是素数幂,m≥9, 且x是一个整数并且满足x∈[3m, 7m-4]4. 如果1-BSEC(3m, 5, 5) 和1-BSEC(x, 5, 5)都存在, 那么1-BSEC(24m+x, 5, 5)也一定存在.

证明 首先构作型是3871的(5, 1)-GDD, 再根据文[11]可得 RGD[4, 1, 3; 24] 是存在的, 它有7个平行类, 设为Pi(1≤i≤7). 接着在每个平行类Pi中, 对任何区组里都加点∞i(1≤i≤7), 然后把 {∞1, ∞2, …, ∞7} 当成是新的组, 就能构造出型是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}, 当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) . 因此通过重复区组就可以证明1-BSEC(v, 5, 5)的存在性.

2) 由定理 3可知, 1-BSEC(19, 5, 5)存在, 再由定理 4可得1-BSEC(95, 5, 5)也存在. 同理可证明H1中其余的点存在. 当X=(H1A)∪{123, 143} 且v∈X时, 存在1-BSEC(v, 5, 5) .

3) 记m∈{9, 13, 17},x=[27, 115]4且x∉{107, 111}, 根据定理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当v≡23(mod 92)时， 存在1-BSEC (v, 5, 5).

证明 1) 当v≡1(mod 4)且v≥5时, 由文[7]可知存在B(5, 5;v)且对于洞存在型为25的(5, 5)-GDD. 那么同定理7构造方法一样即可证得， 如果存在 ITD(5,m; 2)和1-BSEC(m, 5, 5), 则1-BSEC(mv, 5, 5)也存在.

2) 当v≡23(mod 92)时, 设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]知, 当m是大于等于7的奇数且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的奇数且x∈[m+4, 5m]2, 接着设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, 当t≥8时, 70t+35≥62t+97, 此时前面的点已经可以覆盖住后面的点. 当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=A1∪A2∪A3. 由文[10]可知, 当v∈A时存在1-BSEC(v, 5, 10), 且当v≡5(mod 10) 且v≥25 时, 存在1-BSEC(v, 5, 10). 同条件1), 设m=2t+1,vt=[62t+35, 70t+35]2, 由条件1) 知m是大于等于7的奇数且m≠15, 则可知t≥3且t≠7. 算出3≤t≤8且t≠7时各vt的存在区间, 再结合定理10 已知存在1-BSEC(v, 5, 5)的小阶数重复区组, 并利用文[10]的构造方法取点对(m,x)满足条件x∈[m+4, 5m]2且满足1-BSEC(5m, 5, 10)和1-BSEC(x, 5, 10)都存在, 则1-BSEC(30m+x, 5, 10)存在. 令A=[17, 529]2,B=AH, 能得到当v∈B时均存在1-BSEC(v, 5, 10). 则当v∈H时若1-BSEC(v, 5, 10)也存在, 可得1-BSEC(v, 5, 10)存在的充分必要条件就为v≡1(mod 2)且v≥17.