囚犯问题

superacid

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

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

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

fallenjoker

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

flwb

利用集体在一起的时间,互相认识并记住所有的人,从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 编辑 ]

flwb

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

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

耗子哥哥

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

superacid

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

专业新手

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

sky妖媚

没看懂。。。。怎么玩的

今夜微凉

数学归纳法是突破口不？ 2、3、4... ...100

feifucong

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