关于女生的数学问题：柯克曼女生散步问题

大家好，今天的节目线索来自一位署名“牙科医生王本材”的听众，他在电子邮件里说他对历史上的一道著名数学题“柯克曼女生散步问题”（kirkman’s schoolgirl problem）进行了一些扩展研究，而且有些新的猜想，让我看看。我以前知道有这么一个问题，但从没深入研究。这次我就研究了一下“柯克曼女生散步问题”。不研究不要紧，一研究发现这个问题不但有深度，而且还有很丰富的历史，所以就做一期节目跟大家聊聊。

话说在1850年，在英国的一本名为“女士和先生们的日记”（Layd’s And Gentleman’s Diary）的杂志中，登载了这么一个数学题：

15 个女生每天出去散步一次，每次散步三人一组。请问如何安排散步方案，可以使得一周七天内任何两个人恰好一起散步一次？

这本杂志虽然名称听上去有点像娱乐八卦杂志，但确实是一本数学杂志，每一期都会有很多数学趣题，而最出名的就是这道“柯克曼女生散步问题”，这个问题名称的来源出自于出题者托马斯·柯克曼(Thomas Penyngton Kirkman)。

托马斯·柯克曼是历史上一位很”不典型”的数学家，他1806年生于英格兰的一个棉花商人家庭。他的家庭出生并不是那种很有文化背景的，14岁之前没有接受过正规数学教育，并在这时候结束了学业到他父亲的办公室工作。

但是他发现自己对数学很有兴趣，于是9年之后，23岁时，不顾父亲反对，前往爱尔兰都柏林的圣三一学院学习，并在27岁时终于获得学士学位。后来返回英格兰成为了一个教区的教长，此后便在教会工作长达50年。他始终对数学保持高度兴趣，并在40岁时发表了第一篇数学论文，并逐步证明自己的能力，于1857年51时入选英国的最高学术机构皇家学会（Royal Society），并且得到当时英国其他的一些著名数学家的称赞和友谊，比如凯莱(Cayley)和哈密尔顿（Hamiloton）等人，所以柯克曼是很难得的大器晚成的数学家。

今天说的这道题目“柯克曼散步问题”在当时也是引领潮流的一道题，引起了组合数学研究的一阵风潮。那让我们先简单分析一下这道题看看：

首先15个女生，3个人一组的话，那每天就有5组；一周的话就有5×7=35组。而每组3人如果是A、B、C的话，那么会出现AB, BC, CA三种两两组合。35组的话，就会产生种两人组合。题目要求任何两个女生恰好组合一次出去散步，那么我们计算下15人中取2人的组合数，恰好等于之前的计算。那么我们知道这道题至少是设计过的，数字是合理的。

但接下去你不必马上开始动笔去找最终的组合结果，我相信任何人只要有中学数学程度，哪怕是死排这个组合，那么最多三天你肯定能排出结果。但是这道题如果只是纯消耗各位时间，翻来覆去做排列组合那也成不了百年名题了。

有水平的听众肯定在想如何对这道题进行“一般化”，也就是不局限于这组数字，如果我们对所有数字组合都能找出答案，那就完美了。那要“一般化”，我们就看看这题里面有哪些参数可以改成变量。首先总人数15是一个变量，一般记作v；分成3个人一组，这个3是一个变量，一般记作b；一共出行7天，这个7是一个变量，一般记作r。还有两个不太明显的变量：一个是题目要求任何两个人都恰好组合1次，但题目可以规定每两个人恰好组合2次3次啊，所以这个“1”次也是一个变量，一般记作λ。还有前面算过一共产生35组，这个35，也是一个变量，记作b，所以一共有了5个变量。

但现在肯定有听众会说，你这5个变量不是独立的啊，它们之间会有关系。比如很明显“总人数”x“出行天数”=总的组数x每一组人数。还有一个稍不太明显的关系，（两人恰好组合一次的前提下，可以从前面组合数推理过程中导出）是：天数x(组数-1)=人数-1。以下是这两组关系的一般形式：

既然5个数里面有两个等式关系，那就（大致）说明确定了其中三个，可以计算出另外两个。但是因为这5个数在讨论问题过程中经常出现，所以数学家还是定义了这5个变量。请大家暂时记住下，有“五变量两等式”，在后面还会多次提到。

