z****i 发帖数: 406 | 1 在一个监狱里,有很多犯人,监狱长提出一个古怪的要求,要在这些犯人里面随机的抽
出N个犯人,让他们方向一致站成一纵排,然后给每个人戴上一顶帽子,帽子的颜色只
有两种:黑和白,而且两者数量也是随机的。每个人只能看到他前面的所有人的帽子,
但是看不到自己的和身后人的帽子。然后让每个人说出自己帽子的颜色,只能说黑或者
白,而且不能在声调等其他方面透露出信息(比如大声说或者小声说)。如果2个人以
上说错了自己帽子的颜色,那么所有的人都将被处死,如果只有一个人说错或者全部对
了,那么就全部释放。当然了,在这之前给犯人们一定的时间让他们考虑,制定出一种
方案。
请问,犯人能不能找到一个这样的方案来获得自由呢?方案是什么呢? |
s******0 发帖数: 13782 | 2 发题的和第一个答对的都有奖
【在 z****i 的大作中提到】 : 在一个监狱里,有很多犯人,监狱长提出一个古怪的要求,要在这些犯人里面随机的抽 : 出N个犯人,让他们方向一致站成一纵排,然后给每个人戴上一顶帽子,帽子的颜色只 : 有两种:黑和白,而且两者数量也是随机的。每个人只能看到他前面的所有人的帽子, : 但是看不到自己的和身后人的帽子。然后让每个人说出自己帽子的颜色,只能说黑或者 : 白,而且不能在声调等其他方面透露出信息(比如大声说或者小声说)。如果2个人以 : 上说错了自己帽子的颜色,那么所有的人都将被处死,如果只有一个人说错或者全部对 : 了,那么就全部释放。当然了,在这之前给犯人们一定的时间让他们考虑,制定出一种 : 方案。 : 请问,犯人能不能找到一个这样的方案来获得自由呢?方案是什么呢?
|
X*********n 发帖数: 570 | 3 1. 从最后一个可以看见前面所有人帽子的, 比如叫第N个人, 开始报颜色
2. 开始时定好规则, 如果最后这个人看到前面黑帽子个数为奇数, 则报"黑", 否则报"
白"
3. 这样第N-1个人能看到他之前的黑帽个数, 如果最后一个人报的为"黑", 则表明前N-
1共有奇数个黑, 如果第N-1个人看到奇数个黑, 就知道自己是白, 如果看到偶数个黑,
就知道自己也是黑
4. 第N-2个人一直到第一个人, 一边听别人报的颜色, 一边update自己的信息, 报出自
己的颜色
这样第N个人一半概率猜对, 前N-1个人全对 大家都没事 包子
【在 z****i 的大作中提到】 : 在一个监狱里,有很多犯人,监狱长提出一个古怪的要求,要在这些犯人里面随机的抽 : 出N个犯人,让他们方向一致站成一纵排,然后给每个人戴上一顶帽子,帽子的颜色只 : 有两种:黑和白,而且两者数量也是随机的。每个人只能看到他前面的所有人的帽子, : 但是看不到自己的和身后人的帽子。然后让每个人说出自己帽子的颜色,只能说黑或者 : 白,而且不能在声调等其他方面透露出信息(比如大声说或者小声说)。如果2个人以 : 上说错了自己帽子的颜色,那么所有的人都将被处死,如果只有一个人说错或者全部对 : 了,那么就全部释放。当然了,在这之前给犯人们一定的时间让他们考虑,制定出一种 : 方案。 : 请问,犯人能不能找到一个这样的方案来获得自由呢?方案是什么呢?
|
z****i 发帖数: 406 | 4 Bingo!
好,我们来加一点难度。如果帽子颜色不止两种呢?比如说,有黑,白,红三种颜色。
有没有办法?
报"
N-
,
【在 X*********n 的大作中提到】 : 1. 从最后一个可以看见前面所有人帽子的, 比如叫第N个人, 开始报颜色 : 2. 开始时定好规则, 如果最后这个人看到前面黑帽子个数为奇数, 则报"黑", 否则报" : 白" : 3. 这样第N-1个人能看到他之前的黑帽个数, 如果最后一个人报的为"黑", 则表明前N- : 1共有奇数个黑, 如果第N-1个人看到奇数个黑, 就知道自己是白, 如果看到偶数个黑, : 就知道自己也是黑 : 4. 第N-2个人一直到第一个人, 一边听别人报的颜色, 一边update自己的信息, 报出自 : 己的颜色 : 这样第N个人一半概率猜对, 前N-1个人全对 大家都没事 包子
|
s******0 发帖数: 13782 | 5 赞头像!
青蛙王子, 是比武招亲的意思吗?
【在 z****i 的大作中提到】 : 在一个监狱里,有很多犯人,监狱长提出一个古怪的要求,要在这些犯人里面随机的抽 : 出N个犯人,让他们方向一致站成一纵排,然后给每个人戴上一顶帽子,帽子的颜色只 : 有两种:黑和白,而且两者数量也是随机的。每个人只能看到他前面的所有人的帽子, : 但是看不到自己的和身后人的帽子。然后让每个人说出自己帽子的颜色,只能说黑或者 : 白,而且不能在声调等其他方面透露出信息(比如大声说或者小声说)。如果2个人以 : 上说错了自己帽子的颜色,那么所有的人都将被处死,如果只有一个人说错或者全部对 : 了,那么就全部释放。当然了,在这之前给犯人们一定的时间让他们考虑,制定出一种 : 方案。 : 请问,犯人能不能找到一个这样的方案来获得自由呢?方案是什么呢?
|
X*********n 发帖数: 570 | 6 最后两个人一个报黑 一个报白
这样worst case错两个 平均错一个 还有没有包子?
【在 z****i 的大作中提到】 : Bingo! : 好,我们来加一点难度。如果帽子颜色不止两种呢?比如说,有黑,白,红三种颜色。 : 有没有办法? : : 报" : N- : ,
|
z****i 发帖数: 406 | 7 哈哈,是因为我名字被我老板(美国人)念出来就是‘青蛙’, 被他这样念了4年了,
我也认了。。。
【在 s******0 的大作中提到】 : 赞头像! : 青蛙王子, 是比武招亲的意思吗?
|
z****i 发帖数: 406 | 8 再想想有没有办法保证最多只错一个,呵呵
【在 X*********n 的大作中提到】 : 最后两个人一个报黑 一个报白 : 这样worst case错两个 平均错一个 还有没有包子?
|
s******0 发帖数: 13782 | 9 你好好做题
别问太多了
【在 X*********n 的大作中提到】 : 最后两个人一个报黑 一个报白 : 这样worst case错两个 平均错一个 还有没有包子?
|
X*********n 发帖数: 570 | 10 搞不定了 公布答案吧
【在 z****i 的大作中提到】 : 再想想有没有办法保证最多只错一个,呵呵
|
|
|
z****i 发帖数: 406 | 11 A hint. For the two-color case, what you did is the following: assign a
number X to every hat,
X = 1 if the hat is black;
X = 0 if the hat is white.
Then you sum up all the X's, divide the sum by 2 and look at the residual.
can you come up with a similar strategy for 3-color case?
【在 X*********n 的大作中提到】 : 搞不定了 公布答案吧
|
X*********n 发帖数: 570 | 12 got it.
x=2 if red
x=1 if black
x=0 if white
then sum up all x_i (i=1..N) and divide the sum by 3, get the residual, say
r_n. the last people always tells others the color according to this
residual, i.e., r_n=0-->white, r_n=1-->black, r_n=2-->red.
based on r_n and the residual r_{n-1} calculated by the N-1th man, the N-1th
people can get his color, and following the similar method, all people in
front can get their correct color as well.
is it correct? i guess this solution can also be extended
【在 z****i 的大作中提到】 : A hint. For the two-color case, what you did is the following: assign a : number X to every hat, : X = 1 if the hat is black; : X = 0 if the hat is white. : Then you sum up all the X's, divide the sum by 2 and look at the residual. : can you come up with a similar strategy for 3-color case?
|
z****i 发帖数: 406 | 13 This is exactly correct!! :)
say
1th
【在 X*********n 的大作中提到】 : got it. : x=2 if red : x=1 if black : x=0 if white : then sum up all x_i (i=1..N) and divide the sum by 3, get the residual, say : r_n. the last people always tells others the color according to this : residual, i.e., r_n=0-->white, r_n=1-->black, r_n=2-->red. : based on r_n and the residual r_{n-1} calculated by the N-1th man, the N-1th : people can get his color, and following the similar method, all people in : front can get their correct color as well.
|
s******0 发帖数: 13782 | 14 你是花妹的师兄吗?
say
1th
【在 X*********n 的大作中提到】 : got it. : x=2 if red : x=1 if black : x=0 if white : then sum up all x_i (i=1..N) and divide the sum by 3, get the residual, say : r_n. the last people always tells others the color according to this : residual, i.e., r_n=0-->white, r_n=1-->black, r_n=2-->red. : based on r_n and the residual r_{n-1} calculated by the N-1th man, the N-1th : people can get his color, and following the similar method, all people in : front can get their correct color as well.
|
X*********n 发帖数: 570 | 15 who is 花妹?
【在 s******0 的大作中提到】 : 你是花妹的师兄吗? : : say : 1th
|
z****i 发帖数: 406 | 16 Me...
Were you a math major at NJU? If so, you are my ShiXiong/ShiDi... :)
【在 X*********n 的大作中提到】 : who is 花妹?
|
X*********n 发帖数: 570 | 17 呵呵 不是 不过我本科论文导师以前是数学系的
【在 z****i 的大作中提到】 : Me... : Were you a math major at NJU? If so, you are my ShiXiong/ShiDi... :)
|
s*****r 发帖数: 2347 | 18 这个题目牛x,LZ在念mf?在纽约哪个学校?有空交流交流哈 |
s*****r 发帖数: 2347 | 19 一棍子打飞。。第一次的题目俺第一个答对啊,啥都没拿到
【在 s******0 的大作中提到】 : 发题的和第一个答对的都有奖
|
kx 发帖数: 16384 | 20 晕
好吧
我认错了
我慢慢消化消化你的答案
【在 z****i 的大作中提到】 : Me... : Were you a math major at NJU? If so, you are my ShiXiong/ShiDi... :)
|
kx 发帖数: 16384 | 21 那就让她补足
【在 s*****r 的大作中提到】 : 一棍子打飞。。第一次的题目俺第一个答对啊,啥都没拿到
|
z****i 发帖数: 406 | 22 没有在念mf。。 (mf是master in finance?)
在一个烂校念应数phd。快毕业了,改thesis改得想吐,所以你看到我成天在论坛上晃
荡。。。
11月去纽约。
【在 s*****r 的大作中提到】 : 这个题目牛x,LZ在念mf?在纽约哪个学校?有空交流交流哈
|