当前位置:首页 期刊杂志

议“柯克曼女生问题”

时间:2024-05-08

【摘要】“柯克曼女生问题”实质就是解决STS(v)、KTS(v),LSTS(v)、LKTS(v)等组合设计的存在性、构造及其可解数.文章在“K题”、“J题”可解性的基础上,列举了六种类型“K题”和一种“J题”的人工构造方法,并从不同角度探讨了可解总数的7种推算结果.

【关键词】柯克曼女生问题;K题J题;充要条件;解法;解数

【中图分类号】O157.1 【文献标识码】A

“柯克曼女生问题”,是因英国数学家柯克曼(T.P.Kirkman)1847年在《女士與先生之日记》杂志上,发表了一篇题为“疑问六”的女生散步命题而引出的.其意是:一位女教师带领15名女学生散步,每3人一组共5组结伴而行.问能否安排一周7天的散步计划,使其中任意2名女生曾被分到一组,且仅被分到一组?笔者将此命题简称为“K题”.之后英国数学家西尔菲斯特(J.J.Sylvester)和凯莱(A.Cayley),又于1850年将此题扩展为:能否安排13周的散步计划,不但使每周都符合“K题”要求,而且使其中任意3名女生曾被分到一组,且仅被分到一组?笔者将此扩展题简称为“J题”.

“K题”“J题”先后提出后,从19世纪中叶开始,到20世纪,直至当今,从英国、德国、法国到美国,苏联(俄罗斯),到中国,无数学者和爱好者从组合数学理论对“K题”“J题”进行了百多年的研究、探讨.他们绞尽脑汁、呕心沥血,前赴后继地攻下了一道道难关,攀登了一个个险峰,创立出“组合设计”这一新理论,为组合数学增添了一个重要分支,推动着现代应用数学的发展!

把v元集X(v)中的元,按k个元一组的子集(称作区组)共b个进行配置,这种组合设计的类型称作区组设计.若使每个元在b 个区组中出现γ次,每对元在b个区组中出现λ次,则此区组设计叫平衡区组设计.由于涉及v、b、γ、k、λ5个参数,平衡区组设计又可用{v、b、γ、k、λ}设计表示.

若一个区组集B(Bi),可分拆为若干平行类,使得每个元素恰好出现在每个平行类的一个区组中,则称其为可分解的,记为RB(k,λ,v),可分解的STS(v)即RB(3,1,v)被称为Kirkman三元系,记作KTS(v).

将v集X(v)上总计v3个3-子集分拆为彼此没有公共3-子集的(v-2)个STS(v),记作DS(v),这种配置就称v阶Steiner三元系大集,记为LSTS(v).

将v集X(v)上总计v3个3-子集分拆为彼此没有公共3-子集的(v-2)个KTS(v),记作DK(v),这种配置就称v阶Kirkman三元系大集,记为LKTS(v).

显然,“K题”就是一个KTS(15),即RB(3,1,15)设计,“J题”就是一个LKTS(15),即DK(15)=13设计.因此笔者认为“柯克曼女生问题”,实质就是解决STS(v)、KTS(v),LSTS(v)、LKTS(v)的存在条件,构造方法和可构总数.

一、关于“K题”“J题”可解的充要条件

关于“K题”“J题”引发的STS(v)、KTS(v),LSTS(v)、LKTS(v)设计的存在性,即设计的充要条件,经学者百年的艰苦努力,已从理论上基本破题,特别是我国组合数学家陆家羲贡献突出,他不但攻下LSTS(v)设计存在性的难题外,还对RB(k,λ,v)设计作出了存在性的一般性结论.

关于陆家羲的研究成果,康庆德教授,罗见今教授都有专著[1],笔者就有关存在性结论摘录如下:

1.存在STS(v),当且仅当v≡1,3(mod6),且v≥3;

2.存在KTS(v),当且仅当v≡3(mod6),且v≥3;

3.若v≡1,3(mod6),且v>7则D(v)=v-2,LSTS(v)存在;

4.若v≡3(mod6),且v>7则D(v)=v-2,LKTS(v)存在;

对照以上充要条件,“K题”为{35,15,7,3,1}设计,其中v=15,v-3=12,可被6整除,KTS(15)可解;“ J题”为LKTS(15)=13设计,其v=15,v-3=12可被6整除,存在v-2=13,可解.

二、关于“K题”“J题”的题解.

“K题”“J题”题解就是进行排列配置的具体操作,即对15名女生一周7天和13周91天的3人行按要求进行编排.对此编排,从学者至爱好者,从大学生到初中生都纷纷进行着尝试、摸索,可谓方法种种,结果多多,至今还没有一个定式.

