諶義才

(四川新川航空儀器有限責(zé)任公司，四川廣漢618300)

1 引 言

“某寄宿學(xué)校的15個(gè)女生，每天都要三人一行外出散步一次，怎樣安排才能使每個(gè)學(xué)生一周7天內(nèi)和其他14個(gè)女生在三人行中散步各1次.”看似簡(jiǎn)單的數(shù)學(xué)題難倒了世界上眾多著名數(shù)學(xué)家，這就是英國數(shù)學(xué)家科克曼(Thomas Penyngton Kirkma, 1806-1895)于1850年提出的著名的“科克曼女生問題”.

在科克曼發(fā)表女生問題的研究之后，西爾維斯特和凱萊對(duì)這一問題提出更苛刻的條件.西爾維斯特(15名女生問題：某班級(jí)有15名女生，老師每天組織她們出去散步，第三人一行，問如何安排女生順序使每個(gè)女生同其他女生同一行中散步，恰好13周不重復(fù).這一問題直到1974年才由美國的丹尼斯頓借助電子計(jì)算機(jī)得以確證，v=15如下的13個(gè)方案：

星期日 {i,a,b},{8+i,9+i,12+i},{3+i,7+i,10+i},{2+i,6+i,11+i},{1+i,4+i,5+i};

星期一 {2+i,8+i,b},{1+i,6+i,a},{4+i,7+i,11+i},{3+i,5+i,9+i},{i,10+i,12+i};

星期二 {11+i,12+i,b},{4+i,10+i,a},{6+i,7+i,9+i},{1+i,2+i,3+i},{i,5+i,8+i};

星期三 {5+i,7+i,b},{3+i,12+i,a},{2+i,9+i,10+i},{1+i,8+i,11+i},{i,4+i,6+i};

星期四 {4+i,9+i,b},{2+i,5+i,a},{6+i,8+i,10+i},{1+i,7+i,12+i},{i,3+i,11+i};

星期五 {1+i,10+i,b},{9+i,11+i,a},{5+i,6+i,12+i},{3+i,4+i,8+i},{i,2+i,7+i};

星期六 {3+i,6+i,b},{7+i,8+i,a},{5+i,10+i,11+i},{2+i,4+i,12+i},{i,1+i,9+i}.

其中15名女生分別標(biāo)記為a,b,0,1,2,…,12，而數(shù)字i=0,1,…,12.每取i的一個(gè)值，所列的5×7個(gè)區(qū)組就給出了所求的隊(duì)形安排[1].此后，由“科克曼女生問題”引申出的組合數(shù)學(xué)中的一般的科克曼三元系存在性問題，一直到1971年才告徹底解決，其中包括中國的優(yōu)秀數(shù)學(xué)家陸家羲在內(nèi)的許多數(shù)學(xué)家都作出了貢獻(xiàn).從此之后，不但15個(gè)女生問題安排問題，哪怕是21個(gè)、27個(gè)、32個(gè)……，甚至是“6N+3”(N為自然數(shù))個(gè)的女生散步問題都已解決[2].

“科克曼女生問題”既是一個(gè)數(shù)學(xué)智力題，那就具備一定初等數(shù)學(xué)知識(shí)的人想必都可解，但未必都能解.本文用初等數(shù)學(xué)知識(shí)來解析這道智力題.

2 解析“科克曼女生問題”

用1～15號(hào)分別代表15個(gè)女生，三人一組按順序排列組合，則“科克曼女生問題”的15個(gè)女生全部排列組合形式見表3.

2.1 選一周的1號(hào)女生組合

將2～15號(hào)女生任意分成7組，再將1號(hào)女生加入，再按順排組合填入表1.

2.2 選一周的2號(hào)女生組合

2號(hào)組合亦有7組，在表1中星期一第一組中已有一個(gè)2號(hào)女生組合(1-2-15)，因此在表3中只選定六個(gè)2號(hào)組合即可.

選星期二第二組的2號(hào)組合：在表3中找出2號(hào)全部排列組合78個(gè)，將有2-15，3-14，4-13，5-12，6-11，7-10，8-9及當(dāng)天3，14號(hào)的全部組合刪除，然后任意選一組排列組合(如選2-4-10)，并將2-4-10填入表1星期二第二組內(nèi).

選星期三第二組的2號(hào)組合：在表3中找出2號(hào)全部排列組合78個(gè)，將有2-15，3-14，4-13，5-12，6-11，7-10，8-9，2-4，2-10，4-10及當(dāng)天4，13號(hào)的全部組合刪除，然后任意選一組排列組合(如選2-3-11)，并將2-3-11填入表1星期三第二組內(nèi).

其余2號(hào)組合按此方法進(jìn)行選擇，六個(gè)2號(hào)組合就全部選定，選定后填入表1內(nèi).

表1 科克曼1，2號(hào)女生組合散步表

從表1中可以看出，2號(hào)女生組合放置的位置與1號(hào)女生有所不同.相同點(diǎn)是三人組合都是從小至大排列組合，不同點(diǎn)是：1號(hào)女生組合按順排組合，2號(hào)女生組合可任意放置那一天，只要當(dāng)天不同號(hào)即可.至此，1號(hào)和2號(hào)的組合選擇共13組，全部選定.

2.3 其它三人組組合的選擇

1號(hào)女生組合和2號(hào)女生組合共13組選定后，剩下的其它22組三人組合選擇難度較大.其選擇方法就不能用上述1號(hào)女生組合和2號(hào)女生組合的選擇方法進(jìn)行選擇，必須把剩余組合組列出(限于篇幅，未列出組合組).對(duì)組合組進(jìn)行篩選，確定22組的組合位置.在此給出科克曼女生散步一組解，見表2.

表2 科克曼15女生散步一組解

從表2組合中可以看出幾個(gè)特點(diǎn)：

第一、每天15個(gè)女生分成五組，三人組合全部按順排組合.

第二、第一組1號(hào)女生組合中間女生在排列位置上全部采用順排(從小到大)的方法，主要是考慮到后面計(jì)算組解的準(zhǔn)確數(shù).

第三、第二組的2號(hào)女生組合位置，可任意放置，只要當(dāng)天不出現(xiàn)同號(hào)即可.

第四，同一天第一組至第五組前面女生全部從小到大排列.

3 “科克曼女生問題”組合位置發(fā)生變化時(shí)，對(duì)組解的影響

若將表1中的1號(hào)組合中9號(hào)與10號(hào)對(duì)調(diào)，2號(hào)組合不變，“科克曼女生問題”的組解就會(huì)發(fā)生變化，在此給出科克曼女生散步一組解，見表4.

若將表中的2號(hào)組合中13號(hào)與14號(hào)對(duì)調(diào)，1號(hào)組合不變，“科克曼女生問題”的組解亦會(huì)發(fā)生變化，在此給出科克曼女生散步一組解，見表5.

合理選擇排水管材對(duì)于管道的使用壽命、日常維護(hù)以及控制工程造價(jià)都起到非常關(guān)鍵的作用，本次施工選用高密度聚乙烯（HDPE）雙壁波紋管、排水檢查井選用塑料檢查井（成品），此類管道、井體不僅抗壓耐沖擊、內(nèi)壁光滑摩阻小，而且重量輕、施工快捷[2]。

由表4和表5組解可見，無論是1號(hào)組合位置還是2號(hào)組合位置發(fā)生變化，“科克曼女生問題”的組解結(jié)果都會(huì)發(fā)生變化.由此可見，在滿足題意的前提下，可以對(duì)1號(hào)組合或2號(hào)組合進(jìn)行調(diào)整，也可以同時(shí)對(duì)1號(hào)組合和2號(hào)組合進(jìn)行調(diào)整.通過對(duì)三人組合的調(diào)整，可以解得“科克曼女生問題”的不同組解.

表3 “科克曼女生問題”三人組合全部排列組合圖(從小至大排列，共455個(gè))

注X為女生代號(hào).用X=1代入，可得1號(hào)女生共91組排列組合；用X=2代入并刪除左1列，可得2號(hào)女生共78組排列組合；用X=3代入，并刪除左2列，可得3號(hào)女生共66組排列組合；其余號(hào)依此類推，最后一個(gè)就是13號(hào)女生的排列組合，只有1個(gè)為13-14-15.

表4 科克曼15女生散步一組解

表5 科克曼15女生散步一組解

4 “科克曼女生s問題”存在十三系列解

在研究“科克曼女生問題”時(shí)，發(fā)現(xiàn) “科克曼女生問題” 存在“十三系列解”.

1號(hào)女生存在一個(gè)“十三系列解” ，見表6.從表6中可以看出，表內(nèi)列出了1號(hào)女生的全部排列組合，并且在每個(gè)系列中，1號(hào)女生與其余號(hào)女生均見面一次.

2號(hào)女生存在三個(gè)“十三系列解” ，見表7、表8、表9.從表7、表8、表9中可以看出，各表內(nèi)列出了2號(hào)女生的全部排列組合，并且在每個(gè)系列中，2號(hào)女生與其余號(hào)女生均見面一次.

1，2號(hào)女生十三系列解可以合并，同一天出現(xiàn)同號(hào)時(shí)調(diào)整2號(hào)組合星期位置.

其余號(hào)女生(X)可以用1號(hào)女生十三系列解生成X號(hào)女生十三系列解，具體操作方法是：將X號(hào)與1號(hào)對(duì)換即可，再調(diào)整為順排形式.

表6 “科克曼女生問題” 1號(hào)女生十三系列解

表7 “科克曼女生問題” 2號(hào)女生十三系列解之一

表8“科克曼女生問題” 2號(hào)女生十三系列解之二

表9 “科克曼女生問題” 2號(hào)女生十三系列解之三

5 “科克曼女生問題”引申出的“6N+3”(N為自然數(shù))個(gè)的女生散步問題的研究

“科克曼女生問題”存在十三系列解，由此推論出“6N+3” (N為自然數(shù))個(gè)的女生散步問題都存在“6N+1”系列解”.

6 “科克曼女生問題”組解的計(jì)算

若只考慮一周第一組的組合變化，“科克曼女生問題”的組解有13×11×9×7×5×3×1=135135組.

若只考慮星期一一天的組合變化，“科克曼女生問題”的組解有91×55×28×10×1=1401400組.

若只考慮一周第一組及星期一第二至第五組的組合變化，“科克曼女生問題”的組解有670269600組，見表10.星期二至星期日的第二組至第五組的組合變化數(shù)計(jì)算起來很復(fù)雜，但其變化數(shù)只有數(shù)百種(約608種)的變化.由此可見，“科克曼女生問題”的組解約有670269600×608=407523916800組.

表10 “科克曼女生問題”組解計(jì)算

7 “科克曼女生問題”組解的應(yīng)用

“科克曼女生問題”的組解在醫(yī)藥試驗(yàn)設(shè)計(jì)上得到廣泛運(yùn)用.在滿足“科克曼女生問題”題意的前提下，可以對(duì)兩個(gè)號(hào)任意組合，隨意而動(dòng).就象練氣功一樣，意到那里氣就到那里.茲舉“科克曼女生問題”一組解(見表11).從表11中看1號(hào)組合和2號(hào)組合，其組合方式就象2條巨龍?jiān)谀抢镂鑴?dòng).

