gxqcn 发表于 2008-1-20 16:14:23

囚犯放风问题

　　杜德尼被誉为数学游戏解的三剑客之一。他曾提出如下问题：

　　设有九个犯人（依次编号为：ABCDEFGHI），放风时分三组，每组三人。每组的三个犯人拷在一起，中间的人分别与左边、右边的人共同拷一付手铐。
　　试问：如何把这些犯人分组及安排他们在各组的位置，使得在六天中，任两个犯人恰有一次共同拷一付手铐？

gxqcn 发表于 2008-1-20 16:30:03

据说这个问题公布之后，长期无人能够给出完美解答，最后还是杜德尼本人给出了答案。

northwolves 发表于 2008-1-21 14:24:54

感觉与“柯克曼女生问题”异曲同工

mathe 发表于 2008-1-21 14:31:24

原帖由 northwolves 于 2008-1-21 14:24 发表 http://bbs.emath.ac.cn/images/common/back.gif
感觉与“柯克曼女生问题”异曲同工
我也是如此感觉:)

kenmark 发表于 2008-1-22 14:51:53

柯克曼女生问题
......

p0303230 发表于 2008-1-23 10:41:52

3组6天 —— 有18次站中间的位置
9个犯人都是公平的 —— 一人两次
也可以 设A有x次站中间的机会—— 2*x + (6 - x) = 9 - 1 => x = 2
然后根据此进行排列

gxqcn 发表于 2008-2-16 11:01:35

答案公布

第一天：ABC DEF GHI
第二天：ADC EBG HFI
第三天：AFB GCH DIE
第四天：AEH BIC DGF
第五天：GAI BHD ECF
第六天：CAH BDF EGI

该问题有及其深刻的背景——斯坦纳(Steiner)系统，“柯克曼女生问题”是其一个子集，
我国已故的数学奇才陆家羲在此有卓越的建树，曾被专家评价：“这是世界20年来组合设计方面最重大的成果之一。”
可惜英年早逝，令人扼腕！
页: [1]
查看完整版本: 囚犯放风问题