笔者在2007年和2013年分别对“K题”和“ J题”的编排进行过艰苦的摸索,设计了一个abc法,试图用手工排出a,b,c三个字母,且下标1,2,3,4,5五个数字的abc型式,组成7×5行列式(每天为行,各组为列),定义为abc模式,即一周7天的散步计划.同时欲从abc模式的结构特征推导出编排总数.这期间也学习了不少有识之士之论点,对本人深有启发,对《解“柯克曼难题” 之abc法》中之不足、甚至错误之处有所领悟,对“K题”“ J题”的构造、总数有进一步认识.

从笔者搜集到的资料,“柯克曼女生问题”的构造方法有两大类:

一类是借助电子计算机编排程序构造,为数尚不多,除1974年美国数学家顿利斯特(R.H.Denniston)借助电子计算机编制出 “ J题”安排的数学模型[2]外,还有天津理工学院光电信息与电子工程系张金标教授于2002年编制的计算机快速求解程序[3],安徽大学计算机系程锦松教授于2003年编制的计算机回朔法程序[4].后两位教授只解了“K题”.

另一类就是人工编排法,此类应用较多,有表格编排,图解编排,行列编排等,而这些方法又多用于“K题”.目前涉及“J题”的人工法有宁夏韩进轩于1990年发表了一个简化 “J题”解,即LRS(9)=7的解法【5】,还有江苏王华学于2011年5月14日在网易博客hfliuob的日记中列出了第22029类的72个“K题”解和编号8的一个“J题”解,但并未介绍具体方法.本人斗胆在《abc法》中探索了“K题”和“J题”的一种人工方法.

个人认为凡用人工编排的都具有两个特点:

一是15名散步女生都以数字或字母标志.有的用1,2,…,15标志,有的用大小字母A(a),B(b),…,O(o)代表.还有用字母+数字(并标或下标)标志;

另一个是都先行设定基础序列.有的编排第一天(或星期日、首日)的散步安排,依此再编排后6天的散步安排;有的则是将某一编号的女生固定在7天的最前位置上,再将其余14名女生编号,按两人编组共7组,分别与7天所固定的那名女生,编成7天中第一组的3人行,依此再编制每天其他各组的3人行.

现据笔者拙见选择6种类型案例:

1.英国牧师弗罗斯特的一般性解法.

其要点是,以x,a1,a2,b1,b2,c1,c2,d1,d2,e1,e2,f1,f2,g1,g2等15个元素为15名女生的编号,并按天为列、组为行排成7列,每列5组,每组3个元素,且使任意选出的两个元素出现于7×5=35个三元组合中的一个,且仅出现在这一组合中.作为7列中的初始三元组合现选定为:

Xa1a2Xb1b2Xc1c2 Xd1d2 Xe1e2 Xf1f2 Xg1g2

然后只要把a1,a2,b1,b2,……g1,g2等14个元素正确地分布在系列的其他4行上就可得一个题解.

首先用a,b,…,g,这7个字母按顺序排列,构成一个三元组合群,其中每对元素恰好只出现一次,即abc,ade,afg,bdf,beg,cdg,cef.从这个群里恰好可以为每列选取4个三元組合,使这些组合包含在该列第一行中已出现的字母之外的其他所有字母,然后将这些三元组合按字母顺序排入每列便得如下初始安排:

星期日

星期一

星期二

星期三

星期四

星期五

星期六

Xa1a2

Xb1b2

Xc1c2

Xd1d2

Xe1e2

Xf1f2

Xg1g2

bdf

ade

ade

abc

abc

abc

abc

beg

afg

afg

afg

afg

ade

ade

cdg

cdg

bdf

beg

bdf

beg

bdf

cef

cef

beg

cef

cdg

cdg

cef

最后用下标1和2对初始安排作出标志,可按bdf、beg、cdg、cef、ade、afg、abc次序进行标注,并遵守下列规则:

(1)一列中的一字母标上一个下标后,下一次该字母在同一系列中出现时应标上另一个下标;

(2)假如一个组合的某两个字母已标有下标,这两个下标不得以同顺序标在别的组合中该两个字母上;

(3)假如一个字母的下标尚未按以上规则决定,那末将这个字母标上1.

按以上规则标注初始安排,即得一题解:

星期日

星期一

星期二

星期三

星期四

星期五

星期六

Xa1a2

Xb1b2

Xc1c2

Xd1d2

Xe1e2

Xf1f2

Xg1g2

