議“柯克曼女生問題”

【摘要】“柯克曼女生問題”實(shí)質(zhì)就是解決STS（v）、KTS（v），LSTS（v）、LKTS（v）等組合設(shè)計(jì)的存在性、構(gòu)造及其可解數(shù).文章在“K題”、“J題”可解性的基礎(chǔ)上，列舉了六種類型“K題”和一種“J題”的人工構(gòu)造方法，并從不同角度探討了可解總數(shù)的7種推算結(jié)果.

【關(guān)鍵詞】柯克曼女生問題；K題J題；充要條件；解法；解數(shù)

【中圖分類號】O157.1 【文獻(xiàn)標(biāo)識碼】A

“柯克曼女生問題”，是因英國數(shù)學(xué)家柯克曼（T.P.Kirkman）1847年在《女士與先生之日記》雜志上，發(fā)表了一篇題為“疑問六”的女生散步命題而引出的.其意是：一位女教師帶領(lǐng)15名女學(xué)生散步，每3人一組共5組結(jié)伴而行.問能否安排一周7天的散步計(jì)劃，使其中任意2名女生曾被分到一組，且僅被分到一組？筆者將此命題簡稱為“K題”.之后英國數(shù)學(xué)家西爾菲斯特（J.J.Sylvester）和凱萊（A.Cayley），又于1850年將此題擴(kuò)展為：能否安排13周的散步計(jì)劃，不但使每周都符合“K題”要求，而且使其中任意3名女生曾被分到一組，且僅被分到一組？筆者將此擴(kuò)展題簡稱為“J題”.

“K題”“J題”先后提出后，從19世紀(jì)中葉開始，到20世紀(jì)，直至當(dāng)今，從英國、德國、法國到美國，蘇聯(lián)（俄羅斯），到中國，無數(shù)學(xué)者和愛好者從組合數(shù)學(xué)理論對“K題”“J題”進(jìn)行了百多年的研究、探討.他們絞盡腦汁、嘔心瀝血，前赴后繼地攻下了一道道難關(guān)，攀登了一個個險峰，創(chuàng)立出“組合設(shè)計(jì)”這一新理論，為組合數(shù)學(xué)增添了一個重要分支，推動著現(xiàn)代應(yīng)用數(shù)學(xué)的發(fā)展！

把v元集X（v）中的元，按k個元一組的子集（稱作區(qū)組）共b個進(jìn)行配置，這種組合設(shè)計(jì)的類型稱作區(qū)組設(shè)計(jì).若使每個元在b 個區(qū)組中出現(xiàn)γ次，每對元在b個區(qū)組中出現(xiàn)λ次，則此區(qū)組設(shè)計(jì)叫平衡區(qū)組設(shè)計(jì).由于涉及v、b、γ、k、λ5個參數(shù)，平衡區(qū)組設(shè)計(jì)又可用{v、b、γ、k、λ}設(shè)計(jì)表示.

若一個區(qū)組集B（Bi），可分拆為若干平行類，使得每個元素恰好出現(xiàn)在每個平行類的一個區(qū)組中，則稱其為可分解的，記為RB（k，λ，v），可分解的STS（v）即RB（3，1，v）被稱為Kirkman三元系，記作KTS（v）.

將v集X（v）上總計(jì)v3個3-子集分拆為彼此沒有公共3-子集的（v-2）個STS（v），記作DS（v），這種配置就稱v階Steiner三元系大集，記為LSTS（v）.

將v集X（v）上總計(jì)v3個3-子集分拆為彼此沒有公共3-子集的（v-2）個KTS（v），記作DK（v），這種配置就稱v階Kirkman三元系大集，記為LKTS（v）.

顯然，“K題”就是一個KTS（15），即RB（3，1，15）設(shè)計(jì)，“J題”就是一個LKTS（15），即DK（15）=13設(shè)計(jì).因此筆者認(rèn)為“柯克曼女生問題”，實(shí)質(zhì)就是解決STS（v）、KTS（v），LSTS（v）、LKTS（v）的存在條件，構(gòu)造方法和可構(gòu)總數(shù).

