Author Topic: 每周一题:帽子问题 (8/16/04 -- 8/22/04)  (Read 9314 times)

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« on: 八月 14, 2004, 12:37:55 am »
上周问题讨论:

TESTPOST的解法基本正确,只是叙述有些繁。主要是要认识到被三个男生所解的题
目数与被三个女生所解的题目数之和大於 N X N,所以说还是抽屉原理的翻
版。

这周的题目大概知道的人挺多,几年前曾经轰动一时。这样的题目迟找会有人把它
提到这个论坛上来。我想还是我把它出出来比较好。尤其是对於一般N的情况,我
对它的解了解得还不是太透,大家可以讨论一下。

本周题目:帽子问题

三个人去参加一个集体竞赛。竞赛的方式很简单,猜帽子的颜色。竞赛时,三个人
每人被随机地戴上一个红色或蓝色的帽子(红色和蓝色的概率均等,一半一半)。
每个人只能看见别人的帽子,但看不见自已的帽子。竞赛要求每个人根据自已所见
而猜出自已帽子的颜色。每个人可以选择猜或是不猜(也就是放弃)。如果三人中
至少有一个人猜对,而且没有人猜错,则算他们赢。否则就算他们输(也就是说如
果有任何一个人答错,或者全部放弃都算输)。因为帽子是随机戴上的,别人帽子
的颜色与他的帽子的颜色是不相关的。所以如果每个人都猜,则他们赢的概率是八
分之一(三个人都必须对,而每个人猜对的可能性都是二分之一)。如果他们大家
合作,选择一个人猜,另外两个人永远放弃,则他们赢的概率是二分之一。我们的
问题是,他们能不能有一个好的策略,使得他们的胜率大於二分之一。结果当然是
肯定的,否则我们不会出这个题目了。具体怎么做,就是你的问题。他们在竞赛前
可以讨论,一旦竞赛开始就不可以有任何形式的信息交流。而且他们也不知道同队
中别的人所答的内容。

如果你觉得这个问题比较容易,那么请试一试超过三人的情况,比如说四人的情况。
他们的最好胜率是多少。如果每个队有N个人,最好胜率又是多少?

Elixir

  • Jr. Member
  • **
  • Posts: 32
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« Reply #1 on: 八月 19, 2004, 07:12:07 pm »
这题有些不明白, 我觉得如果不能交流信息, 而且每人都不知道其他人回答的什么:红,蓝,或者弃权, 1/2概率是极限.
如果可以知道别人有否弃权 (这其实就是一种信息交流),  可以好一点, 比如第一个人若看见其余两人戴同色帽子, 就弃权, 否责猜. 剩下两人根据第一人弃权与否, 见机行事.

Elixir

  • Jr. Member
  • **
  • Posts: 32
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« Reply #2 on: 八月 19, 2004, 07:30:41 pm »
刚才想错了,  3个人, 让看见2顶同色帽子的人猜另外一种color,  胜率3/4.
4个人的话,  好象应该 让看见AAB 的人猜B, 看见AAA or BBB 的人猜A, 胜率11/16

packman

  • Full Member
  • ***
  • Posts: 226
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« Reply #3 on: 八月 19, 2004, 08:00:27 pm »
It's more complicated than that.
简单==完美

方信

  • Newbie
  • *
  • Posts: 15
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« Reply #4 on: 八月 20, 2004, 02:39:17 pm »
How many Hats do they have? Is it a big pool? Or the number of all Hats is the same as the number of people.

Have no clue on this one, if the number of Hats is infinite or very big number.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« Reply #5 on: 八月 20, 2004, 03:52:34 pm »
There are infinitely many (or big enough) hats, so that the probability of getting a blue or red hat is always 50%, no matter how many hats have been given out.

packman

  • Full Member
  • ***
  • Posts: 226
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« Reply #6 on: 八月 20, 2004, 04:17:57 pm »
deleted.
简单==完美

方信

  • Newbie
  • *
  • Posts: 15
每周一题:帽子问题 (8/16/04 -- 8/22/04)
« Reply #7 on: 八月 20, 2004, 09:24:44 pm »
Just to make sure I understand the question correctly.

Even if someone gives up, his partners have no knowledge about it. Is it right?

Do all three have to give their answers at once, or independently, without even knowing the others are going to give up?