poster239

女生散步问题

如何将25名女生分成5组,做出一个连续散步若干天的计划,使得任意两个女生曾被分到一组且仅被分到一组.
女生散步问题
6 人挑战成功
趣味数学挑战

完成本期挑战需要达到:

大众数学水平

题目

一位女教师每天带领班上的(其中为素数)名女生去散步,她把这些女生按n人一组分成n组,作出一个连续散步 __________天的分组计划,使得任意两个女生曾被分到一组且仅被分到一组.

选项

柯克曼女生问题

1850年,英国神甫科克曼提出了15个女学生问题:一位女教师每天带领班上的15名女生去散步,她把这些女生按3人一组分成5组,问能不能作出一个连续散步7天的分组计划,使得任意两个女生曾被分到一组且仅被分到一组,也就是说,随便从15人中挑出2人,她俩在一周所分成的35个小组里必在一组中见过一面,且仅见一面.

这个饶有趣味的游戏在一些数学家的介绍、研究和推广下很快在许多国家流传开来.

科克曼在同一刊物上公布了他自己给出的一个答案如下(1至15代表15个女生):

星期日 {1, 2, 3},{4, 8, 12},{5, 10, 15},{6, 11, 13},{7, 9, 14};

星期一 {1, 4, 5},{2, 8, 10},{3, 13, 14},{6, 9, 15},{7, 11, 12};

星期二 {1, 6, 7},{2, 9, 11},{3, 12, 15},{4, 10, 14},{5, 8, 13};

星期三 {1, 8, 9},{2,12,14},{3, 5, 6}, {4, 11, 15},{7, 10, 13};

星期四 {1, 10, 11},{2, 13, 15},{3, 4, 7},{5, 9, 12},{6, 8, 14};

星期五 {1, 12, 13},{2, 4, 6},{3, 9, 10},{5, 11, 14},{7, 8, 15};

星期六 {1, 14, 15},{2, 5, 7},{3, 8 ,11},{4, 9, 13},{6, 10, 12}.

科克曼本人给出了一个解,后来发现,科克曼给出的解并不是他所提出问题的唯一答案.

事实上,过了一百多年,到1974年,这一问题由德尼斯顿借助于电子计算机得到解决. 科克曼女生问题激起了兴趣的浪潮,吸引了许多数学家,推动了组合数学的发展.

下面我们也提出一个简单版的“柯克曼女生”问题供大家思考娱乐.

简单版“柯克曼女生问题”

一位女教师每天带领班上的25名女生去散步,她把这些女生按5人一组分成5组,问能不能作出一个连续散步若干天的分组计划,使得任意两个女生曾被分到一组且仅被分到一组?

任何一个学生每天将与四个学生在一组,因此他至少需要六天才能与其他24个同学一起合作过.如果这24名学生都是不同的,那么在这六天里,该学生将与其他每个同学正好合作一次.因此,最好的安排是六天,其中每个学生与其他每个学生正好合作一次.那么如何实现呢?

我们将25名学生排成5行5列的矩阵.

1.在第1天,让同一列的学生成为小组.

  1. 进行如下操作.

在第2天,将第2行的每个学生向右移动一个位置(行末的学生被移到行首);将第3行的每个学生向右移动两个位置;将第4行的每个学生向右移动三个位置;将第5行的每个学生向右移动四个位置;第1行的学生是保持不变的.

新的列构成了第2天的小组.

  1. 在第3,4,5天重复这个过程.

  2. 在第6天,让同一行的学生成为小组.

以上这个方案就可以让任意一名学生与其他所有学生分到一组且仅被分到一组.