由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
NJU版 - 大家来做题(2)
相关主题
新人报道:fields from Math Dept. of NJURe: 谁知道蒋少涌教授的?
大家就甭为这个ZRK浪费精力了.Re: 又到了毕业的季节~~~
南园暮色(转载)Good article about NJU's past ZZ
回忆生物系陈建秀老师NJU's folk music group's information
[转载] NJU校警伤人事件Re: 请问NJU有几位新当选院士
[转载] NJU校警伤人事件之二2003年中国科学院院士增选
Last December in NJU补充一下年级信息Re:今天南加州校友聚会小结
from NJU bbs建站主要是3个问题。其他暂时不必太考虑
相关话题的讨论汇总
话题: 1th话题: residual话题: color话题: 帽子话题: 做题
进入NJU版参与讨论
1 (共1页)
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 的大作中提到】
: 再想想有没有办法保证最多只错一个,呵呵
相关主题
[转载] NJU校警伤人事件之二Re: 谁知道蒋少涌教授的?
Last December in NJURe: 又到了毕业的季节~~~
from NJU bbsGood article about NJU's past ZZ
进入NJU版参与讨论
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?在纽约哪个学校?有空交流交流哈
1 (共1页)
进入NJU版参与讨论
相关主题
建站主要是3个问题。其他暂时不必太考虑[转载] NJU校警伤人事件
here are some photos from the new NJU web forum[转载] NJU校警伤人事件之二
小百合BBS海外重建组第一号通告,正名Last December in NJU
小百合BBS海外重建组第二号通告,召集from NJU bbs
新人报道:fields from Math Dept. of NJURe: 谁知道蒋少涌教授的?
大家就甭为这个ZRK浪费精力了.Re: 又到了毕业的季节~~~
南园暮色(转载)Good article about NJU's past ZZ
回忆生物系陈建秀老师NJU's folk music group's information
相关话题的讨论汇总
话题: 1th话题: residual话题: color话题: 帽子话题: 做题