魔方吧·中文魔方俱乐部

标题: 囚犯问题 [打印本页]

作者: superacid 时间: 2010-11-4 15:06:53 标题: 囚犯问题

一百个囚犯被警长集中在一起。每一个囚犯有两个手套，一个黑色，一个白色。他们被告知今天晚上可以商讨策略，过了那晚之后就没有任何互相交流的机会了。次日早晨，他们每个人都会被分配一个不同的实数，并且写在他们的额头上。每个囚犯可以看见其他人头上的数字，但看不见自己的。每个囚犯需要做的就是决定哪个手套戴在哪个手上（每只手都必须带一个手套）。当所有囚犯带好手套后，根据他们头上数字的大小，他们就会被从小到大一个挨着一个排成一列。然后他们需要和旁边的人手拉手，如果拉在一起的手都是同色手套，则所有一百个囚犯都会被释放。

你的任务是寻找一个使他们被释放的概率最大化的策略。

from 北大数院《数学风采》第18期

作者: TanLaiChen 时间: 2010-11-4 15:13:18

厉害。。。这样也有。。。

作者: 风流沙驼 时间: 2010-11-4 16:22:56

可以用逆序对~~在matrix67的博客里看到过

作者: feifucong 时间: 2010-11-4 17:05:39

貌似有难度啊，回帖的那么少- -

作者: 今夜微凉 时间: 2010-11-4 18:32:46

数学归纳法是突破口不？

2、3、4... ...100

作者: sky妖媚 时间: 2010-11-4 18:38:56

没看懂。。。。怎么玩的

作者: 专业新手 时间: 2010-11-4 19:40:17

我预言乌木老师要现身（貌似是废话）

作者: superacid 时间: 2010-11-5 22:53:38 标题: 回复 7# 的帖子

乌木的数学思维还不至于能轻松解答此类题目吧...

作者: 耗子哥哥 时间: 2010-11-5 23:01:44

基本目标：根据现有的条件判定自己的实数奇偶性。
条件还没完全理解，思考中……

作者: flwb 时间: 2010-11-8 08:49:39

是只能看到头和号码,不能看到别人的手套吗?

[ 本帖最后由 flwb 于 2010-11-8 09:02 编辑 ]

作者: flwb 时间: 2010-11-8 16:12:46

利用集体在一起的时间,互相认识并记住所有的人,从1到100给每个人编号,记住自己和每个人的号码,奇数号码的人是-1,偶数号码的人是+1,确定-1左手戴白手套,+1左手戴黑手套,(也可以反过来)。
第二天，假设只有99号拿到的新号和原来的顺序不一样，假设排在第50位，他看别人的顺序都是正常的，那他还是-1。排在49号的还是原来49号那个，他看到99号跑到第50号前面去了，这个99和其后一直到98的每个人，两两相比，顺序都反了，每反一次记为-1，一共有49个-1，相乘得-1，然后和自己的-1相乘得+1，这样他就把他原来的-1调整为+1。原来的50号本来是+1，他看到有48个错误排列，48个-1相乘得+1，那他还保持+1不变，依次类推，最后的排列一定是-1 +1 -1 +1 -1 +1 ...............。
结论是找到有多少个-1（两两相比，大号在前），连同自己的-1或+1，相乘得出的结果就是自己戴手套的方法。

[ 本帖最后由 flwb 于 2010-11-8 16:26 编辑 ]

作者: fallenjoker 时间: 2010-11-9 20:39:43

是否只能看别人的号码而其他的都不能看？
能够看别人穿的手套吗？
可不可以有暗号？比如说穿了手套又脱。

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)