“科克曼女生問題” 一組解(表2組解：第十三系列)可以通過1號(hào)女生 “十三系列解” ，變換出一個(gè)“科克曼女生問題”十三系列組解，見表12.

8 結(jié) 論

本文給出了“科克曼女生問題”的解答方法：

第一步，選一周第一組的1號(hào)組合7個(gè).

第二步，再選一周第二組的2號(hào)組合6個(gè).

第三步，列出其余22組全部組合進(jìn)行篩選，確定22組組合位置.

注 亦可以任意選擇2個(gè)號(hào)進(jìn)行組合(7+6)個(gè)，再確定其余22組組合位置.

“科克曼女生問題”存在十三系列解：

“科克曼女生問題”1號(hào)女生存在一個(gè)1號(hào)女生十三系列解.“科克曼女生問題”2號(hào)女生存在三個(gè)2號(hào)女生十三系列解，并且1、2號(hào)女生十三系列解可以合并.

“科克曼女生問題”一組解可以通過1號(hào)或2號(hào)女生十三系列解變換出十三系列組解.

“科克曼女生問題”引申出的“6N+3”(N為自然數(shù))個(gè)的女生散步問題，都存在“6N+3”系列解.

“科克曼女生問題”是組合設(shè)計(jì)問題.“科克曼女生問題”解題三步曲和十三解系列圖應(yīng)用在醫(yī)藥試驗(yàn)設(shè)計(jì)上，醫(yī)藥試驗(yàn)設(shè)計(jì)將迎來一場(chǎng)新的技術(shù)革命.

科克曼女生問題的組解：

科克曼女生問題的組解若只考慮一周第一組的組合變化和第一天第二組至第五組的組合變化，則科克曼女生問題的組解有670269600組.若考慮全部組合變化，“科克曼女生問題”的組解約有407523916800組.

表11 科克曼15女生散步一組解

表12 “科克曼女生問題”十三系列組解

表12(續(xù))

[參 考 文 獻(xiàn)]

[1] 楊雅琴，李秋月，馬騰宇.組合數(shù)學(xué)[M].北京：國防工業(yè)出版社，2013：154-156.

[2] 范曉英.“科克曼女生問題”早已解決[N].江南時(shí)報(bào)，2002-05-19(10).