組合學專題

—從“柯爾曼的女生問題”談起

Kirkman’s schoolgirl problem（T. P. Kirkman 1847）

90.9.13                                              大陸 康廣德教授 演講

                                                         王安蘭老師  整理

 

(一)在英格蘭有一位Thomas Penyngton Kirkman為英格蘭教會的教區長，寫了一本刊物，名為＜Lady’s and Gentleman’s Diary＞，由它的名字可能看不出它是一本數學刊物，會讓人以為只是一些人茶餘飯後的消遣的話題及內容，但其實這是數學在生活中的珠璣。

 

    在西元1847年，這本刊物提及一個英國教會學校中發生的事件：“一位女老師在課後晚自息結束時，帶了15位女學生在林間散步，因老師管束嚴格，故15位女學生被要求排成五列三行，同一列的3人可互換位置聊聊天，但列與列間不可互換交談；如何排出一週7天，每天晚上不同的排列方法，但使任何二位同學皆有機會同行”。

 

    考慮這個問題，先看人數和天數的合理性：

∴一天就有15對，7天共15．7＝105對

二者數量相同，∴一週七天的排列可使每2人皆有依次相處的機會。

 

    Kirkman在刊物中徵求“誰能幫這位女老師做出這一星期的隊伍排列表？”

但做出，一年後Kirkamn公佈答案如下表：

 

(二)由於Kirkman的女生問題，引起一些喜愛數學的人之興趣，在1850年，當時有名的數學家Jame’s Josepti Sylvester和Arther Cayley二人將此問題擴展：“請你排出13週的名單，每週都要符合原來的要求（即15位學生中每2人都恰有一次在同一列），但這13 週內不許有相同的列（即任何一列的3人在這13週內恰出現1次）”。

 

    同樣考慮這個問題數字的合理性，為何要求是13週，而不是其他週數呢？

∵一天5列，每列為一三元組，一週有5．7＝35個三元組

∴13週共有5．7．13＝455個三元組

因數量的合理性，可達成不重複的要求。

    Sylvester和Cayley提出的這個問題，困難度提高許多，一值延伸120多年無人解決，直到1944年美國數學家R.H.F. Denniston才借助電子計算機，解決了此問題。

 

    這裡的15個女學生標記為a,b,0,1,2,…,12；13週的標記為i＝0,1,2,…,12。

    而數字的加法均以模13來取值。

 

(三)為何Kirkman女生問題中要用“15”這個總數？可不可以換別的數？什麼樣的庶事可行的？

    “9”是一個可以考慮的數字.

例如：9位女生走200公尺的跑道，要求她們排成三列，每列3人，每走完一圈就換隊形.

∴欲使任二人皆有一次在同一列，必須要走完4圈才有可能.

一天走完四圈，共有3．4＝12個三元組.*    84÷12＝7

∴欲使一列3人的所有組合恰出現一次，需要7天才可完成.

    故可仿Sylvester和Cayley的問題設計一問題.

    “你如何安排7天的隊形，使9位女生每天走4圈，而在每天中每2人恰有一次在同一列，但這一週內任合一列的3人恰出現一次.” 以下為仿Kirkman的問題，排出1天4圈的隊形.

 

(四)(一般化系統建立)

(1)設x為一個v元集.A是x的一些「子集」，它們滿足某種「條件」時，稱（x, A）為一個區組設計.

   上述科克曼問題之一般性建立為

     從v元集點集中取出若干個3-子集，構成一個系統，須滿足v元集中任一個2-子集恰出現在某個“取出的”3-子集中，則稱此為STS(v) （steiner triple system 斯坦那三元系）

 

例如：下塗給初一個STS(7)，它有7個區組（7個3-子集），分別是正三角條邊、三調高線和內切圓周.

       圖中，內切圓切點、三邊頂點，及三高之共典型成7個點，分別標上0∼6的數字，此即一7元集（v＝7）.

       7個3-子集 {1, 4, 2}，{2, 5, 3}，{3, 6,1} （三邊）

                  {1, 0, 5}，{3, 0, 4}，{2, 0,6} （三高）

                  {4, 5, 6}                  （圓周）

                 

                  

      

 

(2)區組集&可以分拆為幾個(平行)類，每類中的全部區組都恰好是v元集x的一個分拆則稱為可分解，一個可分解的STS(v)，記為KTS(v)

  （ps.如STS中所有的3-子集，彼此都無重複是用相同的數，將v元集中的每個數恰好完全分割，稱為一平行類，而上例之STS(7)中，非一平行類，故非KTS(7)）.

  例如：開始提到的科克曼女生問題的解答就是一個KTS(15)

       

          一星期7天，每天5列3人的隊形，共有7×5＝35個3-子集.

         

        (ii)一星期7天，每天的隊形即為一平行類.

          即其解答共由35個3-子集構成可分拆為7個平行類，而每個平行類含5個區組（3-子集）

  再舉一例前面所舉“9位女生走200公尺的跑到，要求排成三列，每列3人，走完一圈就換隊形，1天走4圈，而在每天中每3人恰有一次在同一列．．．”，1天4圈的隊形即為一KTS(9).

 

   而每圈為一平行類.

 

  ps.STS(v)中要夠成一個平行類，3︱v是必要的.故3︱v才有可能為KTS(v)

    但並非3︱v集存在KTS(v)，例如KTS(12)不存在.

 

