pa
发帖数: 82 | 1 在一个监狱里，有101个犯人，被关在10１个独立的牢房里，互相无法通信。
一天，召开全体囚徒大会。国王大赦，给大家一个机会。
条件：在当天夜里，会有人来把每间牢房门的正面随机地刷上黑色或者白
色，颜色的选择是同等概率随机的（比如用抛硬币的方法决定门上该刷黑色还是白
色），犯人们都不知道自己门上被刷了什么颜色。
第二天早上，犯人会依次被叫到典狱长办公室里。在走出牢房时，犯人都有机会看
见所有其他人门上的颜色，但是因为他自己的牢门是开着的，门的正面靠着墙，所
以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色，
只能回答说“黑色”或者“白色”。然后犯人被带回牢房，关好门后，下一个犯人
再被叫出询问。如此这般，直到所有人都被叫出来一次为止。
注意：在典狱长办公室里犯人是看不到前面其他犯人的回答的。
机会：最后典狱长统计一下所有犯人的回答。如果猜对自己门上颜色的犯人数过半
，那么就释放所有犯人。如果不过半，每个犯人都只好把牢继续坐下去。
问题：囚徒大会后给大家20分钟时间讨论，囚徒们能找到方法么？ | t*****l
发帖数: 39 | 2 是不是统一口径，每个人都猜看到的多数的颜色？
【在 pa 的大作中提到】
: 在一个监狱里，有101个犯人，被关在10１个独立的牢房里，互相无法通信。
: 一天，召开全体囚徒大会。国王大赦，给大家一个机会。
: 条件：在当天夜里，会有人来把每间牢房门的正面随机地刷上黑色或者白
: 色，颜色的选择是同等概率随机的（比如用抛硬币的方法决定门上该刷黑色还是白
: 色），犯人们都不知道自己门上被刷了什么颜色。
: 第二天早上，犯人会依次被叫到典狱长办公室里。在走出牢房时，犯人都有机会看
: 见所有其他人门上的颜色，但是因为他自己的牢门是开着的，门的正面靠着墙，所
: 以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色，
: 只能回答说“黑色”或者“白色”。然后犯人被带回牢房，关好门后，下一个犯人
: 再被叫出询问。如此这般，直到所有人都被叫出来一次为止。
| l******d
发帖数: 1633 | 3 我也觉得这样可以
最差的情况就是50:51了
【在 t*****l 的大作中提到】
: 是不是统一口径，每个人都猜看到的多数的颜色？
| h*****0
发帖数: 4889 | 4 那要是看到一样多怎么办？
【在 t*****l 的大作中提到】
: 是不是统一口径，每个人都猜看到的多数的颜色？
| t*****l
发帖数: 39 | 5 random
最坏情况n white, n+1 black
那么n个人猜black, n+1个人猜random
错误概率1/2^(n+1)
【在 h*****0 的大作中提到】
: 那要是看到一样多怎么办？
| 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 的大作中提到】
: random
: 最坏情况n white, n+1 black
: 那么n个人猜black, n+1个人猜random
: 错误概率1/2^(n+1)
| h*****0
发帖数: 4889 | 8 把题目稍改一下，狱长有可能故意耍大家，以很高的概率率51：50
【在 f*****e 的大作中提到】
: 偶觉得也差不多这样了,
: 如果绝对平均,那么就是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 的大作中提到】
: 是不是统一口径，每个人都猜看到的多数的颜色？
| f*****e
发帖数: 148 | 10 查了一下,现在估算的宇宙年龄是137亿年
就是4.32d17秒
如果是事先约定的来猜, 失败的几率是从宇宙诞生以来,每秒做10^24次选择,才轮到他
们不被大赦的一次可能.
如果是随机猜,那也是,每10秒做一次选择,他们才会有一次机会再坐牢,其实两种方法都
安全
不过事先约定更安全,安全系数是10^25倍 | | | h*****0
发帖数: 4889 | 11 但是如果是51：50（监狱长暗自你们）,几乎必挂。
【在 f*****e 的大作中提到】
: 查了一下,现在估算的宇宙年龄是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 的大作中提到】
: 为什么???
: 51:50, 那50人一定猜对
: 51人只要保证不全猜错就可以了,事先安排答案的结果是51人全猜错的可能信是10^-31
: 为什么必挂?
| f*****e
发帖数: 148 | | p*******e
发帖数: 1167 | 15 但是他们怎么知道是50:51呢？
可能是49:52
那么按照约定，他们肯定全错
【在 f*****e 的大作中提到】
: 你不会猜少的啊?
| 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 的大作中提到】
: 在一个监狱里，有101个犯人，被关在10１个独立的牢房里，互相无法通信。
: 一天，召开全体囚徒大会。国王大赦，给大家一个机会。
: 条件：在当天夜里，会有人来把每间牢房门的正面随机地刷上黑色或者白
: 色，颜色的选择是同等概率随机的（比如用抛硬币的方法决定门上该刷黑色还是白
: 色），犯人们都不知道自己门上被刷了什么颜色。
: 第二天早上，犯人会依次被叫到典狱长办公室里。在走出牢房时，犯人都有机会看
: 见所有其他人门上的颜色，但是因为他自己的牢门是开着的，门的正面靠着墙，所
: 以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色，
: 只能回答说“黑色”或者“白色”。然后犯人被带回牢房，关好门后，下一个犯人
: 再被叫出询问。如此这般，直到所有人都被叫出来一次为止。
| 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 的大作中提到】
: 囚徒们商量：先看看其它门的颜色，如果一个颜色比另一个颜色多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 的大作中提到】
: 囚徒们商量：先看看其它门的颜色，如果一个颜色比另一个颜色多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 的大作中提到】
: 我觉得计算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 的大作中提到】
: 在一个监狱里，有101个犯人，被关在10１个独立的牢房里，互相无法通信。
: 一天，召开全体囚徒大会。国王大赦，给大家一个机会。
: 条件：在当天夜里，会有人来把每间牢房门的正面随机地刷上黑色或者白
: 色，颜色的选择是同等概率随机的（比如用抛硬币的方法决定门上该刷黑色还是白
: 色），犯人们都不知道自己门上被刷了什么颜色。
: 第二天早上，犯人会依次被叫到典狱长办公室里。在走出牢房时，犯人都有机会看
: 见所有其他人门上的颜色，但是因为他自己的牢门是开着的，门的正面靠着墙，所
: 以他看不见自己门上面的颜色。在办公室里典狱长让每个囚犯猜自己门上的颜色，
: 只能回答说“黑色”或者“白色”。然后犯人被带回牢房，关好门后，下一个犯人
: 再被叫出询问。如此这般，直到所有人都被叫出来一次为止。
| h*****0
发帖数: 4889 | 22 不存在绝对有效。概率最优解，其成功概率上限为101/102
【在 m*****n 的大作中提到】
: 2天了，有答案吗？概率最优还是绝对有效？
| N*****N
发帖数: 1605 | 23 改天研究下，这个题也有意思
【在 h*****0 的大作中提到】
: 不存在绝对有效。概率最优解，其成功概率上限为101/102
|
|