一、關(guān)于“K題”“J題”可解的充要條件

關(guān)于“K題”“J題”引發(fā)的STS（v）、KTS（v），LSTS（v）、LKTS（v）設(shè)計(jì)的存在性，即設(shè)計(jì)的充要條件，經(jīng)學(xué)者百年的艱苦努力，已從理論上基本破題，特別是我國組合數(shù)學(xué)家陸家羲貢獻(xiàn)突出，他不但攻下LSTS（v）設(shè)計(jì)存在性的難題外，還對RB（k，λ，v）設(shè)計(jì)作出了存在性的一般性結(jié)論.

關(guān)于陸家羲的研究成果，康慶德教授，羅見今教授都有專著[1]，筆者就有關(guān)存在性結(jié)論摘錄如下：

1.存在STS（v），當(dāng)且僅當(dāng)v≡1，3（mod6），且v≥3；

2.存在KTS（v），當(dāng)且僅當(dāng)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}設(shè)計(jì)，其中v=15，v-3=12，可被6整除，KTS（15）可解；“ J題”為LKTS（15）=13設(shè)計(jì)，其v=15，v-3=12可被6整除，存在v-2=13，可解.

二、關(guān)于“K題”“J題”的題解.

“K題”“J題”題解就是進(jìn)行排列配置的具體操作，即對15名女生一周7天和13周91天的3人行按要求進(jìn)行編排.對此編排，從學(xué)者至愛好者，從大學(xué)生到初中生都紛紛進(jìn)行著嘗試、摸索，可謂方法種種，結(jié)果多多，至今還沒有一個定式.

筆者在2007年和2013年分別對“K題”和“ J題”的編排進(jìn)行過艱苦的摸索，設(shè)計(jì)了一個abc法，試圖用手工排出a，b，c三個字母，且下標(biāo)1，2，3，4，5五個數(shù)字的abc型式，組成7×5行列式（每天為行，各組為列），定義為abc模式，即一周7天的散步計(jì)劃.同時欲從abc模式的結(jié)構(gòu)特征推導(dǎo)出編排總數(shù).這期間也學(xué)習(xí)了不少有識之士之論點(diǎn)，對本人深有啟發(fā)，對《解“柯克曼難題” 之a(chǎn)bc法》中之不足、甚至錯誤之處有所領(lǐng)悟，對“K題”“ J題”的構(gòu)造、總數(shù)有進(jìn)一步認(rèn)識.

從筆者搜集到的資料，“柯克曼女生問題”的構(gòu)造方法有兩大類：

一類是借助電子計(jì)算機(jī)編排程序構(gòu)造，為數(shù)尚不多，除1974年美國數(shù)學(xué)家頓利斯特（R.H.Denniston）借助電子計(jì)算機(jī)編制出 “ J題”安排的數(shù)學(xué)模型[2]外，還有天津理工學(xué)院光電信息與電子工程系張金標(biāo)教授于2002年編制的計(jì)算機(jī)快速求解程序[3]，安徽大學(xué)計(jì)算機(jī)系程錦松教授于2003年編制的計(jì)算機(jī)回朔法程序[4].后兩位教授只解了“K題”.

另一類就是人工編排法，此類應(yīng)用較多，有表格編排，圖解編排，行列編排等，而這些方法又多用于“K題”.目前涉及“J題”的人工法有寧夏韓進(jìn)軒于1990年發(fā)表了一個簡化 “J題”解，即LRS（9）=7的解法【5】，還有江蘇王華學(xué)于2011年5月14日在網(wǎng)易博客hfliuob的日記中列出了第22029類的72個“K題”解和編號8的一個“J題”解，但并未介紹具體方法.本人斗膽在《abc法》中探索了“K題”和“J題”的一種人工方法.

個人認(rèn)為凡用人工編排的都具有兩個特點(diǎn)：

一是15名散步女生都以數(shù)字或字母標(biāo)志.有的用1，2，…，15標(biāo)志，有的用大小字母A（a），B（b），…，O（o）代表.還有用字母+數(shù)字（并標(biāo)或下標(biāo)）標(biāo)志；