b1d1f1

a1d2e2

a1d1e1

a2b2c2

a2b1c1

a1b2c1

a1b1c2

b2e1g1

a2f2g2

a2f1g1

a1f2g1

a1f1g2

c2d2e1

a2d1e2

c1d2g2

c1d1g1

b1d2f2

b1e1g2

b2d1f2

b1e2g1

b2d2f1

c2e2f2

c2e1f1

b2e2g2

c1e2f1

c2d2g1

a2d1g2

c1e1f2

笔者在搜集有关此方法时发现无论是10年前还是近几年,当凡引用弗罗斯特解“K题”此方法时,都有跟风式的错误之处:

(1)初始安排中的星期一之第二行都错为abe,致使注入下标也错误为b2.当日的第一行明明已是Xb1b2了,此日就不能再有b(b2)应是ade(a1d2e2);

(2)答案中星期三的第二行错为a1b2c2、第三行错为a2f2g1,如此就会出现a1b2与a2f2各两个,应是a2b2c2与a1f2g1;

(3)同理,星期四的第二、三行错为a1b1c1与a2f1g1,应是a2b1c1与a1f1g2.

以上明显之错,能持续之久、之广非吾所思,借此以予纠正,以免再行错传!

2.B.皮尔斯(B.Pierxe)递推解法[6].

1862年皮尔斯对“K题”给出一种有代表性的,并被西尔菲斯特称为最佳解题方法:先假定一名女生固定在某一组,再将其他女生从1到14编号,并按一定规律安排了星期日的分组散步计划,则其他6天星期γ(γ=1,2,…,6)的散步分组,可按原编号与γ与数字之和安排(和数超14的则减去14).

此方法关键在于如何安排星期日的分组计划.由于一时未搜集到此法的具体内容,本人不揣浅薄推敲了一段时间,最后我的结论是,按以上编号进行递推不可解!其原因:

(1)现将每天为行,每天5组三元组合为列,若可解,此编排呈14列从小到大的循环数字序列,为了不出现两名女生在35个三元组中的重复,其星期日的5个三元组中各两两元素数字之差不能相同,这就需要3×4+1=13个差数,即有1,2,…,13这13个差数.而满足13这个差数的编号只有1与14编号的数字之差,这样1和14编号已定,那12这个差数就无法满足;

(2)在星期日的5个三元组中,两两元素中当有一个大于8时(不含8)此列必出现14编号,按递推法其下必是1编号,就会在此两列中出现上下两个差数,且除差数7之外两差数不同,也就会造成14列中相同的差数.

如何按递推法才能解“K题”呢?本人经摸索认为只有将1至14这单一的序列编号,划为两个序列编号方可.

现将X外的14名女生以a1,a2,a3,a4,a5,a6,a7,b1,b2,b3,b4,b5,b6,b7编号,这样a和b的下标数字之差就是相同也无碍解题.试选定以a下标1与2,3与5,4与7其差分别1、2、3;选定b下标4、5、7,之间差也为1、2、3,由此即可排出星期日,继而排出一周的散步安排:

星期日

a1a2b1

a3a5b6

a4a7b2

a6Xb3

b4b5b7星期一

a2a3b2

a4a6b7

a5a1b3

a7Xb4

b5b6b1星期二

a3a4b3

a5a7b1

a6a2b4

a1Xb5

b6b7b2星期三

a4a5b4

a6a1b2

a7a3b5

a2Xb6

b7b1b3星期四

a5a6b5

a7a2b3

a1a4b6

a3Xb7

b1b2b4星期五

a6a7b6

a1a3b4

a2a5b7

a4Xb1

b2b3b5星期六

a7a1b7

a2a4b5

a3a6b1

a5Xb2

b3b4b6

将上述安排中,a与b对换,下标数字不变,又是一题解.还可按下标数字进行编排,同样也能获得其他解.

3.关于“K题”“J题”解数

组合设计的计数是一个既复杂又较难的问题,因此对“K题”“J题”的解数至今还没有权威的结论.作为探索笔者意欲从“K题” “J题”的构造法中导出其结果.

1.从李立新置换解来计“K题”解数.

李立新本人按选择的首日散步分组计划可找到6912个答案,就此笔者认为按置换解法的程序应有3×3×3×2×3×3×2×2×2×2×2×2=27×18×16×4=31104个答案.进一步考虑首日散步分组计划的变化数即可计得总解数.

首日散步分组计划的变化数,笔者认为是C315×C312×C39×C36=455×220×84×20=168168000个,因此解数就有2个结果.

