Question

柯克曼女生问题

一位女教师每天带领班上的15名女生去散步，他把这些女生按3人一组分成5组，问能不能作出一个连续散步7天的分组计划，使得任意两个女生曾被分到一组且仅被分到一组，也就是说，随便从15人中挑出2人，她俩在一周所分成的35个小组里必在一组中见过一面，且仅见一面。

15个女生分别编号为1-15，将15个女生分为3人一组，则所有的分组是C315=455
我们利用循环语句从这455种分组情况中找出35个三元组，是它们满足：
1）、每一个女生出现7次
2）、每一个女生都只和其他14名女生相遇且仅相遇一次
（1,2,3）（1,4,5）（1,6,7）（1,8,9）（1,10,11）（1,12,13）（1,14,15）
（2,4,6）（2,5,7）（2,8,10）（2,12,14）（2,13,15）（3,4,7）（3,5,6）
（3,8,11）（3,9,10）（3,12,15）（3,13,14）（4,8,12）（4,9,14）（4,11,15）
（5,8,13）（5,9,12）（5,10,15）（5,11,14）（6,8,14）（6,9,15）（6,10,12）
（6,11,13）（7,8,15）（7,9,14）（7,10,13）（7,11,12）（2,9,11）（4,10,14）则怎样用这35个三元组构造一个可行解？

Answer 1

英国数学家柯克曼于1850年提出一个问题：某宿舍有十五名女生，每天三人一组进行散步，怎样安排才能使每位女生，有机会与其他每位女生在同一组，并恰好每星期一次？