加州：哪位参议员“好用”？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Immigration - 落地生根

加州：哪位参议员“好用”？

加州：哪位参议员“好用”？# Immigration - 落地生根

p*72010-05-25 07:05

1 楼

Three people are trying to win the following game as a team:
Each of them is put on a hat of either red or blue with i.i.d probability of
1/2. (i.e. equal chance of being red and blue, and what's put on one person
doesn't affect what are on the other people.) Each one can only see the
other people's hats, but not his own. He has to guess the color of his own
hat by writing down either "Red", "Blue", or "Don't know". After all three
people write down their guesses, they would win if:
1. At least one of them guessed right, and
2. None of them guessed wrong.
Note: "guessed right" is defined as guessing a color that is the color of
the hat. "guessed wrong" is defined as guessing a color that is NOT the
color of the hat. It's neither "right" nor "wrong" if "don't know" is
guessed.
Those three people can discuss a strategy before the hats are put on their
heads. After the hats are on, they can't communicate to each other including
seeing other's guess. What strategy would give them the best chance of
winning and what's the probability of winning under that strategy
我的想法是如果看到1个r一个b就选不知道，如果看到2个b就选r，看到2个r就选b，不过看到答案觉得自己好像没作对

c*g2010-05-25 07:05

2 楼

想催485，哪位用过？

p*72010-05-25 07:05

3 楼

顶

t*72010-05-25 07:05

4 楼

应该是施瓦辛格，超级无敌。。。

Z*Z2010-05-25 07:05

5 楼

没看明白。全选不知道不行么？

of
person

【在 p********7 的大作中提到】

: Three people are trying to win the following game as a team:
: Each of them is put on a hat of either red or blue with i.i.d probability of
: 1/2. (i.e. equal chance of being red and blue, and what's put on one person
: doesn't affect what are on the other people.) Each one can only see the
: other people's hats, but not his own. He has to guess the color of his own
: hat by writing down either "Red", "Blue", or "Don't know". After all three
: people write down their guesses, they would win if:
: 1. At least one of them guessed right, and
: 2. None of them guessed wrong.
: Note: "guessed right" is defined as guessing a color that is the color of

p*72010-05-25 07:05

6 楼

就是保证一个人猜对的概率，如果觉得自己猜对的概率小就选不知道。

【在 Z*****Z 的大作中提到】

: 没看明白。全选不知道不行么？
:
: of
: person

K*g2010-05-25 07:05

7 楼

凭直觉，如果对方是两个red，第三个答blue；对方是两个blue，第三个答red；如果一
个blue,一个red，第三个答“i do not know"。但是需要证明。我感觉这题不是什么
brain teaser，完全是道概率题。

【在 p********7 的大作中提到】

: 就是保证一个人猜对的概率，如果觉得自己猜对的概率小就选不知道。

h*62010-05-25 07:05

8 楼

跑了一遍程序，这个方法是对的。
只要不是全红或者全蓝，都能做到全部无误并且有一个正确，成功率达到75%

K*g2010-05-25 07:05

9 楼

其实也能证明成功率是75%，1-2/8=75%
但是怎么证明是优的呢？

【在 h**6 的大作中提到】

: 跑了一遍程序，这个方法是对的。
: 只要不是全红或者全蓝，都能做到全部无误并且有一个正确，成功率达到75%

p*72010-05-25 07:05

10 楼

方法是对的，就是75%，不过如果有4个人就不简单了

【在 h**6 的大作中提到】

: 跑了一遍程序，这个方法是对的。
: 只要不是全红或者全蓝，都能做到全部无误并且有一个正确，成功率达到75%

h*62010-05-25 07:05

11 楼

四个人的话，有两种策略，都可以达到68.75%的成功率。
1.三红猜红，二红一蓝猜蓝，二蓝一红猜不知道，三蓝猜红。
四红、两红两蓝、一红三蓝成功。
三红一蓝、四蓝不成功。
2.三红猜蓝，二红一蓝猜不知道，二蓝一红猜红，三蓝猜蓝。
三红一蓝、两红两蓝、四蓝成功。
四红、一红三蓝不成功。
对于 n 个人的问题，枚举法复杂度为O(3^n*n)

K*g2010-05-25 07:05

12 楼

你这个枚举法的复杂度是怎么算的？能详细点吗？

【在 h**6 的大作中提到】

: 四个人的话，有两种策略，都可以达到68.75%的成功率。
: 1.三红猜红，二红一蓝猜蓝，二蓝一红猜不知道，三蓝猜红。
: 四红、两红两蓝、一红三蓝成功。
: 三红一蓝、四蓝不成功。
: 2.三红猜蓝，二红一蓝猜不知道，二蓝一红猜红，三蓝猜蓝。
: 三红一蓝、两红两蓝、四蓝成功。
: 四红、一红三蓝不成功。
: 对于 n 个人的问题，枚举法复杂度为O(3^n*n)

h*62010-05-25 07:05

13 楼

对于 n 个人的情况，每个人所见有 n 种可能，分别是
n-1 红 0 蓝，n-2 红 1 蓝，n-3 红 2 蓝，……，0 红 n-1 蓝
每种可能对应有三种策略，总共有 3^n 种策略。
实际分配帽子有 2^n 种方法，但是我们所关心的仅仅是红帽子和蓝帽子的个数，因此
只有 n+1 种方法需要观察，但算实际成功率的时候需要乘以对应组合数。
于是总复杂度为O(3^n*n)

j*a2010-05-25 07:05

14 楼

我的想法是：
有8中可能： r = red, b = blue
r r r
r r b
r b r
b r r
r b b
b b r
b r b
b b b
round 1:
如果第一个看到后面两个人其中有一个是r，就写don't know. 第二个第三个人always
say: don't know。如果后面两个都是b, then write red.
round 2:
第一个人说don't know, 如果第二个看到第三个人是r, 就写don't know, 第三个人写
don't know.
round 3:
第一个和第二个人写don't know. 第三个人写red.
这样成功率是7/8. 也就是三个人都是blue的时候会错。

b*e2010-05-25 07:05

15 楼

3^n part can be reduced to O(n^2). Just need to find the threashhold to
switch your guess:
If all red, guess blue; if all blue, guess red. In the middle, there are
two points where you switch from blue to unknown, and from unknown to red.
That is C(n, 2).

【在 h**6 的大作中提到】