柯克曼的“女学生问题”

《柯克曼的“女学生问题”》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、柯克曼的“女学生问题”　　1850年，英格兰教会的一个教区长柯克曼提出了一个有趣的“女学生问题”，即在某地方的一所住宿学校中有9个女学生同住在一间宿舍里，每天她们都要去校外散步一次。为了加强她们间的相互了解和增进友谊，负责宿舍管理的人想，她们散步时如果将她们分成3组，每组有3位同学，是否可以使得每一个女生在4天之内，都能够与其余的8个女学生有且仅有一次在一个组内的机会。这个乍一看起来似乎很简单的问题，却使负责管理宿舍的人苦苦思索了很久。1851年，他终于找到了一种分组的方案，符合他的要求并发表了名为《女士与先生的日记））的文章。如果我

2、们把9个女学生的名字用1到9这九个数字编成号，就是方案　　第一天：{1，2，3}，{4，5，6}，{7，8，9}　　第二天：{1，4，7}，{2，5，8}，{3，6，9}　　第三天：{1，5，9}，{3，4，8}，{2，6，7}　　第四天：{1，6，8}，{2，4，9}，{3，5，7}　　于是管理宿舍的人就按照他所找出的方案来安排学生们的校外散步了。这样，问题也就解决了。后来，人们把这种方案称为柯克曼三元系。　　我们更进一步问：是否有一种方法，可以找出更多一些的柯克曼三元系呢？　　　　　　　　　　解回答是肯定的，并且9个人，分成4天的

3、散步方案至少有=1680种。　　　　　　我们给出这个方法：将1，2，3，4，5，6，7，8，9任意分成3组，每组3人括在一个括号中：如第一组{a，b，c}，第二组{d，e，f}，第三组{g，h，i}。其中，a，b，c，d，e，f，g，h，i是l，2，3，4，5，6，7，8，9的任意一种组合。　　　　　　对第m组的第n个数，给以记号amn，即a11=a，al2：b，a13=C；a21=d，a22=e，a23=f，a31=g，a32=h，a33=i，则如下的四行数组必为一个由9个数组成的四组的柯克曼三元系。　　　　　　{a11，a12，a

4、13}，{a21，a22，a23}，{a31，a32，a33}　　　　　　{a11，a21，a31}，{a12，a22，a32}，{a13，a23，a33}　　　　　　{a11，a23，a33}，{a13，a21，a32}，{a12，a23，a31}　　　　　　{a11，a23，a32}，{a12，a21，a33}，{a13，a22，a31}①　　　　　　　　　　首先，容易证明每行的9个数两两互不相同。其次，为证明每个人amn与其他8个人均相遇且恰好相遇一次，我们随便取定一个amn，比方取a13，将含有a13的全部三元数组取来，即{a

5、13，a21，a32}，{a13，a23，a33}，{a13，a22，a31}，{a11，a12，a13}，容易看出，。al3与其他8个人）即a21，a32，a23，a33，a22，a31，a11，a12）恰好各在一组中相遇一次。类似地，含a11，a12，a21，a22，a23，a31，a32，a33的数组分别为　　　　　　　　　　　　例管理宿舍的人给出的方案是{1，2，3}，{4，5，6}，{7，8，9}。于是有all=1，al2=2，a13=3，a21=4，a22=5，a23=6，a31=7，a32=8，a33=9。按式①我们就得

6、到柯克曼三元系：　　　　　　　　　　　　注1850年，英国数学家西尔维斯特和凯莱对柯克曼的女学生问题又提出进一步要求，即希望给出一个连续十三周的队列安排，不但使得每周内的安排都符合原来的规定，而且使任意3名学生在全部十三周内都恰有一天排在同一行。　　　　　　西尔维斯特和凯莱提出的问题难度相当大，直到1974年才由丹尼斯顿借助于电子计算机给出如下的第一个答案。安排如下：　　　　　　　　　　　　　　　　各个周的队列安排分别对应于i的取值0，1，…，12，而数字加法结果均以模13取值。