下面说几个听上去高大上的名词，但是听我一说也就“简单”的不得了。首先，这类问题在数学里被称为区组设计(Block Design），因为我们的目标是设计出女生散步的组合，也就是“区组”或简称“块”。

另外因为最终设计不需要使用到所有15人中取3人的组合，所以这叫“不完全区组设计”。再有，因为最终设计结果是高度对称的，每个人出去散步的天数一样，每两个人的组合恰有一次，所以我们叫这种设计是平衡的，所以总的来说，这个问题属于“平衡的不完全区组设计”（ Balanced Incomplete Block Design）问题，英文简称“BIBD问题”。

又因为柯克曼女生问题的5个参数值分别是：总块数35，每天有15块，总共7组，每块3人，每两人恰好出现在1块，所以这个问题也被称为-设计问题。再因为这5个参数之间有两个等式关系，我们可以省略两个参数，所以也经常简称为-设计问题。有了15，3，1三个参数，另外两个参数，35和7是可以被算出来的。

请原谅我一下子灌输了这么多听上去高大上的概念，但这些概念是为了后面的叙述简便。你看问题改为-设计问题后，就容易记忆许多。原来的题目可以改成：请你给15个女生划分出若干3个女生组成的子集，要使得任何两个女生恰好出现在一个子集中。你会发现你的答案就只能划分出35个子集，而且每个女生恰好出现在7个子集中。这意味着原本题目有两个条件是可以隐去的，如果你认识到这一点，那么你对原题的认识就升华了一步。

那么我们再考虑一下如何具体去找这种划分。用死办法去排，当然可以，但是有一种画图的方法可能简便点。你在纸上画上15个点，表示这个15个女生，如果有三个女生分成一组，那么你就对这三个女生连一条线，那么第一天的出行方案就需要5条线。然后你可以换一种笔的颜色，再画5条线。如果你能用7种颜色完成着色，那么出行方案就徘出来了。

但我推荐你一开始可以只用一种颜色的笔来画，你的目标是画出35条线，每条线经过三个点，每两个点之间有且仅有一条线。等画出这35条线后，你再设法把它拆成7份，这种方法我觉得要简便点。更重要的是，如果你仔细听过大老李之前的一期有关“有限单群分类定理”的节目，你会发现这个画图过程跟那期提出过的一个问题很像！

在那期节目里，大老李提过一个问题：请你在纸上画7个点，然后对每3个点进行连线，要求是任何两个点之间有且仅有一条连线。这个问题只是把15个点改成了7个点。这道画图题各位可以马上试试，应该很快能画出来。

(上图：7个点的施泰纳三元系)

而且我在那期节目里说了，你画出来的这种图被称为“施泰纳系统”（Steiner System），而且人们从几个施泰纳系统里找出了散在单群。你别看“施泰纳系统”这个名词又是那么高大上，其实就是一种BIBD问题。

说到“施泰纳系统”，简单介绍一下施泰纳（Jakob Steiner）。施泰纳是与柯克曼同时代数学家，1896年出生在瑞士。跟柯克曼相似的是，他小时候也没有得到很好的教育，没有进过正规学校，长期帮父母务农，甚至14岁前还不能写字。但是他很早就表现出了很好的数学天赋。20岁时，他离开家乡，到瑞士西南部城市伊韦尔东生活，进入由当时的教育家裴斯泰洛齐开办的学校中，既当老师又当学生。这段时间对施泰纳影响很大，他对很多数学教材里的命题提出了新的证明，而且师生都发现他的新证明简介简洁又漂亮，从而都转向使用他的证明。这使得施泰纳对自己的数学才能得到了信心。

终于他在26岁时进入柏林大学学习了2年，之后转为了职业数学家。可以说施泰纳也是有点大器晚成的数学家。在柯克曼提出他的女生散步问题的之前几年，施泰纳正好也在研究组合问题。施泰纳此时研究的问题后来被称为“施泰纳系统”，其中最基本的研究对象就是“施泰纳三元系”（Steiner Triple Systems）。

“三元系”的意思就是三个一组的意思。之前女生出行问题正好问的是三人一组。你会发现如果是1个人一组或2个人一组的问题都太平凡了，只有当3个人一组，这个问题才值得研究。所以，所谓施泰纳三元系就是BIBD问题中，当分组大小为3的一类子问题。

现在第一个问题就是当分组大小确定为3的情况下，总人数是什么样的数字，可以存在施泰纳三元系？之前我们提到两个例子分别是总人数为7和15的情况，那其他数字能产生施泰纳三元系吗？显然有很多数字不行。你想到的第一条就是这个总人数要满足前面说过的：那5大参数所要满足的2大等式，否则有些参数都不是整数，那肯定不行。所以这两个等式肯定是必要条件。

那是不是充分条件呢？还不是。1844年，柯克曼证明了施泰纳三元系存在的充分必要条件，就是总人数除以6的余数必须是1或3：

这是一个非常漂亮的结论，而且是充要条件。但是问题没有完，存在施泰纳三元系，不代表能有一个柯克曼问题中的散步方案。比如说7个人，分3人一组出行，但7除不尽3，显然就没有一个合适的散步方案。

柯克曼肯定是在研究过施泰纳三元系之后，发现有些三元系还有更强的性质，就是可以把分组结果分成数量相等的若干组，而且每一组中的元素并集恰好是全体元素。而15是满足除3和9这两种比较平凡的情况外，第一个满足施泰纳三元系条件，且满足这种继续分解条件的数字，所以他才提出了这么一道柯克曼女生散步问题！

而后来人们把柯克曼的这种继续分解的方案称为“可分解的平衡不完全区组设计”（Resolvable Balanced Incomplete Block Design），简称RBIBD问题。而如果一个施泰纳三元系，存在一种RBIBD设计，那就被称为柯克曼三元系（Kirkman Triple System）。即柯克曼三元系的定义要比施泰纳三元系的条件更严格，是施泰纳三元系的子集。

现在问题又来了，怎样的施泰纳三元系可以是柯克曼三元系？这个问题比施泰纳三元系的存在性问题就难非常多了。但柯克曼三元系存在的必要条件，很早人们就发现有两个：

一个是总人数能够整除3，这是显然的。第二个是总人数是奇数，这点虽然不太明显，但是有兴趣推导一下还是能推导出来的。而两个条件综合起来，就是人数除以6余3，。

但再一次，以上这个条件是否就是充分条件呢？这个问题一拖就是100多年。

这里要再次介绍一位数学家，他是我国近代略带悲剧色彩，但是绝对值得介绍和纪念的一位数学：陆家羲。陆家羲1935年出生在上海，家境贫困。1948年父亲因病去世，导致家庭经济难以维持，他勉强熬到初中毕业就开始辍学。1950年进入一家五金行做学徒工。1951年考入东北电器工业管理局训练班，半年後以第一名成绩结业，分配至哈尔滨电机厂工作，月薪64元（当时的高薪）。

1957年，22岁的他自学考入东北师范大学物理系，看到一本孙泽瀛所著《数论方法趣引》，被深深吸引，特别是其中的“柯克曼女生散步问题”，改变了他人生道路。他曾说“物理是我的最爱，数学则是我的娱乐”。

1961年，陆家羲认为他证明了柯克曼三元系的存在的充分必要条件，就是之前提到的人数除以6余3这个条件，写了一篇题为《寇克曼和斯泰纳系的制作方法》的论文，寄给了中科院数学研究所。但也许是他的论文内容太先进了，中科院研究所过了两年才给与答复，建议他修改后重新投稿其他单位。

陆家羲对自己的证明是充满信心的，于是1963年和1965年两次重写他的论文发给了《数学通报》和《数学学报》两本刊物，但都杳无音讯。到1966年，由于众所周知的原因，中国的所有科学研究继续都陷于停滞。

6年后，1972年，陆家羲结婚，育有一女，让他的生活有了点色彩。又过了7年，1979年，陆家羲借到了两本1974年和1975年出版的国外的组合数学权威刊物《组合论》（Combinatorics），发现国外有人（Ray-Chaudhuri and Wilson）已经在1971年和1975年分别解决了柯克曼三元系存在性的充要条件问题以及推广到n元组的情况。这对陆家羲的打击太大了，因为即使从1971年开始算，这也比他的发现晚了7到10年。

但是陆家羲并不灰心，他在国外研究者的基础上进一步拓展了问题，并取得了突破。于是他直接写了篇英文论文，寄给了美国的这本《组合论》杂志。1981年，他又寄了3篇论文给《组合论》杂志，都得到出版。这些论文得到了国外同行的高度评价。加拿大多伦多大学教授门德尔逊说：“这是二十多年来组合设计中的重大成就之一。” 多伦多大学校长还邀请陆家羲到多伦多大学任职，而此时陆家羲还只是包头一所中学的物理老师。

经过国外同行认可后，陆家羲终于也被中国学术界认可。1983年10月，他成为唯一被特邀的中学教師參加了在武汉举行的第四节中国数学年会。大会充分肯定他的成就，表彰他勇攀数学高峰的奋斗精神。会议结束后，为了返校上課，他隨即返回包头家中。回家后就兴奋地对妻子說“这次可见过大世面了”。10月30日晚饭后，和家人聊了一下便說“太累了太累了，明天再讲，早些休息吧”。积久的疲劳，和長期潜伏的疾病已远远超过他生理所能承受的极限。当晚凌晨1时许，心脏病突发，猝然与世长辞，未留下一句遗言，年仅48岁。

1987年，陆家羲被追授了国家自然科学奖一等奖。陆家羲的身世让人唏嘘长叹，我们只能思考如何不让这种悲剧重演。

那我们再回到柯克曼三元系的存在性问题，前面提到了柯克曼三元系存在的充分必要条件就是人数除以6余3。接下来你可能还想问四元系和五元系等等的存在性问题。我可以简单汇报一下：长期以来对是否存在无穷多个施泰纳4元和5元系，一直不能解决。但2014年，Peter Keevash 的一篇论文中给出了一个积极的答案。而是否存在6以及以上的“非平凡”的施泰纳系统，更是区组设计问题中长期未解决的难题。施泰纳系已经那么难，那一般的柯克曼系的问题也更不用提了。

最后再看看这位王本材听众邮件里提出的问题：他问的是如果有 n^2

个男生，按n个人一组出去散步，能否构造出如同柯克曼女生问题中的散步方案？那我们就用今天节目里提到过的一些知识来简单分析一下这个问题。首先我们能想到的检验一下这两个参数的合理性。

有个学生，n个人一组，那么一天里面就有n组。那需要走多少天呢？对某个学生来说，他出去散步一次，他可以认识n-1个其他学生。那么n+1天后，他可以认识 $(n-1)(n+1)=n^{2}-1$ 个学生，这是如果有散步方案的话，他应该需要认识的学生数。这样我们知道散步方案需要n+1天。

那我们再检查下一下，n+1天的方案里是否满足每两个学生恰好出去散步一次。这部分留给听众验证，但结论是合理的。所以我们知道这位听众考虑的问题中，数字设定是合理的！

数字设定合理，我们就可以考虑一下怎么构造方案。如果n=3，那么这个问题就是柯克曼三元系的问题，而9除以6余3，符合柯克曼三元系存在的充要条件，所以我们确定9个人是肯定有4天的散步方案的。

而n>3之后，问题一下子很难。但还好有人做了软件，把已知的可以构造的BIBD设计都存好了。所以我就用软件考察了一下n=4-10的情况。发现4到9之间，除了6以外，所有的BIBD设计都找到了，但是RBIBD设计，也就是构造出散步方案的话，只有n=4的情况找出来了。而对n=10的情况，是否存在BIBD设计还是未知的。

而这位王本材听众确实提到了，他认为n=6的时候是无解的。他还对哪些n能构造出柯克曼系(RBIBD设计）做了猜想。但目前找到的的RBIBD设计过少，所以我无从对他的猜想评价。但总体上他找的这组数是合理的，他也确定6是无解的，说明他是有一定研究的。我觉得现在可以考虑的是设法构造出n=5，也就是25个男生，5人一组，散步6天的方案，或者证明它不存在，这将是一个新发现。当然10以内除了6都可以尝试。

我非常感谢这位听众给我发的这封邮件，让我了解了柯克曼女生散步问题，这个问题可以用“出乎意料”、“别有洞天”来形容。说出乎意料是因为它表面上是一道平淡无奇的排列组合题，但是深入挖掘下去内容是如此博大精深，完全出乎意料。我这期节目是我比较长的节目了，但我节目里说的内容大概只有我阅读材料的1/10。说“别有洞天”是因为这个问题牵涉的问题很广，比如欧拉方、矩阵、仿射几何、数域、群等等，这些都只能留给有兴趣的听众研究了。

另外，这道题牵涉的三位数学家都有点自学成才，大器晚成之感。陆家羲的个人历史悲剧值得我们思考，如何使其不再重演。

最后，我可以出一道简单的思考题，看看大家对今天节目理解多少：

请你考虑下，有21个女生，分别按3人、7人分组，仅从数值上分析，能否找出BIBD设计？进一步，是否存在柯克曼的散步设计？

关于女生的数学问题：柯克曼女生散步问题

在喜马拉雅FM收听：”大老李聊数学”