另一個是都先行設(shè)定基礎(chǔ)序列.有的編排第一天（或星期日、首日）的散步安排，依此再編排后6天的散步安排；有的則是將某一編號的女生固定在7天的最前位置上，再將其余14名女生編號，按兩人編組共7組，分別與7天所固定的那名女生，編成7天中第一組的3人行，依此再編制每天其他各組的3人行.

現(xiàn)據(jù)筆者拙見選擇6種類型案例：

1.英國牧師弗羅斯特的一般性解法.

其要點(diǎn)是，以x，a1，a2，b1，b2，c1，c2，d1，d2，e1，e2，f1，f2，g1，g2等15個元素為15名女生的編號，并按天為列、組為行排成7列，每列5組，每組3個元素，且使任意選出的兩個元素出現(xiàn)于7×5=35個三元組合中的一個，且僅出現(xiàn)在這一組合中.作為7列中的初始三元組合現(xiàn)選定為：

Xa1a2Xb1b2Xc1c2 Xd1d2 Xe1e2 Xf1f2 Xg1g2

然后只要把a(bǔ)1，a2，b1，b2，……g1，g2等14個元素正確地分布在系列的其他4行上就可得一個題解.

首先用a，b，…，g，這7個字母按順序排列，構(gòu)成一個三元組合群，其中每對元素恰好只出現(xiàn)一次，即abc，ade，afg，bdf，beg，cdg，cef.從這個群里恰好可以為每列選取4個三元組合，使這些組合包含在該列第一行中已出現(xiàn)的字母之外的其他所有字母，然后將這些三元組合按字母順序排入每列便得如下初始安排：

星期日

星期一

星期二

星期三

星期四

星期五

星期六

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

最后用下標(biāo)1和2對初始安排作出標(biāo)志，可按bdf、beg、cdg、cef、ade、afg、abc次序進(jìn)行標(biāo)注，并遵守下列規(guī)則：

（1）一列中的一字母標(biāo)上一個下標(biāo)后，下一次該字母在同一系列中出現(xiàn)時應(yīng)標(biāo)上另一個下標(biāo)；

（2）假如一個組合的某兩個字母已標(biāo)有下標(biāo)，這兩個下標(biāo)不得以同順序標(biāo)在別的組合中該兩個字母上；

（3）假如一個字母的下標(biāo)尚未按以上規(guī)則決定，那末將這個字母標(biāo)上1.

按以上規(guī)則標(biāo)注初始安排，即得一題解：

星期日

星期一

星期二

星期三

星期四

星期五

星期六

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

筆者在搜集有關(guān)此方法時發(fā)現(xiàn)無論是10年前還是近幾年，當(dāng)凡引用弗羅斯特解“K題”此方法時，都有跟風(fēng)式的錯誤之處：

（1）初始安排中的星期一之第二行都錯為abe，致使注入下標(biāo)也錯誤為b2.當(dāng)日的第一行明明已是Xb1b2了，此日就不能再有b（b2）應(yīng)是ade（a1d2e2）；

（2）答案中星期三的第二行錯為a1b2c2、第三行錯為a2f2g1，如此就會出現(xiàn)a1b2與a2f2各兩個，應(yīng)是a2b2c2與a1f2g1；

（3）同理，星期四的第二、三行錯為a1b1c1與a2f1g1，應(yīng)是a2b1c1與a1f1g2.

以上明顯之錯，能持續(xù)之久、之廣非吾所思，借此以予糾正，以免再行錯傳！

2.B.皮爾斯（B.Pierxe）遞推解法[6].

1862年皮爾斯對“K題”給出一種有代表性的，并被西爾菲斯特稱為最佳解題方法：先假定一名女生固定在某一組，再將其他女生從1到14編號，并按一定規(guī)律安排了星期日的分組散步計(jì)劃，則其他6天星期γ（γ=1，2，…，6）的散步分組，可按原編號與γ與數(shù)字之和安排（和數(shù)超14的則減去14）.

