pa 发帖数: 82 | 1 在一个监狱里,有101个犯人,被关在101个独立的牢房里,互相无法通信。
一天,召开全体囚徒大会。国王大赦,给大家一个机会。
条件:在当天夜里,会有人来把每间牢房门的正面随机地刷上黑色或者白
色,颜色的选择是同等概率随机的(比如用抛硬币的方法决定门上该刷黑色还是白
色),犯人们都不知道自己门上被刷了什么颜色。
第二天早上,犯人会依次被叫到典狱长办公室里。在走出牢房时,犯人都有机会看
见所有其他人门上的颜色,但是因为他自己的牢门是开着的,门的正面靠着墙,所
以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色,
只能回答说“黑色”或者“白色”。然后犯人被带回牢房,关好门后,下一个犯人
再被叫出询问。如此这般,直到所有人都被叫出来一次为止。
注意:在典狱长办公室里犯人是看不到前面其他犯人的回答的。
机会:最后典狱长统计一下所有犯人的回答。如果猜对自己门上颜色的犯人数过半
,那么就释放所有犯人。如果不过半,每个犯人都只好把牢继续坐下去。
问题:囚徒大会后给大家20分钟时间讨论,囚徒们能找到方法么? | t*****l 发帖数: 39 | 2 是不是统一口径,每个人都猜看到的多数的颜色?
【在 pa 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 在一个监狱里,有101个犯人,被关在101个独立的牢房里,互相无法通信。 : 一天,召开全体囚徒大会。国王大赦,给大家一个机会。 : 条件:在当天夜里,会有人来把每间牢房门的正面随机地刷上黑色或者白 : 色,颜色的选择是同等概率随机的(比如用抛硬币的方法决定门上该刷黑色还是白 : 色),犯人们都不知道自己门上被刷了什么颜色。 : 第二天早上,犯人会依次被叫到典狱长办公室里。在走出牢房时,犯人都有机会看 : 见所有其他人门上的颜色,但是因为他自己的牢门是开着的,门的正面靠着墙,所 : 以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色, : 只能回答说“黑色”或者“白色”。然后犯人被带回牢房,关好门后,下一个犯人 : 再被叫出询问。如此这般,直到所有人都被叫出来一次为止。
| l******d 发帖数: 1633 | 3 我也觉得这样可以
最差的情况就是50:51了
【在 t*****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是统一口径,每个人都猜看到的多数的颜色?
| h*****0 发帖数: 4889 | 4 那要是看到一样多怎么办?
【在 t*****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是统一口径,每个人都猜看到的多数的颜色?
| t*****l 发帖数: 39 | 5 random
最坏情况n white, n+1 black
那么n个人猜black, n+1个人猜random
错误概率1/2^(n+1)
【在 h*****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那要是看到一样多怎么办?
| f*****e 发帖数: 148 | 6 偶觉得也差不多这样了,
如果绝对平均,那么就是51:50
50中的人出去,看出51:49, 就猜少数的颜色.
如果51中的人出去,就是50:50,这个时候,这理出去的人,事先规定好,那个人如果看到颜
色比例是
相同的情况下,你必须说某某颜色(比如大家抽签,奇数黑,偶数白),
这种事先规定的,万一全猜错了的几率是 (另外看到不对称的50人都猜对了,所以这里51人都猜错,他们才危险)
50!*50!/100!=5.00489*10^-30
如果让51人随机猜,全猜错的可能是4.44*10^-16
所以,没看猜颜色少的那种,万一同样多,猜事先分配好的颜色
如果撞到5d-30的几率实在关的值得,
其实由于黑白不对称,所以真正被再关的几率是10^-31....几乎不可能 | f*****e 发帖数: 148 | 7 不能random
看我的计算
【在 t*****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : random : 最坏情况n white, n+1 black : 那么n个人猜black, n+1个人猜random : 错误概率1/2^(n+1)
| h*****0 发帖数: 4889 | 8 把题目稍改一下,狱长有可能故意耍大家,以很高的概率率51:50
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 偶觉得也差不多这样了, : 如果绝对平均,那么就是51:50 : 50中的人出去,看出51:49, 就猜少数的颜色. : 如果51中的人出去,就是50:50,这个时候,这理出去的人,事先规定好,那个人如果看到颜 : 色比例是 : 相同的情况下,你必须说某某颜色(比如大家抽签,奇数黑,偶数白), : 这种事先规定的,万一全猜错了的几率是 (另外看到不对称的50人都猜对了,所以这里51人都猜错,他们才危险) : 50!*50!/100!=5.00489*10^-30 : 如果让51人随机猜,全猜错的可能是4.44*10^-16 : 所以,没看猜颜色少的那种,万一同样多,猜事先分配好的颜色
| h*****0 发帖数: 4889 | 9 不过这个基本上是成功概率极高的方法了。恰好51:50的几率太低,不考虑也正常。
【在 t*****l 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是不是统一口径,每个人都猜看到的多数的颜色?
| f*****e 发帖数: 148 | 10 查了一下,现在估算的宇宙年龄是137亿年
就是4.32d17秒
如果是事先约定的来猜, 失败的几率是从宇宙诞生以来,每秒做10^24次选择,才轮到他
们不被大赦的一次可能.
如果是随机猜,那也是,每10秒做一次选择,他们才会有一次机会再坐牢,其实两种方法都
安全
不过事先约定更安全,安全系数是10^25倍 | | | h*****0 发帖数: 4889 | 11 但是如果是51:50(监狱长暗自你们),几乎必挂。
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 查了一下,现在估算的宇宙年龄是137亿年 : 就是4.32d17秒 : 如果是事先约定的来猜, 失败的几率是从宇宙诞生以来,每秒做10^24次选择,才轮到他 : 们不被大赦的一次可能. : 如果是随机猜,那也是,每10秒做一次选择,他们才会有一次机会再坐牢,其实两种方法都 : 安全 : 不过事先约定更安全,安全系数是10^25倍
| f*****e 发帖数: 148 | 12 为什么???
51:50, 那50人一定猜对
51人只要保证不全猜错就可以了,事先安排答案的结果是51人全猜错的可能信是10^-31
为什么必挂? | h*****0 发帖数: 4889 | 13 是猜多的?那50人必错。
31
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 为什么??? : 51:50, 那50人一定猜对 : 51人只要保证不全猜错就可以了,事先安排答案的结果是51人全猜错的可能信是10^-31 : 为什么必挂?
| f*****e 发帖数: 148 | | p*******e 发帖数: 1167 | 15 但是他们怎么知道是50:51呢?
可能是49:52
那么按照约定,他们肯定全错
【在 f*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你不会猜少的啊?
| f*****e 发帖数: 148 | 16 当......
偶错的不是一般的离谱...... | pa 发帖数: 82 | 17 囚徒们商量:先看看其它门的颜色,如果一个颜色比另一个颜色多2个或以上,每个
人都说自己的颜色是多的那种;若看到的黑
白一样多就统一都说黑色(或白色)。
1、若颜色A>=52个,则每个人看到的都是(颜色A-颜色B)>=2,每个人都会说A,说
对的概率>=52/101,全部释放。
2、若颜色A=51个,则颜色B=50个,则有50人看到的是颜色A>颜色B,50人都会说
A,都错了,51人看到黑白一样多,就统一都
说黑色(或白色),此时释放的几率为1/2。
3、问题的关键是颜色A=51个,颜色B=50个的现象存在的几率是多少呢?
若门数为N,N为奇数,所有颜色的排列有power(2,n)种可能,
则A=cell(N/2),B=floor(N/2)的几率为 n×(n-1)/power(2,n)
n=101时 几率几乎等于零,就是说,基本上囚犯不可能再坐牢了
4、此种方法n=3时,坐牢的几率是1/2*(3*2/8)=3/8
n=5 时,坐牢的几率是1/2*(5*4/32)=5/16
n=7 时,坐牢的几率是1/2*(7*6/128)=21/128
n
【在 pa 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 在一个监狱里,有101个犯人,被关在101个独立的牢房里,互相无法通信。 : 一天,召开全体囚徒大会。国王大赦,给大家一个机会。 : 条件:在当天夜里,会有人来把每间牢房门的正面随机地刷上黑色或者白 : 色,颜色的选择是同等概率随机的(比如用抛硬币的方法决定门上该刷黑色还是白 : 色),犯人们都不知道自己门上被刷了什么颜色。 : 第二天早上,犯人会依次被叫到典狱长办公室里。在走出牢房时,犯人都有机会看 : 见所有其他人门上的颜色,但是因为他自己的牢门是开着的,门的正面靠着墙,所 : 以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色, : 只能回答说“黑色”或者“白色”。然后犯人被带回牢房,关好门后,下一个犯人 : 再被叫出询问。如此这般,直到所有人都被叫出来一次为止。
| g*******e 发帖数: 84 | 18 我觉得计算P(A=51,B=50)的公式有问题。分母是所有的排列可能,但分子并没有给出所
有的排列可能。正确的算法用binomial distribution.每个门的颜色是一个独立的tria
l, 每次trial是白色的机会是0.5,所以有50个白门的几率可以用excel 的 binomdist
函数计算。P(A=50)=binomdist(50,101,0.5,0)=0.078, 再加上A=51的概率,出现(50,
51)的可能性有15%,相当大了。
【在 pa 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 囚徒们商量:先看看其它门的颜色,如果一个颜色比另一个颜色多2个或以上,每个 : 人都说自己的颜色是多的那种;若看到的黑 : 白一样多就统一都说黑色(或白色)。 : 1、若颜色A>=52个,则每个人看到的都是(颜色A-颜色B)>=2,每个人都会说A,说 : 对的概率>=52/101,全部释放。 : 2、若颜色A=51个,则颜色B=50个,则有50人看到的是颜色A>颜色B,50人都会说 : A,都错了,51人看到黑白一样多,就统一都 : 说黑色(或白色),此时释放的几率为1/2。 : 3、问题的关键是颜色A=51个,颜色B=50个的现象存在的几率是多少呢? : 若门数为N,N为奇数,所有颜色的排列有power(2,n)种可能,
| M******H 发帖数: 249 | 19 好象不对吧.
若看到一样多,说明有51个人是一样颜色,就是说有51个人将会猜,你叫他们猜一样的?1/
2的几率死翘翘.
【在 pa 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 囚徒们商量:先看看其它门的颜色,如果一个颜色比另一个颜色多2个或以上,每个 : 人都说自己的颜色是多的那种;若看到的黑 : 白一样多就统一都说黑色(或白色)。 : 1、若颜色A>=52个,则每个人看到的都是(颜色A-颜色B)>=2,每个人都会说A,说 : 对的概率>=52/101,全部释放。 : 2、若颜色A=51个,则颜色B=50个,则有50人看到的是颜色A>颜色B,50人都会说 : A,都错了,51人看到黑白一样多,就统一都 : 说黑色(或白色),此时释放的几率为1/2。 : 3、问题的关键是颜色A=51个,颜色B=50个的现象存在的几率是多少呢? : 若门数为N,N为奇数,所有颜色的排列有power(2,n)种可能,
| M******H 发帖数: 249 | 20 恩,如果是完全随机,多到101次出现黑白相当50:51的机率是很大的,不能忽略.
tria
binomdist
50,
【在 g*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我觉得计算P(A=51,B=50)的公式有问题。分母是所有的排列可能,但分子并没有给出所 : 有的排列可能。正确的算法用binomial distribution.每个门的颜色是一个独立的tria : l, 每次trial是白色的机会是0.5,所以有50个白门的几率可以用excel 的 binomdist : 函数计算。P(A=50)=binomdist(50,101,0.5,0)=0.078, 再加上A=51的概率,出现(50, : 51)的可能性有15%,相当大了。
| | | m*****n 发帖数: 74 | 21 2天了,有答案吗?概率最优还是绝对有效?
【在 pa 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 在一个监狱里,有101个犯人,被关在101个独立的牢房里,互相无法通信。 : 一天,召开全体囚徒大会。国王大赦,给大家一个机会。 : 条件:在当天夜里,会有人来把每间牢房门的正面随机地刷上黑色或者白 : 色,颜色的选择是同等概率随机的(比如用抛硬币的方法决定门上该刷黑色还是白 : 色),犯人们都不知道自己门上被刷了什么颜色。 : 第二天早上,犯人会依次被叫到典狱长办公室里。在走出牢房时,犯人都有机会看 : 见所有其他人门上的颜色,但是因为他自己的牢门是开着的,门的正面靠着墙,所 : 以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色, : 只能回答说“黑色”或者“白色”。然后犯人被带回牢房,关好门后,下一个犯人 : 再被叫出询问。如此这般,直到所有人都被叫出来一次为止。
| h*****0 发帖数: 4889 | 22 不存在绝对有效。概率最优解,其成功概率上限为101/102
【在 m*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 2天了,有答案吗?概率最优还是绝对有效?
| N*****N 发帖数: 1605 | 23 改天研究下,这个题也有意思
【在 h*****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不存在绝对有效。概率最优解,其成功概率上限为101/102
|
|