打字猴:1.70101905e+09
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
1701019091 研究斯坦纳三元系和柯克曼三元系的主要任务,是要确定使B[3;1;v]和RB[3;1;v]存在的所有的v,并要了解那些存在解的种种性质。“柯克曼女生问题”就是RB[3;1;15],已经知道它的解是存在的。孙泽瀛在书中给出了两组答案。
1701019092
1701019093 答案一(用0-14编号来表示15位女生)
1701019094
1701019095 周日 014;21314;3511;6710;89 12周一 028;17 14;31012;41113;5 6 9周二 0314;18 10;2911;4612;57 13周三 079;11213;26 3;458;101114周四 0510;16 11;2712;3813;4914周五 06 13;13 9;2410;51214;7 8 11周六 01112;12 5;347;684;9 1013
1701019096
1701019097 答案二
1701019098
1701019099 周日 014;29 11;31012;5713;68 14周一 028;112 13;347;569;10 11 14周二 0314;12 5;4612;7811;91013周三 0510;16 11;2712;3813;4 9 14周四 0613;17 14;2410;3511;8912周五 079;18 10;236;41113;51214周六 01112;213 14;458;13 9;6 7 10
[ 上一页 ]  [ :1.70101905e+09 ]  [ 下一页 ]