此方法關(guān)鍵在于如何安排星期日的分組計(jì)劃.由于一時未搜集到此法的具體內(nèi)容，本人不揣淺薄推敲了一段時間，最后我的結(jié)論是，按以上編號進(jìn)行遞推不可解！其原因：

（1）現(xiàn)將每天為行，每天5組三元組合為列，若可解，此編排呈14列從小到大的循環(huán)數(shù)字序列，為了不出現(xiàn)兩名女生在35個三元組中的重復(fù)，其星期日的5個三元組中各兩兩元素?cái)?shù)字之差不能相同，這就需要3×4+1=13個差數(shù)，即有1，2，…，13這13個差數(shù).而滿足13這個差數(shù)的編號只有1與14編號的數(shù)字之差，這樣1和14編號已定，那12這個差數(shù)就無法滿足；

（2）在星期日的5個三元組中，兩兩元素中當(dāng)有一個大于8時（不含8）此列必出現(xiàn)14編號，按遞推法其下必是1編號，就會在此兩列中出現(xiàn)上下兩個差數(shù)，且除差數(shù)7之外兩差數(shù)不同，也就會造成14列中相同的差數(shù).

如何按遞推法才能解“K題”呢？本人經(jīng)摸索認(rèn)為只有將1至14這單一的序列編號，劃為兩個序列編號方可.

現(xiàn)將X外的14名女生以a1，a2，a3，a4，a5，a6，a7，b1，b2，b3，b4，b5，b6，b7編號，這樣a和b的下標(biāo)數(shù)字之差就是相同也無礙解題.試選定以a下標(biāo)1與2，3與5，4與7其差分別1、2、3；選定b下標(biāo)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對換，下標(biāo)數(shù)字不變，又是一題解.還可按下標(biāo)數(shù)字進(jìn)行編排，同樣也能獲得其他解.

3.關(guān)于“K題”“J題”解數(shù)

組合設(shè)計(jì)的計(jì)數(shù)是一個既復(fù)雜又較難的問題，因此對“K題”“J題”的解數(shù)至今還沒有權(quán)威的結(jié)論.作為探索筆者意欲從“K題” “J題”的構(gòu)造法中導(dǎo)出其結(jié)果.

1.從李立新置換解來計(jì)“K題”解數(shù).

李立新本人按選擇的首日散步分組計(jì)劃可找到6912個答案，就此筆者認(rèn)為按置換解法的程序應(yīng)有3×3×3×2×3×3×2×2×2×2×2×2=27×18×16×4=31104個答案.進(jìn)一步考慮首日散步分組計(jì)劃的變化數(shù)即可計(jì)得總解數(shù).

首日散步分組計(jì)劃的變化數(shù)，筆者認(rèn)為是C315×C312×C39×C36=455×220×84×20=168168000個，因此解數(shù)就有2個結(jié)果.

（1）168168000×6912=1162377216000組；

（2）168168000×31104=5230697482000組.

2.從湛義才13系列法來計(jì)“K題”解數(shù).

湛義才本人對“K題”解數(shù)有個結(jié)論：

若只考慮一周第一組的變化，“K題”解有13×11×9×7×5×3×1=135135組；

若只考慮星期一一天的組合變化，“K題”解有91×55×28×10×1=1401400組；

若只考慮一周第一組及星期一第二組至第五組的組合變化，“K題”解有135135×40×124=670296600組；

星期二至星期日的第二組至第五組的變化數(shù)約608個，由此可知“K題”解數(shù)約有670296600×608=407523916800組.

對湛義才先生所列40，124數(shù)字之來源且不計(jì)，就提供的數(shù)據(jù)筆者認(rèn)為“K題”解數(shù)亦可為：

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

3.從“abc法”來計(jì)“K題”解數(shù).

筆者abc法中，abc模式的第一行必是a1b1c1，a2b2c2，a3b3c3，a4b4c4，a5b5c5，而其余6行5列有以下幾個特征：

（1）如abc型式的下標(biāo)數(shù)字從小到大順序排列，則下標(biāo)數(shù)字形式必是123，124，125，134，135，145，234，235，245，345這10種形式；

