當前位置:編程學習大全網 - 編程語言 - 科克曼女生問題的問題的推廣

科克曼女生問題的問題的推廣

這壹問題更壹般的推廣是:怎樣把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,對許多這種區組設計都有這種大集問題。而西爾維斯特問題則是區組設計大集問題的最早淵源 。

盡管這種設計的大集問題提出得很早,但由於它的可分解性難度,這壹課題的研究至今進展很小。中國學者陸家羲等在這方面做出了壹些成功突破[7]。

顯然,對於給定的正整數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世紀組合學領域的重大成就之壹。但是,科克曼三元系大集的存在問題則更為困難。可惜陸家羲因為積勞成疾而英年早逝,來不及深入研究這些工作。

“女生問題”引出了組合數學的壹個重要分支——組合設計,這也是組合數學起源於數學遊戲的壹個佐證,對這些數學遊戲,壹旦當人們認識到它們在數學和其他科學上的深刻含義後,便又促使人們對它進行更深入的研究,從而豐富了數學學科的內容和知識。

  • 上一篇:急求C語言高手編程 80積分!謝謝~好心人幫下小女子吧..
  • 下一篇:什麽品牌變頻器質量好?
  • copyright 2024編程學習大全網