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？在纽约哪个学校？有空交流交流哈
|
