新浪博客

柯克曼女生散步问题的解法

2011-04-30 09:11阅读：

http://blog.sina.cn/dpool/blog/u/1772900004

柯克曼女生散步问题是世界上最难的一百道数学题之一，许多人对它充满兴趣，有些数学爱好者甚至花费几年时间来钻研它。这道题题意是这样的:“15个女生每天分组散步1次， 3人1组，规定1个星期内任意2人都有1次（且仅1次）编在同组。要求排出1个星期的分组方案
在此，我想介绍一种我的拙劣方法，虽繁琐，但一举便可解出24种，我只是初二年级的学生，才疏学浅之流，还望批评指正。若句子晦涩难懂，实是因我表述水平甚差，并不是像那些市面上的专家故意把语言弄的难懂来冒充博学。
几乎所有人看到此题都会想到为这15个人编上
1~15的号码，我的拙法也并无新意。但接下来，我们要做的不是一天一天将七天的安排好，而是想方设法安排出三十五个三人组。这些三人组并不是随随便便的三人组，因为共七天，每天五个三人组，所以三十五组，并且在这三十五组中，1~15每个数字都必须不多不少在不分配在同一天的七个三人组中出现，并且根据题意，在一个数字出现的七个组里，任一组的另外两个成员都不得出现在其余的六个组里，我们可以得到如下一张表（K-1），我们再往里面填数：
柯克曼女生散步问题的解法
K-1 注：每个红框内为一大组
我们给这十五个大组，每组起一个名字，以1开头的为第一大组，2开头的为第二大组，3开头的为第三大组，依次类推……这些名字敬请大家牢记。这里有十五乘七105个小组，任一小组填入两个数都应有另外两个小组也填入两个数，任一三人小组中若填入一个数，则另有一个小组填入一个数，例如，我们在第一大组中第一个小三人组中填入1 2 3，则第二大组中应填上2 1 3，第三大组中应填上3 1 2.
我们首先假设出5组，1 2 3 4 5 6 7 8 9 10 11 12 13 14 15，当然你可以设别的，只是我认为这么看还比较顺眼。
下面我们列这样一个关系图(K-2)，我们称横着的五行为横组，纵着的三列为纵组，这两个名称，也请大家记牢，方便后面表述。
柯克曼女生散步问题的解法
K-2
到现在为止，让我们看看我们有哪些事情可以肯定，我想唯一有价值的一点便是，已经在过一组的1 2 3 不可能再结伴了，类似，4 5 6 7 8 9 10 11 12 13 14 15也不能再结伴，所以我们的表有了新的进展，成了如下K-3
柯克曼女生散步问题的解法
K-3
大家可能不太明白这是什么意思，我来解释一下，因为1 2 3不可能再结伴，所以必定放在不同的小组中，当然，你完全可以把前三个大组中的4 5 6 换成任一横组里的三个数，另外十二个大组中的1 2 3也是一样。其他的我们再也没有什么可以肯定的了，譬如我们在任一大组中举任意没有在此大组中出现的一个数，例如第一大组中，7，我们不能确定它在哪个小组，不知道它是不是和4 5 6其中的哪一个一组或是在4 5 6和1 一组时，，7根本不和它们一组，这些都是无法肯定的。
现在我们的面前出现了很多条路。我要说的是，后面的路不止一条是正确的，我草草算之，便有两条正确之路，其中一条我算下去，得到24中正确答案，另一种由于中国的教育制度只留给我大多时间死记书本知识，无暇再去钻研，其实大约只需两天的课间，中午课余时间，就能再算出24种，只是按老师的说法，这两天的的课余时间，可以背多少古文！也是，在我们的教育制度下兴趣爱好啥用也不顶，除非是背死书的爱好，只有把书背得死死的，我们才有光明的未来！
下面言归正传，说说这两条路吧。
我们先来考虑一下，每一个横组里的三个数，都是处境完全相同的，因为看着顺眼，我们就来看看第一 第二 第三这三个大组。
1 2 3这三个数都已各自结伴，且都与4 5 6结伴，剩下的只有如图（K-4），
柯克曼女生散步问题的解法K-4
所以我们的第一条路是这样的，分别将7 10 13 8 11 14 9 13 15 填入第一第二第三大组中还空一个数的三个小组，即成了（K-5）
柯克曼女生散步问题的解法
K-5
现在来看一看第一第二第三这三个大组，都各空余六个数字，下面的六个数字，就不能随便填了，这几个数字每个都会再出现在两个大组，即出现两次，如果这两次和它同组的除去1或2或3 ，之外的另两个数在同一横组中就不行了，这就会导致这个数有一次必须与剩下的同一横组中的两个数同组，而这同一横组中的两个数必定早已结过伴，所以不合题意。因此我们得将每大组剩下的6个数分配一下，使每个数字两次出现时同组中的除1或2或3的另一个数不在同一横组，我安排出了这样一组，图K-6
柯克曼女生散步问题的解法
K-6
剩下的空缺就简单了，在第四大组中，剩下六个数为10 11 12 13 14 15，我们只需将这6个数在同一竖组中的两个数结伴，把这三个双人伴填入剩余三个没有填完的小组中。第五、六大组同理，这样即成了图K-7
柯克曼女生散步问题的解法
K-7
剩下的空只需看大组里缺少哪几个数即可，例如在第七大组中，7还没有和14 12 一组，所以七大组空缺处填入14 12，最后变成了K-8
柯克曼女生散步问题的解法
 K-8
删去重复的，剩下的正好三十五组，如图K-9
柯克曼女生散步问题的解法

我的更多文章

下载客户端阅读体验更佳

APP专享