《科克曼女生问题——百年组合数学难题.doc》由会员分享，可在线阅读，更多相关《科克曼女生问题——百年组合数学难题.doc（8页珍藏版）》请在三一文库上搜索。
1、科克曼女生问题百年组合数学难题科克曼，1806年3月31日出生于英格兰的波尔顿，他在一个没有学问的商人家庭中长大，曾为受到较好的教育奋斗过，但他甚至没有受到任何水平的数学教育，他于1833年在都柏林大学获得艺术学位，被派到英格兰教会，成为一个教区的教区长，达五十年之久科克曼善于思考和勤奋不懈，使他成为具有严密性和洞察力的数学家，并很快进入当时研究的前列，并获得当时英国著名数学家凯莱、哈密尔顿、德莫根的赞扬和友谊当他提出了著名的十五个女生问题时，科克曼的名言已变成众所周知了1850年，科克曼在女士与先生之日记杂志上发表了题为疑问六的文章，提出了15个女学生问题：一位女教师每天带领好班上的15名女
2、生去散步，他把这些女生按3人一组分成5组，问能不能作出一个连续散步7天的分组计划，使得任意两个女生曾被分到一组且仅被分到一组，也就是说，随便从15人中挑出2人，她俩在一周所分成的35个小组里必在一组中见过一面，且仅见一面这个饶有趣味的游戏在一些数学家的介绍、研究和推广下很快在许多国家流传开来科克曼本人给出了一个解，后来发现，科克曼给出的解并不是他所提出问题的唯一答案事实上，过了一百多年，到1974年，这一问题柚德尼斯顿借助于电子计算机得到解决科克曼女生问题激起了兴趣的浪潮，吸引了许多数学家，推动了组合数字的发展问题的解答这个是组合数学里的问题。解决这一问题并不很困难，凯莱首先给出了一个答案，然
3、后科克曼发表了他自己的答案，当然在他提出这一问题时他就已经知道了答案。西尔维斯特（J.J.Sylvester）对这一问题也有研究，后来他就谁先想到这一问题与科克曼有过争论。科克曼在同一刊物上公布了他自己给出的一个答案如下（1至15代表15个女生）：这个解是一个15阶科克曼三元系，其中v=15，k=3，=1。科克曼不但解决了斯坦纳三元系的存在性问题，同时还对r的每个素数值，给出了参数为v=r2+r+1，k=r+1，=1的2-设计，即现称作的有限射影平面。他应用循环差集构造r=4、r=8的射影平面，也发现参数为v=2n，k=4，=1的3-设计和其他几种特殊的设计。可以说，科克曼是组合设计之父。问题
4、的推广这一问题更一般的推广是：怎样把n个女学生分成n/3组，使得在每(n1)/2天内任意两个女生在同一组内只相遇一次。显然如果这样的n存在，那么定有n3(mod6)。直到1971年，满足这个条件的n的存在性问题才得以证明。科克曼当时的工作并未引起人们的重视，直到1853年，几何学家斯坦纳在研究四次曲线的两切线问题时再次提出了这一组合问题，并在克雷尔杂志上发表一文重新指出这种三元系存在的必要条件是n1，3(mod6)，此处不考虑分成n/3组，三元系的问题才引起学者的注意。1859年，赖斯（M.Reiss）证明了这一猜想。但由于当时信息不灵，他们并不知道英国的数学家对此问题已先行一步。早在1844
5、年，就有数学家已提出了B(3,1，v)的情形，而科克曼已于1847年证明了赖斯在12年后才得到的那个结论。由于这一原因及斯坦纳当时的声望，B(3,1，v)一直被称为斯坦纳三元系，并将一般的B(k,1，v)称为斯坦纳系。对于一般的平衡不完全区组设计BIBD（balanceincompleteblockdesign）的研究中，费舍尔（R.A.Fisher）和叶斯（F.Yates）在1938年的一本著作4中给出了一个B(k,，v)的各个参数间满足的基本关系式：rv=bk与r(k1)=(v1)，其中r表示每个区组中都含有r个元素，b表示全部的区组个数。显然，这是一个B(k,，v)存在的必要而非充分条件
6、。1940年，费舍尔又得到了B(k,，v)存在的一个限定条件，即费舍尔不等式bv。给出和证明B(k,，v)存在性的充要条件是很困难的。三元系在被提出后，又经过约100年的探索，直到1961年才由哈纳尼（H.Hanani）证明了下面的（1）式确是B(3,，v)设计存在的充分条件，同时他还指出这也是B(4,，v)设计存在的充分条件。（v-1）=0（mod2）v（v-1）=0（mod6）当k5时，问题变得复杂了，对每个指定的k5，都满足（1）式但却不存在B(k,，v)的(v,)数值组。1975年，威尔逊(R.M.Wilson)证明了：对给定的正整数k和，除去有限个正整数v以外，（1）式是B(k,，v
7、)存在的充要条件。5其中vk。这一结论宣告了B(k,，v)存在性问题的基本解决。用现代术语来说，科克曼女生问题实际上是一个可分解的平衡不完全区组设计RB(3,1，15)。一个B(k,，v)设计（X，），其区组集?坠可分成若干个平行类，平行类是指?坠中的一些区组，这些区组恰好构成了集合X的一个分拆。那么寻求RB(k,，v)存在的充要条件也成为组合设计发展中的一个难题。对于RB(3,1，v)现常称作科克曼三元系，它的存在性问题曾是历史上一个著名难题。这个问题从提出到解决，历时100多年。确定RB(k,，v)设计存在的必要条件是容易的，即v0（modk）（v-1）0（mod（k-1）同样，数学家也想
8、知道（2）式是否是RB(k,，v)存在的充要条件？由于可分解性条件的难度，这方面的进展很慢。对于k3，1的情形，即科克曼三元系，直到1972年才由雷乔得赫里（D.K.Ray-Chaudhuri）及威尔逊证明了RB(3,1，v)存在的充要条件即是（2）式成立，此时（2）式成为v3(mod6)。1972年，哈纳尼与上述两位数学家合作证明了（2）式也是RB(4,1，v)存在的充要条件，此时v4(mod12)。对于这两项结果，中国学者陆家羲于1961年就已得到，只因投稿未登而失去了这方面的优先权。至此，科克曼女生问题，亦即科克曼三元系的存在性问题得到完全解决。西尔维斯特和凯莱在科克曼发表女生问题的研究
9、之后，便对这一问题提出了一个进一步的要求，即希望给出一个连续13周的队列安排，使得不但每周内的安排都符合原来的要求，还要让任意3名女生在全部13周内恰有一天排在同一组。这是在女生问题基础上出现的一个难度更大的问题，后称之为西尔维斯特问题，可简述为：对于任意可以构造的女生散步方案v，是不是总可以得到v2个没有相同三元组的方案来。西尔维斯特问题引出区组设计的大集问题。这一问题直到1974年才由美国的丹尼斯顿（R.H.Denniston）借助电子计算机得以确证，v=15确有如下的13个方案。其中15名女生分别标记为a，b，0，1，.，12，而数字i=0，1，2，.，12。每取i的一个值，所列的57个
10、区组就给出了所求的队形安排。在这个答案中，每周的安排都是一个RB(3，1，15)，而这13个RB(3，1，15)都在同一个集合上，彼此的区别只在于任何两个之间都没有共同的区组（任意3人同行仅1天）。不难算出，15个人中的3人组共有C151335，每周7天，每天5个3人组，总共13周恰好把全部的3人组都安排了一次。像这样的一种大的安排被称为是RB(3，1，15)的一个大集。不仅对于RBIB，对许多这种区组设计都有这种大集问题。而西尔维斯特问题则是区组设计大集问题的最早渊源6。尽管这种设计的大集问题提出得很早，但由于它的可分解性难度，这一课题的研究至今进展很小。中国学者陆家羲等在这方面做出了一些成
11、功突破7。与当今“教师”一称最接近的“老师”概念，最早也要追溯至宋元时期。金代元好问示侄孙伯安诗云：“伯安入小学，颖悟非凡貌，属句有夙性，说字惊老师。”于是看，宋元时期小学教师被称为“老师”有案可稽。清代称主考官也为“老师”，而一般学堂里的先生则称为“教师”或“教习”。可见，“教师”一说是比较晚的事了。如今体会，“教师”的含义比之“老师”一说，具有资历和学识程度上较低一些的差别。辛亥革命后，教师与其他官员一样依法令任命，故又称“教师”为“教员”。与当今“教师”一称最接近的“老师”概念，最早也要追溯至宋元时期。金代元好问示侄孙伯安诗云：“伯安入小学，颖悟非凡貌，属句有夙性，说字惊老师。”于是看，
12、宋元时期小学教师被称为“老师”有案可稽。清代称主考官也为“老师”，而一般学堂里的先生则称为“教师”或“教习”。可见，“教师”一说是比较晚的事了。如今体会，“教师”的含义比之“老师”一说，具有资历和学识程度上较低一些的差别。辛亥革命后，教师与其他官员一样依法令任命，故又称“教师”为“教员”。显然，对于给定的正整数n，若存在斯坦纳三元系（或科克曼三元系），用D(n)（或Dk(n)）表示各自大集的三元系数，则因为n元集的3-子集共有Cn个，而一个三元系包括n(n-1)/6个3-子集，于是有D(n)n-2（或Dk(n)n-2）。所谓的三元系的大集问题就是，是否对所有的n1，3（mod6）且n7，都有D
13、(n)=n-2？是否对所有的n3（mod6），都有Dk(n)=n-2？如上所述，直到1974年才构造性地证明了Dk(15)=13，可见问题的困难及进展之缓慢。1981年9月至1983年4月，美国组合数学杂志收到了陆家羲的六篇论文。文章宣称，基本上解决了斯坦纳三元系的大集问题。事实上，陆家羲证明了如下结果：若n1，3（mod6）且n7，且n141，283，501，789，1501，2365，则D(n)=n-2。这被誉为20世纪组合学领域的重大成就之一。但是，科克曼三元系大集的存在问题则更为困难。可惜陆家羲因为积劳成疾而英年早逝，来不及深入研究这些工作。要练说，先练胆。说话胆小是幼儿语言发展的障碍
14、。不少幼儿当众说话时显得胆怯：有的结巴重复，面红耳赤；有的声音极低，自讲自听；有的低头不语，扯衣服，扭身子。总之，说话时外部表现不自然。我抓住练胆这个关键，面向全体，偏向差生。一是和幼儿建立和谐的语言交流关系。每当和幼儿讲话时，我总是笑脸相迎，声音亲切，动作亲昵，消除幼儿畏惧心理，让他能主动的、无拘无束地和我交谈。二是注重培养幼儿敢于当众说话的习惯。或在课堂教学中，改变过去老师讲学生听的传统的教学模式，取消了先举手后发言的约束，多采取自由讨论和谈话的形式，给每个幼儿较多的当众说话的机会，培养幼儿爱说话敢说话的兴趣，对一些说话有困难的幼儿，我总是认真地耐心地听，热情地帮助和鼓励他把话说完、说好，增强其说话的勇气和把话说好的信心。三是要提明确的说话要求，在说话训练中不断提高，我要求每个幼儿在说话时要仪态大方，口齿清楚，声音响亮，学会用眼神。对说得好的幼儿，即使是某一方面，我都抓住教育，提出表扬，并要其他幼儿模仿。长期坚持，不断训练，幼儿说话胆量也在不断提高。女生问题引出了组合数学的一个重要分支组合设计，这也是组合数学起源于数学游戏的一个佐证，对这些数学游戏，一旦当人们认识到它们在数学和其他科学上的深刻含义后，便又促使人们对它进行更深入的研究，从而丰富了数学学科的内容和知识。（第 8 页