(1)168168000×6912=1162377216000组;

(2)168168000×31104=5230697482000组.

2.从湛义才13系列法来计“K题”解数.

湛义才本人对“K题”解数有个结论:

若只考虑一周第一组的变化,“K题”解有13×11×9×7×5×3×1=135135组;

若只考虑星期一一天的组合变化,“K题”解有91×55×28×10×1=1401400组;

若只考虑一周第一组及星期一第二组至第五组的组合变化,“K题”解有135135×40×124=670296600组;

星期二至星期日的第二组至第五组的变化数约608个,由此可知“K题”解数约有670296600×608=407523916800组.

对湛义才先生所列40,124数字之来源且不计,就提供的数据笔者认为“K题”解数亦可为:

1401400×11×9×7×5×3×1×608=8857072224000组

3.从“abc法”来计“K题”解数.

笔者abc法中,abc模式的第一行必是a1b1c1,a2b2c2,a3b3c3,a4b4c4,a5b5c5,而其余6行5列有以下几个特征:

(1)如abc型式的下标数字从小到大顺序排列,则下标数字形式必是123,124,125,134,135,145,234,235,245,345这10种形式;

(2)与上述10种下标数字形式相配置的abc形式必是abc,acb,bca,bac,cab,cba,aaa,aab,aba,baa,aac,aca,caa,bbb,bba,bab,abb,bbc,bcb,cbb,ccc,cca,cac,acc,ccb,cbc,bcc,等27種;

(3)6行5列中共需30个下标数字形式与30个abc形式相配置成30个abc型式(注意形式与型式的区别),根据“K题”条件,不但需要10种下标数字形式各3个,而且所配置的3个abc型式必不在同一行出现,只能在6行中的3行出现;

(4)同样根据“K题”条件,每种下标数字与某个abc 形式配置后,就必有其他6种abc 形式不能再与其相配置.如123形式配置abc 形式成为a1b2c3型式后,下标数字123形式就不能与abb、aac、acc,bbc,cbc 这6种abc 形式再配置了.

由以上特征可计“K题”解数:

(1)10个不同下标数字形式各3个可与27种abc形式配置的变化数为:10×27×(27-1-6)×(27-1-6-1-6)=10×27×20×13=70200个;

(2)10种下标数字中的1种与3个abc形式配置的3个abc型式,排列在6行中的3行后,其余9种下标数字形式的各3 和abc形式配置出的27个abc型式,必能与其组成一个abc模式,即为一个答案.而放入6行中3行的变化数有C36=20种,则共有题解为70200×20=1404000组;

(3)计算首日散步分组计划的变化数.按其结构性质原首日散步5个三元组中,每三个字母的下标数字仅能变化其中的一个,因此首日散步分组计划的变化数有3×12×3×9×3×6×3×3=36×27×18×9=157464个;

(4)“K题”解数为1404000×157464=221079456000组.

4.从“abc法”编排来计“J题”解数.

由于行列式行与行,列与列之间的互换性质,“abc法”解“J题”中所选定的2元(a1、b1),可任意排在某2列上(一列,二列)而不影响其结构,而其余13个元所排定的位置影响着结构的变化,因此“J题”的解数为C315×5=105×5=525组.

综上关于“K题”解数的5个结果,加上张金标电子计算机快速求解程序获得“K题”404756352000组解数,共6个结果,以及“J题”解数的一个结果,愿供学者、专家评判、鉴定.

【参考文献】

[1]罗见今.Steiner系若干课题研究的历史回顾——陆家羲学术工作背景概述[J].数学进展,1986(15):2.

[2]康庆德.陆家羲与组合设计大集[J].高等数学研究,2008(1):1.

[3]张金标.女生散步问题的解.天津工学院学报第18卷第4期,2002年12月.

[4]程锦松.一种解寇克曼问题的计算机算法.安徽电气工程职业技术学院第九卷第1期,2004年3月.

[5]韩进轩.一类简化的Kirkman女学生问题的完整解.高等数学园地,1990年.

[6]王青建.数学开心辞典,第二版.名题赏析P355,2014年1月.

[7]鲁海燕,陈玮琪.科克曼女生问题的一种构造解[J].工科数学,第16卷第3期,2000年6月.

[8]湛義才.“科克曼女生问题”的探讨[J].大学数学,第30卷第2期,2014年4月.

[9]吴国浪.解《柯克曼难题》之abc法[J].南京大学数学系2013年11月8日出版(第2期).

免责声明

我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理! 部分文章是来自各大过期杂志,内容仅供学习参考,不准确地方联系删除处理!