囚犯放风问题

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 发表
感觉与“柯克曼女生问题”异曲同工

我也是如此感觉

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年来组合设计方面最重大的成果之一。”
可惜英年早逝，令人扼腕！

账号		自动登录	找回密码
密码			欢迎注册

[推荐] 囚犯放风问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

答案公布