分组散步引发的一个烧脑排列组合问题

 

微信、手机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

标签: none

评论已关闭