1850年，英國神甫科克曼在《女士與先生之日記》雜誌上發表了題為的文章，提出了15個女學生問題：一位女教師每天帶領班上的15名女生去散步，她把這些女生按3人一組分成5組，問能不能作出一個連續散步7天的分組計畫，使得任意兩個女生曾被分到一組且僅被分到一組，也就是說，隨便從15人中挑出2人，她倆在一周所分成的35個小組裡必在一組中見過一面，且僅見一面。
基本介紹
- 中文名：科克曼女生問題
- 外文名：Kirkman's Schoolgirl Problem
- 提出時間：1850年
- 發表地點：《女士與先生之日記》
- 相關人物：科克曼
提出者,影響,問題的解答,問題的推廣,一般的推廣,三元系,
提出者
科克曼（Thomas Penyngton Kirkman，1806－1895），1806年3月31日出生於英格蘭的波爾頓，他在一個沒有學問的商人家庭中長大，曾為受到較好的教育奮鬥過，但他甚至沒有受到任何水平的數學教育，他於1833年在都柏林大學獲得藝術學位，被派到英格蘭教會，成為一個教區的教區長，達五十年之久。
科克曼女生問題
科克曼女生問題這個饒有趣味的遊戲在一些數學家的介紹、研究和推廣下很快在許多國家流傳開來。科克曼本人給出了一個解，後來發現，科克曼給出的解並不是他所提出問題的唯一答案。
影響
事實上，過了一百多年，到1974年，這一問題由德尼斯頓藉助於電子計算機得到解決。科克曼女生問題激起了興趣的浪潮，吸引了許多數學家，推動了組合數學的發展。
問題的解答
這個是組合數學裡的問題。
解決這一問題並不很困難，凱萊首先給出了一個答案，然後科克曼發表了他自己的答案，當然在他提出這一問題時他就已經知道了答案。西爾維斯特（J.J.Sylvester）對這一問題也有研究，後來他就誰先想到這一問題與科克曼有過爭論。
科克曼在同一刊物上公布了他自己給出的一個答案如下（1至15代表15個女生）：
星期日 {1, 2, 3}，{4, 8, 12}，{5, 10, 15}，{6, 11, 13}，{7, 9, 14}；
星期一 {1, 4, 5}，{2, 8, 10}，{3, 13, 14}，{6, 9, 15}，{7, 11, 12}；
星期二 {1, 6, 7}，{2, 9, 11}，{3, 12, 15}，{4, 10, 14}，{5, 8, 13}；
星期三 {1, 8, 9}，{2,12,14}，{3, 5, 6}， {4, 11, 15}，{7, 10, 13}；
星期四 {1, 10, 11}，{2, 13, 15}，{3, 4, 7}，{5, 9, 12}，{6, 8, 14}；
星期五 {1, 12, 13}，{2, 4, 6}，{3, 9, 10}，{5, 11, 14}，{7, 8, 15}；
星期六 {1, 14, 15}，{2, 5, 7}，{3, 8 ,11}，{4, 9, 13}，{6, 10, 12}。
這個解是一個15階科克曼三元系，其中v=15，k=3，λ=1。科克曼不但解決了斯坦納三元系的存在性問題，同時還對r的每個素數值，給出了參數為v=r2+r+1，k=r+1，λ=1的2-設計，即現稱作的有限射影平面。他套用循環差集構造r=4、r=8的射影平面，也發現參數為v=2n，k=4，λ=1的3-設計和其他幾種特殊的設計。可以說，科克曼是組合設計之父。
問題的推廣
一般的推廣
這一問題更一般的推廣是：怎樣把n個女學生分成n/3組，使得在每(n－1)/2天內任意兩個女生在同一組內只相遇一次。顯然如果這樣的n存在，那么定有n≡3(mod6)。直到1971年，滿足這個條件的n的存在性問題才得以證明。
科克曼當時的工作並未引起人們的重視，直到1853年，幾何學家斯坦納在研究四次曲線的兩切線問題時再次提出了這一組合問題，並在克雷爾雜誌上發表一文重新指出這種三元系存在的必要條件是n≡1，3(mod6)，此處不考慮分成n/3組，三元系的問題才引起學者的注意。1859年，賴斯（M.Reiss）證明了這一猜想。但由於當時信息不靈，他們並不知道英國的數學家對此問題已先行一步。早在1844年，就有數學家已提出了B(3,1，v)的情形，而科克曼已於1847年證明了賴斯在12年後才得到的那個結論。由於這一原因及斯坦納當時的聲望，B(3,1，v)一直被稱為斯坦納三元系，並將一般的B(k,1，v)稱為斯坦納系。
對於一般的平衡不完全區組設計BIBD（balance incomplete block design）的研究中，費舍爾（R.A.Fisher）和葉斯（F.Yates）在1938年的一本著作中給出了一個B(k ,λ，v)的各個參數間滿足的基本關係式：rv=bk與 r (k－1)=λ(v－1)，其中r表示每個區組中都含有r個元素，b表示全部的區組個數。顯然，這是一個B(k ,λ，v)存在的必要而非充分條件。1940年，費舍爾又得到了B(k ,λ，v)存在的一個限定條件，即費舍爾不等式b≥v。
三元系
給出和證明B(k ,λ，v)存在性的充要條件是很困難的。三元系在被提出後，又經過約100年的探索，直到1961年才由哈納尼（H. Hanani）證明了下面的（1）式確是B(3,λ，v)設計存在的充分條件，同時他還指出這也是B(4,λ，v)設計存在的充分條件。
λ（v-1）=0（mod2）
λv（v-1）=0（mod6）
當k≥5時，問題變得複雜了，對每個指定的k≥5，都滿足（1）式但卻不存在B(k, λ， v)的(v,λ)數值組。1975年，威爾遜 (R.M.Wilson)證明了："對給定的正整數k和λ，除去有限個正整數v以外，（1）式是B(k,λ，v)存在的充要條件。"[5]其中v≥k。這一結論宣告了B(k,λ，v)存在性問題的基本解決。
用現代術語來說，科克曼女生問題實際上是一個可分解的平衡不完全區組設計RB(3,1，15)。一個B(k,λ，v)設計（X，λ），其區組集?墜可分成若干個"平行類"，平行類是指?墜中的一些區組，這些區組恰好構成了集合X的一個分拆。那么尋求RB(k, λ，v)存在的充要條件也成為組合設計發展中的一個難題。對於RB(3,1，v)現常稱作科克曼三元系，它的存在性問題曾是歷史上一個著名難題。這個問題從提出到解決，歷時100多年。確定RB(k, λ，v)設計存在的必要條件是容易的，即
v≡0（modk）
λ（v-1）≡0（mod（k-1））
同樣，數學家也想知道（2）式是否是RB(k, λ，v)存在的充要條件？由於"可分解性"條件的難度，這方面的進展很慢。
對於k=3，λ=1的情形，即科克曼三元系，直到1972年才由雷·喬得赫里（D.K.Ray-Chaudhuri）及威爾遜證明了RB(3,1，v)存在的充要條件即是（2）式成立，此時（2）式成為 v≡3(mod6)。1972年，哈納尼與上述兩位數學家合作證明了（2）式也是RB(4,1，v)存在的充要條件，此時v≡4(mod12)。對於這兩項結果，中國學者陸家羲於1961年就已得到，只因投稿未登而失去了這方面的優先權。至此，科克曼女生問題，亦即科克曼三元系的存在性問題得到完全解決。
西爾維斯特和凱萊在科克曼發表"女生問題"的研究之後，便對這一問題提出了一個進一步的要求，即"希望給出一個連續13周的佇列安排，使得不但每周內的安排都符合原來的要求，還要讓任意3名女生在全部13周內恰有一天排在同一組"。
"西爾維斯特問題"
這是在"女生問題"基礎上出現的一個難度更大的問題，後稱之為"西爾維斯特問題"，可簡述為：對於任意可以構造的女生散步方案v，是不是總可以得到v－2個沒有相同三元組的方案來。西爾維斯特問題引出區組設計的大集問題。
這一問題直到1974年才由美國的丹尼斯頓（R.H.Denniston）藉助電子計算機得以確證，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，...，12，而數字i=0，1，2，...，12。每取i的一個值，所列的5×7個區組就給出了所求的隊形安排。
在這個答案中，每周的安排都是一個RB(3，1，15)，而這13個RB(3，1，15)都在同一個集合上，彼此的區別只在於任何兩個之間都沒有共同的區組（任意3人同行僅1天）。不難算出，15個人中的3人組共有C15=13×35，每周7天，每天5個3人組，總共13周恰好把全部的3人組都安排了一次。像這樣的一種大的安排被稱為是RB(3，1，15)的一個大集。不僅對於RBIB，對許多這種區組設計都有這種大集問題。而"西爾維斯特問題"則是區組設計大集問題的最早淵源。
儘管這種設計的大集問題提出得很早，但由於它的可分解性難度，這一課題的研究至今進展很小。中國學者陸家羲等在這方面做出了一些成功突破。
顯然，對於給定的正整數n，若存在斯坦納三元系（或科克曼三元系），用D(n)（或Dk(n)）表示各自大集的三元係數，則因為n元集的3-子集共有Cn個，而一個三元系包括n(n-1)/6個3-子集，於是有D(n)≤n-2（或Dk(n) ≤n-2）。
三元系的大集問題
所謂的三元系的大集問題就是，是否對所有的n ≡1，3（mod6）且n >7，都有D(n)=n-2？是否對所有的n ≡3（mod6），都有Dk(n) =n-2？如上所述，直到1974年才構造性地證明了Dk(15) =13，可見問題的困難及進展之緩慢。
1981年9月至1983年4月，美國《組合數學雜誌》收到了陸家羲的六篇論文。文章宣稱，基本上解決了斯坦納三元系的大集問題。事實上，陸家羲證明了如下結果：若n≡1，3（mod6）且n>7，且n≠141，283，501，789，1501，2365，則D(n)=n-2。這被譽為20世紀組合學領域的重大成就之一。但是，科克曼三元系大集的存在問題則更為困難。可惜陸家羲因為積勞成疾而英年早逝，來不及深入研究這些工作。
“女生問題”引出了組合數學的一個重要分支——組合設計，這也是組合數學起源於數學遊戲的一個佐證，對這些數學遊戲，一旦當人們認識到它們在數學和其他科學上的深刻含義後，便又促使人們對它進行更深入的研究，從而豐富了數學學科的內容和知識。
