《肠外与肠内营养》杂志【期刊订阅】【在线投稿】

特殊斯坦纳系设计的一个构造方法（一）

王本材（海南口腔医院，海南海口570100）

摘要：目的：探讨k为质数时斯坦纳系（k^2，k，1）-设计的构造方法。方法：根据（k^2，k，1）-设计k^2个男生0~k天分组散步方案，定义系统位置简化编码为ij，第k天的分配方案为i{j}，根据质数性质进行mod(k)运算。结果： 0~(k-1)天系统位置简化编码为ij处的置入编码表达式为j{n∙j+i}。结论：k为质数时斯坦纳系（k^2，k，1）-设计可存在一般性构造方法。

关键词：斯坦纳系质数模运算k^2 男生散步问题

平衡不完全区组设计(balanced incomplete block design,简称BIBD或BIB)可以计作(b, v, r, k ,λ)-设计，斯坦纳系是当λ=1时的一种特殊形式，计作(v,k,1)-设计。其中，(v,3,1)-设计被称为斯坦纳三元系或斯坦纳三连系。与其相关的问题有1850年科克曼在《女士与先生之日记》杂志上提出的15个女学生散步问题：一位女教师每天带领她班上的15名女生去散步，她八这些女生按3人一组分成5组，问能不能作出一个连续散步7天的分组计划，使得任意两个女生曾被分到且仅被分到一组？本文将讨论k为质数，且v=k^2时的斯坦纳系构造方法。

斯坦纳系(k^2，k，1)-设计可以仿照科克曼女生问题设计成如下男生散步问题：k^2个男生每天分组散步1次， k人1组，共k组，规定k+1天内任意2人都有1次（且仅1次）编在同组。要求排出一个连续散步k+1天的分组方案。

为了讨论方便，我们设定记录天数的方式由1~(k+1)天改为0~k天，其中任意1天编号记录为n，可知0≤n≤(k-1)。

总体思路：将0~k天分配方案的空间位置固定，并确定其编码（定义为系统位置编码），将不同的男生置入不同的位置，男生的编码由系统位置简化编码编辑得出，最后证明任意两个男生曾被分到且仅被分到一组。

第一步：确定系统位置编码

n表示0~k-1天中的任意一天，k天使用k表示。i表示0~k-1组中的任意一组，j表示组中0~k-1位的任意一位。设计中n天i组j位计作nij，k天i组j位计作kij，为系统位置编码。当不考虑天数时去除n，计作ij，定义为系统位置简化编码。0~k天中，系统位置简化编码排列顺序不变。

第二步：构造第k天时的分配方案。

定义第k天（也就是最后一天）的分组方案。将k^2男生随机分为0~(k-1)组，并一一对应置入0~k-1位。则，每个男生对应的简化系统编码由i组和j位2阶数字构成，并由此形成男生的身份编码，记录为I{J}。两男生身份编码重合的判定标准：若I'{J'}=I{J}，则I'=I，且J'=J。

k天的分配方案定义为身份分组。身份分组定义了男生的身份编码。且在k天时，系统位置简化编码为ij处置入的男生为I{J}

身份分组的分配方式如下：

第k天:第0组：0{0},0{1},0{2},……,0{J},……,0{k-1};

第k天:第1组：1{0},1{1},1{2},……,1{J},……,1{k-1};

第k天:第2组：2{0},2{1},2{2},……,2{J},……,2{k-1};

……;

第k天:第i组：I{0},I{1},I{2},……,I{J,}……,I{k-1};I{0},

……;

第k天:第k-1组：(k-1){0},(k-1){1},(k-1){2},……,(k-1){J},……,(k-1){k-1};

注： i,j,n,k自0计数，是为了方便讨论的编号需要，它们的实际位置为{i,j,n,k}+1处。

第三步：构造第0~(k-1)天时，轮换到任意系统位置处男生置入编码的分配方案。

0~k-1天时简化系统编码处将置入不同的男生，其编码称为置入编码，表示为a{b}，置入编码重合判定标准：若a{b}= a'{b'}，则a=a',且b=b'。

定义：置入编码的值对应的身份编码，既，当a=I,且b=J时，a{b}=I{J}。

定义运算法则：当n∙j+i≥k时，取值为(n∙j+i) mod k；同时，k=0(mod k)。

则第0~(k-1)天时，系统位置简化编码ij处放入置入编码a{b}=j{n∙j+i}的男生。

如：第n天第i组的分配方案如下：

系统位置简化编码：i0, i1, i2, ……,ij, ……, i(k-1) ;

第0天，第i组： ……,j{i}, ……

第1天，第i组： ……,j{j+i},……

……

第n天, 第i组：0{i},1{n+i},2{n∙2+i},……,j{n∙j+i},……,(k-1){n∙(k-1)+i};

……

第k-1天，第i组： ……,j{(k-1)j+i},……

第四步：证明

基本命题：当k为质数，且0≤j,i,n≤(k-1)时，任意i≠n∙j+i mod k。

1、证明任意第n天内不会出现相同的置入编码。

根据置入编码重合的判定标准：若j{n∙j+i}=j'{n∙j'+i'}，则j=j',n∙j+i=n∙j'+i';

当j≠j'时，j{n∙j+i}≠j'{n∙j'+i'};

当j=j',i≠i'时，n∙j'+i'=n∙j+i'≠n∙j+I;

因此j{n∙j+i}≠j'{n∙j'+i'}。

2、证明任意第n天内的置入编码都可以找到一个与之对应的身份编码。