（2）與上述10種下標(biāo)數(shù)字形式相配置的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個下標(biāo)數(shù)字形式與30個abc形式相配置成30個abc型式（注意形式與型式的區(qū)別），根據(jù)“K題”條件，不但需要10種下標(biāo)數(shù)字形式各3個，而且所配置的3個abc型式必不在同一行出現(xiàn)，只能在6行中的3行出現(xiàn)；

（4）同樣根據(jù)“K題”條件，每種下標(biāo)數(shù)字與某個abc 形式配置后，就必有其他6種abc 形式不能再與其相配置.如123形式配置abc 形式成為a1b2c3型式后，下標(biāo)數(shù)字123形式就不能與abb、aac、acc，bbc，cbc 這6種abc 形式再配置了.

由以上特征可計(jì)“K題”解數(shù)：

（1）10個不同下標(biāo)數(shù)字形式各3個可與27種abc形式配置的變化數(shù)為：10×27×（27-1-6）×（27-1-6-1-6）=10×27×20×13=70200個；

（2）10種下標(biāo)數(shù)字中的1種與3個abc形式配置的3個abc型式，排列在6行中的3行后，其余9種下標(biāo)數(shù)字形式的各3 和abc形式配置出的27個abc型式，必能與其組成一個abc模式，即為一個答案.而放入6行中3行的變化數(shù)有C36=20種，則共有題解為70200×20=1404000組；

（3）計(jì)算首日散步分組計(jì)劃的變化數(shù).按其結(jié)構(gòu)性質(zhì)原首日散步5個三元組中，每三個字母的下標(biāo)數(shù)字僅能變化其中的一個，因此首日散步分組計(jì)劃的變化數(shù)有3×12×3×9×3×6×3×3=36×27×18×9=157464個；

（4）“K題”解數(shù)為1404000×157464=221079456000組.

4.從“abc法”編排來計(jì)“J題”解數(shù).

由于行列式行與行，列與列之間的互換性質(zhì)，“abc法”解“J題”中所選定的2元（a1、b1），可任意排在某2列上（一列，二列）而不影響其結(jié)構(gòu)，而其余13個元所排定的位置影響著結(jié)構(gòu)的變化，因此“J題”的解數(shù)為C315×5=105×5=525組.

綜上關(guān)于“K題”解數(shù)的5個結(jié)果，加上張金標(biāo)電子計(jì)算機(jī)快速求解程序獲得“K題”404756352000組解數(shù)，共6個結(jié)果，以及“J題”解數(shù)的一個結(jié)果，愿供學(xué)者、專家評判、鑒定.

【參考文獻(xiàn)】

[1]羅見今.Steiner系若干課題研究的歷史回顧——陸家羲學(xué)術(shù)工作背景概述[J].數(shù)學(xué)進(jìn)展，1986（15）：2.

[2]康慶德.陸家羲與組合設(shè)計(jì)大集[J].高等數(shù)學(xué)研究，2008（1）：1.

[3]張金標(biāo).女生散步問題的解.天津工學(xué)院學(xué)報(bào)第18卷第4期，2002年12月.

[4]程錦松.一種解寇克曼問題的計(jì)算機(jī)算法.安徽電氣工程職業(yè)技術(shù)學(xué)院第九卷第1期，2004年3月.

[5]韓進(jìn)軒.一類簡化的Kirkman女學(xué)生問題的完整解.高等數(shù)學(xué)園地，1990年.

[6]王青建.數(shù)學(xué)開心辭典，第二版.名題賞析P355，2014年1月.

[7]魯海燕，陳瑋琪.科克曼女生問題的一種構(gòu)造解[J].工科數(shù)學(xué)，第16卷第3期，2000年6月.

[8]湛義才.“科克曼女生問題”的探討[J].大學(xué)數(shù)學(xué)，第30卷第2期，2014年4月.

[9]吳國浪.解《柯克曼難題》之a(chǎn)bc法[J].南京大學(xué)數(shù)學(xué)系2013年11月8日出版（第2期）.