“科克曼女生問題”的探討

諶義才

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

1 引 言

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

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

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

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

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

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

2.1 選一周的1號女生組合

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

2.2 選一周的2號女生組合

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

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

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

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

表1 科克曼1，2號女生組合散步表

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

2.3 其它三人組組合的選擇

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

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

從表2組合中可以看出幾個特點：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表6 “科克曼女生問題” 1號女生十三系列解

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

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

表9 “科克曼女生問題” 2號女生十三系列解之三

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

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

6 “科克曼女生問題”組解的計算

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

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

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

表10 “科克曼女生問題”組解計算

7 “科克曼女生問題”組解的應用

“科克曼女生問題”的組解在醫(yī)藥試驗設計上得到廣泛運用.在滿足“科克曼女生問題”題意的前提下，可以對兩個號任意組合，隨意而動.就象練氣功一樣，意到那里氣就到那里.茲舉“科克曼女生問題”一組解(見表11).從表11中看1號組合和2號組合，其組合方式就象2條巨龍在那里舞動.

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

8 結(jié) 論

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

第一步，選一周第一組的1號組合7個.

第二步，再選一周第二組的2號組合6個.

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

注 亦可以任意選擇2個號進行組合(7+6)個，再確定其余22組組合位置.

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

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

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

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

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

科克曼女生問題的組解：

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

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

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

表12(續(xù))

[參 考 文 獻]

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

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