已知：0≤j,i,n≤(k-1);

置入编码表达式：a{b}=j{n∙j+i},a=j≤(k-1), b=n∙j+i mod k≤(k-1);

身份编码：I{J}为0~k-1组,0~k-1位连续排列，因此a{b}=j{n∙j+i}必然能被I{J}表达。

3、证明任意第n天内不会出现相同的身份编码。

已知：当a=I,且b=J时，a'{b}=j{n∙j+i}=I{J}; a'{b'}j'{n∙j'+i'}=I'{J'}。

根据证明1、2可知， j{n∙j+i}≠j'{n∙j'+i'};因此I{J}≠I'{J'};

4、证明任意第n天内的置入编码都可以找到唯一一个与之对应的身份编码。

根据证明1、2、3可知，任意第n天内不会出现相同的置入编码和身份编码，且该天内置入编码都可以找到一个与之对应的身份编码。置入编码的总量=身份编码的总量=k^2。

依此特性，任意第n天内的置入编码都可以找到唯一一个与之对应的身份编码。

5、证明任意第n(n∈0~k-1)天任意同组内出现过的置入编码，不会同时出现在任意第n+m(m∈1~k-1，且当n+m≥k时，取值为n+m mod k；同时，k=0 mod k) 天的任意一组内。

根据置入编码设计方案可知判定置入编码重复标准：仅当a=c,且b=d时，a{b}=c{d}。

第n天某系统位置简化编码ij(i,j∈0~k-1)处男生的置入编码为：a{b}=j{n∙j+i}，得知其所在i组包含如下置入编码：

0{i}, 1{n∙1+i},2{n∙2+i},……j{n∙j+i}……(k-1){n∙(k-1)+i};。

同组中，取任意j+s位，其系统位置简化编码为i(j+s)，其置入编码(j+s){n∙(j+s)+i}, (s∈1~k-1,且当j+s≥k时，取值为j+s mod k；同时，k=0 mod k)。

可知，j{n∙j+i}≠(j+s){n∙(j+s)+i}

进一步判断第n+m天时，j{n∙j+i}与(j+s){n∙(j+s)+i}是否会同时出现于任意一组。

根据置入编码设计方案，设第n+m天时，j{n∙j+i}出现于系统位置简化编码为ef处，则此处置入编码为f{(n+m)∙f+e}。

因置入编码与身份编码唯一对应，

则f{(n+m)∙f+e}=j{n∙j+i}，

可知，f=j,且(n+m)∙f+e=n∙j+I mod k,

可得，(n+m)∙j+e= n∙j+i mod k,

m∙j+e=i mod k,

e=i-mj mod k,

设第n+m天时，(j+s){n∙(j+s)+i}出现于系统位置简化编码为Eg处, 则此处置入编码为g{(n+m)∙g+E}。

则g{(n+m)∙g+E}=(j+s){n∙(j+s)+i}，

可知g=j+s,且(n+m)∙g+E=n∙(j+s)+i mod k,

可得，(n+m)∙(j+s)+E=n∙(j+s)+i mod k,

E=i-(n+m)∙(j+s)+n∙(j+s) mod k,

E=i-m(j+s) mod k,

若e=E mod k,

则，i-mj=i-m(j+s) mod k,

则，m∙s=0 mod k;

因，m,s∈1~k-1，故，等式不成立。

因此，任意第n(n∈0~k-1)天任意同组内出现过的置入编码，不会同时出现在任意第n+m(m∈1~k-1，且当n+m≥k时，取值为n+m mod k；同时，k=0 mod k)天的任意一组内。

6、证明j{n∙j+i}与(j+s){n∙(j+s)+i}不会同时出现于身份分组的同一组中。

由证明4可知，j{n∙j+i}与(j+s){n∙(j+s)+i}必然会出现于身份分组中。

第k天时的分配方案，身份分组方案以及定义系统位置简化编码和置入编码方案可知,在身份分组中，置入编码i{j}对应的组位编码值为即为系统位置简化编码，计作ij。

则，j{n∙j+i}在身份分组中的简化系统编码为j(n∙j+i)，位于身份分组的j组n∙j+i位，(j+s){n∙(j+s)+i}在身份分组中的简化系统编码为(j+s)(n∙j+i)，位于身份分组的j+s组n∙(j+s)+i位，因此j{n∙j+i}与(j+s){n∙(j+s)+i}不会同时出现于身份分组的同一组中。

证毕。

至此，k为质数的斯坦纳系(k^2，k，1)-设计构造完成，其任意n(n∈0~k)天简化系统编码ij处的置入编码表达式为：

a{b}=j{n∙j+i},(n∈0~k-1)，

a{b}=i{j},(n=k);

(n∈0~k+1,且i,j∈0~k-1)

若希望避免出现0，既，(N∈1~k+1,且I,J∈1~k)时,则任意I≠(N-1)∙(J-1)+I mod k(N∈1~k)。其任意N(N∈1~k+1)天简化系统编码IJ处的置入编码表达式可转换为：

a{b}=J{(N-1)∙(J-1)+I},(N∈1~k)，

a{b}=I{J},(N=k+1);

(N∈1~k+1,且I,J∈1~k)。

本设计运用质数性质，构造k为质数时斯坦纳系(k^2，k，1)-设计，但当k为合数时i≠n∙j+i mod k不恒成立，因此，此公式仅仅适合k为质数时的（k^2，k，1）-设计。K为合数情况，将在以后进行讨论。

以下为（5^2，5，1）-设计分配方案：

0组 1组 2组 3组 4组