1701019041
数学文化教程 [:1701013774]
1701019042
数学文化教程 第八节 攻克斯坦纳三元系大集的百年难题
1701019043
1701019044
组合数学是一门古老的学问。主要研究离散对象（通常是有限个）按一定的规则进行组合或排列的问题。近代的组合数学有许多有趣的问题。从柯克曼女生问题到三元系大集问题，这个困扰数学家多年的难题，由一个中国包头第九中学的物理教师解决。他在特别困苦的研究环境中呈现的精神，使人肃然起敬。
1701019045
1701019046
1.从河图洛书说起
1701019047
1701019048
这门数学分支几乎与几何和代数一样古老。如在中国，传说4000年前大禹治水时所发现的“洛书”，其实就一种奇妙的数字排列图（图9.8.1）。在该图中，1至9这九个数字均正好出现一次，使其按各行、各列或按斜线相加的数字之和正好等于15。用组合数学的语言：洛书是一个三阶纵横图，也称为三阶幻方（magic square）。宋朝数学家杨辉在他的《续古摘奇算法》（1275年）中给出了从三阶到十阶的纵横图。
1701019049
1701019050
组合数学另一个较古老的研究对象是拉丁方（Latin square）。这是把每种有n个的n种元素放在一个n×n的方格图中，使得每种元素在每行每列中正好出现一次。图9.8.2就是一个4×4的拉丁方。
1701019051
1701019052
随着科学技术的迅速发展，特别是计算机的出现，使得组合数学在物理学、化学、生物学、信息科学、生产管理等领域有了广泛的应用。比如说，拉丁方在实验设计的概率统计理论中就有重要的应用。
1701019053
1701019054
1701019055
1701019056
1701019057
▲ 图9.8.1 中国古代的“洛书”及其对应的数字表示图
1701019058
1701019059
1701019060
1701019061
1701019062
▲ 图9.8.2 一个4×4的拉丁方
1701019063
1701019064
组合数学的研究主要使用归纳法和递归运算法等方法，并不需要太多的分析、微分几何和抽象代数等现代数学核心工具：这些工具一般只适用于处理连续对象而不太适用于离散对象。因此，组合数学的入门较容易。然而，在这门学科中，存在着许多足以难倒最富有才智数学家的有趣的难题。如与“柯克曼女生问题”密切相关的斯坦纳三元系其实是拉丁方概念的一种推广，其中就含有一些曾经长期未能解决的问题。
1701019065
1701019066
2.“柯克曼女生问题”引出斯坦纳三元系和柯克曼三元系
1701019067
1701019068
曾主持筹建华东师范大学数学系和江西大学数学系的中国数学家孙泽瀛（1911—1981），在20世纪50年代初写过一部甚有影响的数学科普著作《数学方法趣引》（图9.8.3），其中介绍了哥尼斯堡七桥、哈密顿周游世界、四色地图、幻方等八个有名的数学问题，而他最后介绍的就是“柯克曼女生问题”。书中写道：
1701019069
1701019070
某地一个学校内，有收容15个女生的宿舍一所。为了健康的目的，三人一组地分为五组，作郊外散步的计划。如果每组的人，每天全是同样的人，当然感觉到乏味，而且同学之间的友谊，也不能发展。因此规定在每一周，任何人都有与其他同学一度同组之机会。究竟应当怎样分配学生，才合乎这个理想？这实在是一个使舍监煞费思考的问题。也就是所谓的寇克满的女生问题。
1701019071
1701019072
这一问题是英国数学家柯克曼（Thomas Penyngton Kirkman，1806—1895）在1850年提出的。用数学语言把该问题抽象化，就有如下的叙述。
1701019073
1701019074
1701019075
1701019076
1701019077
◀ 图9.8.3 《数学方法趣引》封面
1701019078
1701019079
给定一个含有v=15个元素的集合S，要求设计一个由S的若干个k=3元子集（称为“区组”（block））构成的子集族B，使其满足：
1701019080
1701019081
（1）S的每个元素恰在r=7个区组中；
1701019082
1701019083
（2）S的每个二元子集恰在λ=1个区组中；
1701019084
1701019085
（3）B中所有的区组恰可以形成S的b=7个划分。
1701019086
1701019087
满足以上条件（1）和（2）的组合设计，被称为“斯坦纳三元系”（Steiner triple system），记为B[3；1；15]。一般地可以有B[k；λ；v]，称为“斯坦纳系”，其正式名称叫做“平衡不完全区组设计”。注意，条件（1）中的r=7可由参数k，λ，v推出。斯坦纳（Jakob Steiner，1796—1863）是瑞士数学家。
1701019088
1701019089
如果不仅满足条件（1）和（2），还满足条件（3），该组合设计就被称为“柯克曼三元系”（Kirkman triple system），记为RB[3；1；15]。一般地可以有RB[k；λ；v]，称为“柯克曼系”，其正式名称叫做“可解平衡不完全区组设计”。注意，条件（3）中的b=7也可由参数k，λ，v推出。
1701019090