(3)設（x, A）為某種區組設計，（不妨稱為C-區組設計），A由x的一部份C-「子集」分拆為若干個類Ai，便得每個（x, Ai）都恰好是一個C-區組設計，則稱這些（x, Ai）構成一個C-區組設計的大集.

  現來看看：斯坦那三元系的大集情況

 

 

因此若存在v階斯坦那三元系大集（常記為LSTS(v)），則它應由v－2個兩兩不相交（即無公共的3-子集）的STS(v)構成.

同樣KTS(v)可擴展為LKTS(v)

∴Sylvester和Cayley將科克曼問題擴展為13周，此解即為LKTS(15)（13個KTS(15)構成一個LKTS(15)），而“9位女生走200公尺跑道．．．”之例，排出一星期7天，每天4圈之隊形，解即為一LKTS(9)（7個KTS(9)構成一個LKTS(9)）

但7個幾何上的點可成STS(7)之例，就不能成為一LSTS(7).

 

(4)一些已發表之結果

  (i)科克曼和M.Reiss早就各自獨立證明了

    STS(v)存在  v≡1或3（mod 6）.

 

  (ii)Cayley證明了最多只有2個區組不相交的STS(7)，即LSTS(7)不存在.

 

  (iii)1973  L.Teirlmck證明 LSTS(v) → LSTS(3v)

     1975  A.Rosa   證明 LSTS(v) → LSTS(2v+1)

     這兩個漂亮的結果將遞歸構造方法引入到大集的研究工作中.

 

  (iv)1983∼1984 一位名不見經傳的小人物，中國包頭九中的物理教師陸家羲在經過20多年的艱苦奮鬥後投稿＜Journal of Combinatorial Theory＞公佈了如下的大集定理

     “對於v≡1, 3 (mod 6)，v＞7除去v＝141, 283, 501, 789, 1501, 2365這六個未定的階數外，階存在LSTS(v)”.

 

(五)介紹陸家羲先生的生平.

1935年    6月出生在上海市，家境貧苦.

1948年    父親因重病去世，是家庭沉重的打擊，勉強讀到初中畢業，被迫輟學.

1950年    在上海公興汽車五金材料行當學徒，承擔生活重壓.

1951年    考入東北電器工業管理局訓練班，半年後以第一名成績結業，分配至哈爾濱電機場工作，月薪64元（當時是非常高薪）

1957年    自學考上東北師大物理系，讀孫澤瀛所著的「數學方法趣引」，非常喜好而沉浸其中.最吸引他的是“柯克曼女生問題”，也改變了他日後的生活道路.他說：物理是我的最愛，而數學是我的娛樂。

1961年    12月30年將“柯克曼系列與斯坦那系列的構造方法”一文寄至中國科學院數學研究所，一年多後被退回，告知“結果如果是新的，可以直接投稿給＜數學通報＞等刊物”.

1963年    將論文改寫，3月12日投寄＜數學通報＞，一年後答覆“由於篇幅較長，和所用的數學工具，建議令投其他刊物”，又被退回.

1965年    雖幾經挫折，但他對自己的論文卻充滿信心，他又跑遍市內所有圖書館給論文增添新內容，改寫後，取名“平衡不完全區組與可分解平衡不完全區組的構造方法”，3月14日投寄給＜數學通報＞，而這段時間他因頻繁的工作調動，無法專心研究且因他默默工作，很少予人交往，周圍人們無法理解，受到非議.白眼和冷潮熱諷，給他精神上很大的壓力.而這篇論文又在1966年2月被退回.美號稱在1974年以解決的柯克曼擴展問題，其實在他的這篇文章中已解決.

1972年    結婚.婚後生了一個女兒改變了他的生活，使他充滿了生活的興趣.女兒使他的人生有了色彩，性格也漸漸開朗.

1979年    4月他借到1974年和1975年美出版的世界組合數學方面的權威性刊物＜組合論雜誌＞意外發現：柯克曼問題以及推廣到四元組系列的情況，國外已於1971和1972年解決了.這事實對他打擊太大了.這些結果比他的發現還晚了7∼10年，而他的稿子至今還無著路.無論如何，國外發表的時間上是領先了.但他不氣餒，認為自己過去的工作室有意義的.但他擔心的是要是又有新作品又將怎樣呢？

          10月他的研究又有重大突破，寄給＜組合論雜誌＞.

1981年    9月18日起陸續寄“論不相交斯坦那三元系大集”系列文章至＜組合論雜誌＞，令許多西方組合論專家驚訝“這是二十多年來組合設計中的重大成就之一”.

1983年    10月他成為唯一被特邀的中學教師參加了在武漢舉行的第四屆中國數學年會.大會充分肯定他的成就，表彰他勇攀教學高峰的奮鬥精神.會議結束後，為了返校上課，隨即返家.回家後就興奮對妻子說“這次可見大世面了”，晚飯後，和家人聊了一下便說“太累了太累了，明天再講，早些休息吧”.積久的疲勞，和長期潛伏的疾病已遠遠超過他生理所能承受的極限.當晚凌晨1時許，心臟病突發，猝然與世長辭，未留下一句遺言.

 

他的成功完全是靠自己苦讀，興趣及毅力支撐而來的，而他的長才是通過外國學者提出才引起重視，否則他可能還是依然貧病交迫，埋沒以終.怎樣避免這類事件再一次出現，值得深思.