分組散步引發的一個燒腦排列組合問題

原文作者：Marianne Freiberger，此文原載於+Plus Magazine網站。

翻譯作者：333，哆嗒數學網翻譯組成員，就讀於中南大學數學專業。

稿件校對：donckeycn

投稿可發至郵箱1178853280@qq.com，詳情參見徵稿說明。

微信、手機QQ搜索關注DuoDaaMath每獲得更多數學趣文

新浪微博：http://weibo.com/duodaa

如果你曾經製作過時間計劃表或者之類的東西，你就會知道這不是一項輕鬆的工作——這也就是為什麼組合數學，一門根據特定的規則設計東西的藝術，能夠在數學世界中佔有一席之地的原因。最近，正是在這個領域，數學家們有了一些突破。他們發現了一些很多人覺得根本不存在的特殊設計。這些設計所包含的結構非常抽象，但是它們在通訊技術領域很可能大有用處。

理解這一新發現最好的方式是從一個有趣的益智題開始。假設你有一組人，人數為9。每天他們以三個人為一組出去散步。你能做出合適的安排，以保證在四天的散步中任意兩個人同組的次數不超過一次嗎？

它構成了所謂的斯坦納三元系：把n個對象（在這個例子中，n=9，對象是人）安排進一些三元組，以使得任意兩個對象同組的次數不超過一次。上圖顯示了一個S(2,3,7)的斯坦納系，有7個點和7條線（我們把中間的圓也當作一條線），每條線包含3個點，每兩個點只同時出現在一條線上。換句話說，這些線就給出了這7個點滿足上述條件的三元組。更一般地，一個斯坦納系S(t,k,n)是指將n個對象安排進一些k元組，並滿足任意t個對象在同一個k元組中出現的次數不超過一次（譯註：原文為「不超過一次」，但根據「斯坦納系」的定義，應為「恰好一次」）。

你會問一個很自然的問題：t,k,n取哪些值的時候，存在斯坦納系？很明顯，並非所有的數的組合都能夠使系存在。事實上的確如此，我們有一個可除性條件：一個由t,k,n的值所確定的斯坦納系S(t,k,n)能夠存在，t,k,n必須要滿足可除性條件（如圖所示）。一個重要的結果來自於2014年數學家Peter Keevash的工作，這一結果表明當n充分大時，可除性條件是足夠好的：如果n足夠大，且t,k,n滿足可除性條件，那麼一個S(t,k,n)斯坦納系必定存在。

這一結果包含了斯坦納系的一個推廣。讓我們不再去想n個抽象的對象，而是考慮一個由0和1組成的長度為n的字元串（計算機使用這樣的字元串，這表明它和信息技術有關聯）。對於n=3,這樣的字元串有(1,1,1)和(1,0,1)等。對於一個給定的n，所有這樣的字元串的集合構成了一個向量空間（此處我們不詳述向量空間定義的細節，讀者可以參閱任何一本關於線性代數的書）。讓我們把這個向量空間記作F(2,n)：2表明在我們的字元串中所出現的不同的符號只有兩個（0和1）；n表明字元串的長度。每個向量空間都有一個維數，在這裡，維數就是n，即字元串的長度。

正如一個n元集合有子集，一個n維的向量空間也有維數小一些的子空間。這導致我們思考一個類似於斯坦納系的問題：給定一個向量空間F(2,n)，數字t和k，你能找出F(2,n)的某些k維子空間，使得F(2,n)的每一個t維子空間都只包含於其中的一個k維子空間中嗎？如果這樣的系存在，我們稱其為S(2;t,k,n)。（用數字2也是有可能構成一個向量空間的，數字2在我們的這個例子中告訴我們字元串只由兩個符號構成，用別的數q代替2，我們記這樣的向量空間為F(q,n)，與之相關的斯坦納系統記作S(q;t,k,n)）

直到最近，數學家們都認為大家關心的形如S(q;t,k,n)形式的系的具體例子並不存在。不過，Michael Braun, Tuvi Etzion, Patric R.J. ?sterg?rd, Alexander Vardy 和Alfred Wassermann實力打臉，他們把這個預言證否了。特別的，他們找到了S(2;2,3,13)形式的幾個不同的系。

「尋找過程充滿挑戰，因為所涉及的結構數目巨大，」 Ostergard說，「即使是在高性能計算機的幫助下，尋找它們也是一項艱苦的行動。因此，除了使用代數技巧和計算機，我們也得運用自己的經驗去猜測從何處開始搜尋，以縮小搜索的範圍。」

數學家們會很高興，因為這一結果解決了一個長期屹立不倒的問題。然而，這個結果還有一個令人驚訝的實際用處。通訊行業嚴重依賴於糾錯碼：這個想法是給信息用某種方式編碼，使其即使在傳輸過程中產生了錯誤，這些錯誤也能被自動消除。結果證明，S(2;2,3,13)系統給某種特別的糾錯技術提供了最優的編碼。「我們的發現並不能直接變成產品，但是它或許將逐漸成為網際網路的一部分。」 Ostergard說道。最新結果已在Forum of Mathematics, Pi發帖（劍橋大學出版社網站的數學論壇）。

微信、手機QQ搜索關注DuoDaaMath每獲得更多數學趣文

新浪微博：http://weibo.com/duodaa

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！