15 個女生每天出去散步一次，每次散步三人一組。請問如何安排散步方案，可以使得一周七天內(nèi)任何兩個人恰好一起散步一次？
|
轉(zhuǎn)載自：大老李聊數(shù)學(xué) 大家好，今天的節(jié)目線索來自一位署名“牙科醫(yī)生王本材”的聽眾，他在電子郵件里說他對歷史上的一道著名數(shù)學(xué)題“柯克曼女生散步問題”（kirkman’s schoolgirl problem）進行了一些擴展研究，而且有些新的猜想，讓我看看。我以前知道有這么一個問題，但從沒深入研究。這次我就研究了一下“柯克曼女生散步問題”。不研究不要緊，一研究發(fā)現(xiàn)這個問題不但有深度，而且還有很豐富的歷史，所以就做一期節(jié)目跟大家聊聊。 話說在1850年，在英國的一本名為“女士和先生們的日記”（Layd’s And Gentleman’s Diary）的雜志中，登載了這么一個數(shù)學(xué)題： 15 個女生每天出去散步一次，每次散步三人一組。請問如何安排散步方案，可以使得一周七天內(nèi)任何兩個人恰好一起散步一次？ (上圖: 1850年的《女士和先生們的日記》雜志) 這本雜志雖然名稱聽上去有點像娛樂八卦雜志，但確實是一本數(shù)學(xué)雜志，每一期都會有很多數(shù)學(xué)趣題，而最出名的就是這道“柯克曼女生散步問題”，這個問題名稱的來源出自于出題者托馬斯·柯克曼(Thomas Penyngton Kirkman)。
托馬斯·柯克曼是歷史上一位很”不典型”的數(shù)學(xué)家，他1806年生于英格蘭的一個棉花商人家庭。他的家庭出生并不是那種很有文化背景的，14歲之前沒有接受過正規(guī)數(shù)學(xué)教育，并在這時候結(jié)束了學(xué)業(yè)到他父親的辦公室工作。 但是他發(fā)現(xiàn)自己對數(shù)學(xué)很有興趣，于是9年之后，23歲時，不顧父親反對，前往愛爾蘭都柏林的圣三一學(xué)院學(xué)習(xí)，并在27歲時終于獲得學(xué)士學(xué)位。后來返回英格蘭成為了一個教區(qū)的教長，此后便在教會工作長達(dá)50年。他始終對數(shù)學(xué)保持高度興趣，并在40歲時發(fā)表了第一篇數(shù)學(xué)論文，并逐步證明自己的能力，于1857年51時入選英國的最高學(xué)術(shù)機構(gòu)皇家學(xué)會（Royal Society），并且得到當(dāng)時英國其他的一些著名數(shù)學(xué)家的稱贊和友誼，比如凱萊(Cayley)和哈密爾頓（Hamiloton）等人，所以柯克曼是很難得的大器晚成的數(shù)學(xué)家。 今天說的這道題目“柯克曼散步問題”在當(dāng)時也是引領(lǐng)潮流的一道題，引起了組合數(shù)學(xué)研究的一陣風(fēng)潮。那讓我們先簡單分析一下這道題看看：  首先15個女生，3個人一組的話，那每天就有5組；一周的話就有5×7=35組。而每組3人如果是A、B、C的話，那么會出現(xiàn)AB, BC, CA三種兩兩組合。35組的話，就會產(chǎn)生種兩人組合。題目要求任何兩個女生恰好組合一次出去散步，那么我們計算下15人中取2人的組合數(shù)，恰好等于之前的計算。那么我們知道這道題至少是設(shè)計過的，數(shù)字是合理的。 但接下去你不必馬上開始動筆去找最終的組合結(jié)果，我相信任何人只要有中學(xué)數(shù)學(xué)程度，哪怕是死排這個組合，那么最多三天你肯定能排出結(jié)果。但是這道題如果只是純消耗各位時間，翻來覆去做排列組合那也成不了百年名題了。 有水平的聽眾肯定在想如何對這道題進行“一般化”，也就是不局限于這組數(shù)字，如果我們對所有數(shù)字組合都能找出答案，那就完美了。那要“一般化”，我們就看看這題里面有哪些參數(shù)可以改成變量。首先總?cè)藬?shù)15是一個變量，一般記作v；分成3個人一組，這個3是一個變量，一般記作b；一共出行7天，這個7是一個變量，一般記作r。還有兩個不太明顯的變量：一個是題目要求任何兩個人都恰好組合1次，但題目可以規(guī)定每兩個人恰好組合2次3次啊，所以這個“1”次也是一個變量，一般記作λ。還有前面算過一共產(chǎn)生35組，這個35，也是一個變量，記作b，所以一共有了5個變量。 但現(xiàn)在肯定有聽眾會說，你這5個變量不是獨立的啊，它們之間會有關(guān)系。比如很明顯“總?cè)藬?shù)”x“出行天數(shù)”=總的組數(shù)x每一組人數(shù)。還有一個稍不太明顯的關(guān)系，（兩人恰好組合一次的前提下，可以從前面組合數(shù)推理過程中導(dǎo)出）是：天數(shù)x(組數(shù)-1)=人數(shù)-1。以下是這兩組關(guān)系的一般形式： 既然5個數(shù)里面有兩個等式關(guān)系，那就（大致）說明確定了其中三個，可以計算出另外兩個。但是因為這5個數(shù)在討論問題過程中經(jīng)常出現(xiàn)，所以數(shù)學(xué)家還是定義了這5個變量。請大家暫時記住下，有“五變量兩等式”，在后面還會多次提到。 下面說幾個聽上去高大上的名詞，但是聽我一說也就“簡單”的不得了。首先，這類問題在數(shù)學(xué)里被稱為區(qū)組設(shè)計(Block Design），因為我們的目標(biāo)是設(shè)計出女生散步的組合，也就是“區(qū)組”或簡稱“塊”。 另外因為最終設(shè)計不需要使用到所有15人中取3人的組合，所以這叫“不完全區(qū)組設(shè)計”。再有，因為最終設(shè)計結(jié)果是高度對稱的，每個人出去散步的天數(shù)一樣，每兩個人的組合恰有一次，所以我們叫這種設(shè)計是平衡的，所以總的來說，這個問題屬于“平衡的不完全區(qū)組設(shè)計”（ Balanced Incomplete Block Design）問題，英文簡稱“BIBD問題”。 又因為柯克曼女生問題的5個參數(shù)值分別是：總塊數(shù)35，每天有15塊，總共7組，每塊3人，每兩人恰好出現(xiàn)在1塊，所以這個問題也被稱為-設(shè)計問題。再因為這5個參數(shù)之間有兩個等式關(guān)系，我們可以省略兩個參數(shù)，所以也經(jīng)常簡稱為-設(shè)計問題。有了15，3，1三個參數(shù)，另外兩個參數(shù)，35和7是可以被算出來的。
請原諒我一下子灌輸了這么多聽上去高大上的概念，但這些概念是為了后面的敘述簡便。你看問題改為-設(shè)計問題后，就容易記憶許多。原來的題目可以改成：請你給15個女生劃分出若干3個女生組成的子集，要使得任何兩個女生恰好出現(xiàn)在一個子集中。你會發(fā)現(xiàn)你的答案就只能劃分出35個子集，而且每個女生恰好出現(xiàn)在7個子集中。這意味著原本題目有兩個條件是可以隱去的，如果你認(rèn)識到這一點，那么你對原題的認(rèn)識就升華了一步。 那么我們再考慮一下如何具體去找這種劃分。用死辦法去排，當(dāng)然可以，但是有一種畫圖的方法可能簡便點。你在紙上畫上15個點，表示這個15個女生，如果有三個女生分成一組，那么你就對這三個女生連一條線，那么第一天的出行方案就需要5條線。然后你可以換一種筆的顏色，再畫5條線。如果你能用7種顏色完成著色，那么出行方案就徘出來了。 但我推薦你一開始可以只用一種顏色的筆來畫，你的目標(biāo)是畫出35條線，每條線經(jīng)過三個點，每兩個點之間有且僅有一條線。等畫出這35條線后，你再設(shè)法把它拆成7份，這種方法我覺得要簡便點。更重要的是，如果你仔細(xì)聽過大老李之前的一期有關(guān)“有限單群分類定理”的節(jié)目，你會發(fā)現(xiàn)這個畫圖過程跟那期提出過的一個問題很像！ 在那期節(jié)目里，大老李提過一個問題：請你在紙上畫7個點，然后對每3個點進行連線，要求是任何兩個點之間有且僅有一條連線。這個問題只是把15個點改成了7個點。這道畫圖題各位可以馬上試試，應(yīng)該很快能畫出來。 而且我在那期節(jié)目里說了，你畫出來的這種圖被稱為“施泰納系統(tǒng)”（Steiner System），而且人們從幾個施泰納系統(tǒng)里找出了散在單群。你別看“施泰納系統(tǒng)”這個名詞又是那么高大上，其實就是一種BIBD問題。 說到“施泰納系統(tǒng)”，簡單介紹一下施泰納（Jakob Steiner）。施泰納是與柯克曼同時代數(shù)學(xué)家，1896年出生在瑞士。跟柯克曼相似的是，他小時候也沒有得到很好的教育，沒有進過正規(guī)學(xué)校，長期幫父母務(wù)農(nóng)，甚至14歲前還不能寫字。但是他很早就表現(xiàn)出了很好的數(shù)學(xué)天賦。20歲時，他離開家鄉(xiāng)，到瑞士西南部城市伊韋爾東生活，進入由當(dāng)時的教育家裴斯泰洛齊開辦的學(xué)校中，既當(dāng)老師又當(dāng)學(xué)生。這段時間對施泰納影響很大，他對很多數(shù)學(xué)教材里的命題提出了新的證明，而且?guī)熒及l(fā)現(xiàn)他的新證明簡介簡潔又漂亮，從而都轉(zhuǎn)向使用他的證明。這使得施泰納對自己的數(shù)學(xué)才能得到了信心。 (上圖：雅各布·施泰納，1796-1863) 終于他在26歲時進入柏林大學(xué)學(xué)習(xí)了2年，之后轉(zhuǎn)為了職業(yè)數(shù)學(xué)家?？梢哉f施泰納也是有點大器晚成的數(shù)學(xué)家。在柯克曼提出他的女生散步問題的之前幾年，施泰納正好也在研究組合問題。施泰納此時研究的問題后來被稱為“施泰納系統(tǒng)”，其中最基本的研究對象就是“施泰納三元系”（Steiner Triple Systems）。 “三元系”的意思就是三個一組的意思。之前女生出行問題正好問的是三人一組。你會發(fā)現(xiàn)如果是1個人一組或2個人一組的問題都太平凡了，只有當(dāng)3個人一組，這個問題才值得研究。所以，所謂施泰納三元系就是BIBD問題中，當(dāng)分組大小為3的一類子問題。 現(xiàn)在第一個問題就是當(dāng)分組大小確定為3的情況下，總?cè)藬?shù)是什么樣的數(shù)字，可以存在施泰納三元系？之前我們提到兩個例子分別是總?cè)藬?shù)為7和15的情況，那其他數(shù)字能產(chǎn)生施泰納三元系嗎？顯然有很多數(shù)字不行。你想到的第一條就是這個總?cè)藬?shù)要滿足前面說過的：那5大參數(shù)所要滿足的2大等式，否則有些參數(shù)都不是整數(shù)，那肯定不行。所以這兩個等式肯定是必要條件。 那是不是充分條件呢？還不是。1844年，柯克曼證明了施泰納三元系存在的充分必要條件，就是總?cè)藬?shù)除以6的余數(shù)必須是1或3： 這是一個非常漂亮的結(jié)論，而且是充要條件。但是問題沒有完，存在施泰納三元系，不代表能有一個柯克曼問題中的散步方案。比如說7個人，分3人一組出行，但7除不盡3，顯然就沒有一個合適的散步方案。 柯克曼肯定是在研究過施泰納三元系之后，發(fā)現(xiàn)有些三元系還有更強的性質(zhì)，就是可以把分組結(jié)果分成數(shù)量相等的若干組，而且每一組中的元素并集恰好是全體元素。而15是滿足除3和9這兩種比較平凡的情況外，第一個滿足施泰納三元系條件，且滿足這種繼續(xù)分解條件的數(shù)字，所以他才提出了這么一道柯克曼女生散步問題！ 而后來人們把柯克曼的這種繼續(xù)分解的方案稱為“可分解的平衡不完全區(qū)組設(shè)計”（Resolvable Balanced Incomplete Block Design），簡稱RBIBD問題。而如果一個施泰納三元系，存在一種RBIBD設(shè)計，那就被稱為柯克曼三元系（Kirkman Triple System）。即柯克曼三元系的定義要比施泰納三元系的條件更嚴(yán)格，是施泰納三元系的子集。 現(xiàn)在問題又來了，怎樣的施泰納三元系可以是柯克曼三元系？這個問題比施泰納三元系的存在性問題就難非常多了。但柯克曼三元系存在的必要條件，很早人們就發(fā)現(xiàn)有兩個： 一個是總?cè)藬?shù)能夠整除3，這是顯然的。第二個是總?cè)藬?shù)是奇數(shù)，這點雖然不太明顯，但是有興趣推導(dǎo)一下還是能推導(dǎo)出來的。而兩個條件綜合起來，就是人數(shù)除以6余3，。 但再一次，以上這個條件是否就是充分條件呢？這個問題一拖就是100多年。  這里要再次介紹一位數(shù)學(xué)家，他是我國近代略帶悲劇色彩，但是絕對值得介紹和紀(jì)念的一位數(shù)學(xué)：陸家羲。陸家羲1935年出生在上海，家境貧困。1948年父親因病去世，導(dǎo)致家庭經(jīng)濟難以維持，他勉強熬到初中畢業(yè)就開始輟學(xué)。1950年進入一家五金行做學(xué)徒工。1951年考入東北電器工業(yè)管理局訓(xùn)練班，半年後以第一名成績結(jié)業(yè)，分配至哈爾濱電機廠工作，月薪64元（當(dāng)時的高薪）。
(上圖：陸家羲，1935-1983) 1957年，22歲的他自學(xué)考入東北師范大學(xué)物理系，看到一本孫澤瀛所著《數(shù)論方法趣引》，被深深吸引，特別是其中的“柯克曼女生散步問題”，改變了他人生道路。他曾說“物理是我的最愛，數(shù)學(xué)則是我的娛樂”。
1961年，陸家羲認(rèn)為他證明了柯克曼三元系的存在的充分必要條件，就是之前提到的人數(shù)除以6余3這個條件，寫了一篇題為《寇克曼和斯泰納系的制作方法》的論文，寄給了中科院數(shù)學(xué)研究所。但也許是他的論文內(nèi)容太先進了，中科院研究所過了兩年才給與答復(fù)，建議他修改后重新投稿其他單位。 陸家羲對自己的證明是充滿信心的，于是1963年和1965年兩次重寫他的論文發(fā)給了《數(shù)學(xué)通報》和《數(shù)學(xué)學(xué)報》兩本刊物，但都杳無音訊。到1966年，由于眾所周知的原因，中國的所有科學(xué)研究繼續(xù)都陷于停滯。 6年后，1972年，陸家羲結(jié)婚，育有一女，讓他的生活有了點色彩。又過了7年，1979年，陸家羲借到了兩本1974年和1975年出版的國外的組合數(shù)學(xué)權(quán)威刊物《組合論》（Combinatorics），發(fā)現(xiàn)國外有人（Ray-Chaudhuri and Wilson）已經(jīng)在1971年和1975年分別解決了柯克曼三元系存在性的充要條件問題以及推廣到n元組的情況。這對陸家羲的打擊太大了，因為即使從1971年開始算，這也比他的發(fā)現(xiàn)晚了7到10年。 但是陸家羲并不灰心，他在國外研究者的基礎(chǔ)上進一步拓展了問題，并取得了突破。于是他直接寫了篇英文論文，寄給了美國的這本《組合論》雜志。1981年，他又寄了3篇論文給《組合論》雜志，都得到出版。這些論文得到了國外同行的高度評價。加拿大多倫多大學(xué)教授門德爾遜說：“這是二十多年來組合設(shè)計中的重大成就之一。” 多倫多大學(xué)校長還邀請陸家羲到多倫多大學(xué)任職，而此時陸家羲還只是包頭一所中學(xué)的物理老師。 經(jīng)過國外同行認(rèn)可后，陸家羲終于也被中國學(xué)術(shù)界認(rèn)可。1983年10月，他成為唯一被特邀的中學(xué)教師參加了在武漢舉行的第四節(jié)中國數(shù)學(xué)年會。大會充分肯定他的成就，表彰他勇攀數(shù)學(xué)高峰的奮斗精神。會議結(jié)束后，為了返校上課，他隨即返回包頭家中?；丶液缶团d奮地對妻子說“這次可見過大世面了”。10月30日晚飯后，和家人聊了一下便說“太累了太累了，明天再講，早些休息吧”。積久的疲勞，和長期潛伏的疾病已遠(yuǎn)遠(yuǎn)超過他生理所能承受的極限。當(dāng)晚凌晨1時許，心臟病突發(fā)，猝然與世長辭，未留下一句遺言，年僅48歲。 1987年，陸家羲被追授了國家自然科學(xué)獎一等獎。陸家羲的身世讓人唏噓長嘆，我們只能思考如何不讓這種悲劇重演。 那我們再回到柯克曼三元系的存在性問題，前面提到了柯克曼三元系存在的充分必要條件就是人數(shù)除以6余3。接下來你可能還想問四元系和五元系等等的存在性問題。我可以簡單匯報一下：長期以來對是否存在無窮多個施泰納4元和5元系，一直不能解決。但2014年，Peter Keevash 的一篇論文中給出了一個積極的答案。而是否存在6以及以上的“非平凡”的施泰納系統(tǒng)，更是區(qū)組設(shè)計問題中長期未解決的難題。施泰納系已經(jīng)那么難，那一般的柯克曼系的問題也更不用提了。
最后再看看這位王本材聽眾郵件里提出的問題：他問的是如果有 有個學(xué)生，n個人一組，那么一天里面就有n組。那需要走多少天呢？對某個學(xué)生來說，他出去散步一次，他可以認(rèn)識n-1個其他學(xué)生。那么n+1天后，他可以認(rèn)識 那我們再檢查下一下，n+1天的方案里是否滿足每兩個學(xué)生恰好出去散步一次。這部分留給聽眾驗證，但結(jié)論是合理的。所以我們知道這位聽眾考慮的問題中，數(shù)字設(shè)定是合理的！ 數(shù)字設(shè)定合理，我們就可以考慮一下怎么構(gòu)造方案。如果n=3，那么這個問題就是柯克曼三元系的問題，而9除以6余3，符合柯克曼三元系存在的充要條件，所以我們確定9個人是肯定有4天的散步方案的。 9個人（用0-8表示），四天的散步方案： Day 1 Day 2 Day 3 Day 4
而n>3之后，問題一下子很難。但還好有人做了軟件，把已知的可以構(gòu)造的BIBD設(shè)計都存好了。所以我就用軟件考察了一下n=4-10的情況。發(fā)現(xiàn)4到9之間，除了6以外，所有的BIBD設(shè)計都找到了，但是RBIBD設(shè)計，也就是構(gòu)造出散步方案的話，只有n=4的情況找出來了。而對n=10的情況，是否存在BIBD設(shè)計還是未知的。 (n^2,n,1設(shè)計中，施泰納系和柯克曼系存在情況： n 施泰納系 柯克曼系
而這位王本材聽眾確實提到了，他認(rèn)為n=6的時候是無解的。他還對哪些n能構(gòu)造出柯克曼系(RBIBD設(shè)計）做了猜想。但目前找到的的RBIBD設(shè)計過少，所以我無從對他的猜想評價。但總體上他找的這組數(shù)是合理的，他也確定6是無解的，說明他是有一定研究的。我覺得現(xiàn)在可以考慮的是設(shè)法構(gòu)造出n=5，也就是25個男生，5人一組，散步6天的方案，或者證明它不存在，這將是一個新發(fā)現(xiàn)。當(dāng)然10以內(nèi)除了6都可以嘗試。 我非常感謝這位聽眾給我發(fā)的這封郵件，讓我了解了柯克曼女生散步問題，這個問題可以用“出乎意料”、“別有洞天”來形容。說出乎意料是因為它表面上是一道平淡無奇的排列組合題，但是深入挖掘下去內(nèi)容是如此博大精深，完全出乎意料。我這期節(jié)目是我比較長的節(jié)目了，但我節(jié)目里說的內(nèi)容大概只有我閱讀材料的1/10。說“別有洞天”是因為這個問題牽涉的問題很廣，比如歐拉方、矩陣、仿射幾何、數(shù)域、群等等，這些都只能留給有興趣的聽眾研究了。 另外，這道題牽涉的三位數(shù)學(xué)家都有點自學(xué)成才，大器晚成之感。陸家羲的個人歷史悲劇值得我們思考，如何使其不再重演。 最后，我可以出一道簡單的思考題，看看大家對今天節(jié)目理解多少： 請你考慮下，有21個女生，分別按3人、7人分組，僅從數(shù)值上分析，能否找出BIBD設(shè)計？進一步，是否存在柯克曼的散步設(shè)計？ 好了，今天節(jié)目到這，下期再見！ 在喜馬拉雅FM收聽：”大老李聊數(shù)學(xué)” |
|
|
或
