珍珠湾ART

标题: 老题改一改 [打印本页]

作者: constant 时间: 2005-11-8 22:34
标题: 老题改一改

难度：++

有一个聪明国王，他的监狱里有100个死刑犯。他把100人分配到100级台阶上站立，每人头上随机分配红，黄，或蓝帽子一顶。每个人能看见他以下的人所带帽子颜色，但看不见他自己或他以上的人的帽子颜色。然后让100人从最顶的人开始按顺序往下，每人高声喊“红帽子”，“黄帽子”，或“蓝帽子”。最后统计有多少人喊的帽子颜色正好是他所带帽子的颜色。如果至少有N人说对，100个人全部释放。问国王说的N是多少？

（在100人分配台阶和帽子之前，他们可以任意讨论商量如何喊。）

作者: ob 时间: 2005-11-9 01:23
标题: 回复：老题改一改

98.

The first guy tell the number of hat, which color is different from the second guys's hat, is odd or even. The second guy tell the number of another color hat is or or even.

作者: QL 时间: 2005-11-9 05:14
标题: 回复：回复：老题改一改

Actually, I think it can be 99:

The possible colors compostions of the first 99 hats can be divided into 4 groups: (odd,odd,odd), (even,even,odd) (even,odd,even) (odd,even,even). The second guy, based on the colors of the first 98 hats can exclude one situation, so the first guy only have to code the remaining 3 cases with the three colours.

作者: ob 时间: 2005-11-9 09:31
标题: 回复：回复：回复：老题改一改

How can the second guy, based on the colors of the first 98 hats can exclude one situation?

Suppose r=(odd,odd,odd), y=(even,even,odd), b=(even,odd,even). If the first guy can say "Don't know", I know how to do it. Otherwise, how to handle (odd,even,even)?

作者: QL 时间: 2005-11-9 16:18
标题: 回复：回复：回复：回复：老题改一改

I guss my notation is misleading. By (odd,even,even) I mean there are odd # of red, even # of yellow and even # of blue.

If the sencond guy, with 98 hats in front of him, counts (odd,odd,even), he knows that the first guy, with 99 hats in front of hime, will not count (even,even,odd). So the first guy don't have to worry about this situation when he try to encode his observation.

作者: constant 时间: 2005-11-9 17:49
标题: 再加几问

如果有四种颜色的帽子呢？100种呢？无穷多种呢？

作者: ob 时间: 2005-11-9 20:01
标题: 回复：回复：回复：回复：回复：老题改一改

I understand you point. What about the situation when #99 count (even,even,even)?

作者: 12345 时间: 2005-11-10 05:26
提示: 作者被禁止或删除内容自动屏蔽

作者: QL 时间: 2005-11-11 06:48
标题: 回复：回复：回复：回复：回复：回复：老题改一改

good question.

作者: QL 时间: 2005-11-11 06:50
标题: 回复：老题改一改

I still can not prove or disprove whether 99 is right, are you sure this is only a ++ question?

作者: constant 时间: 2005-11-11 17:38
标题: 回复：回复：老题改一改

Yes. It is not difficult. You should be able to get it except your thinking is limited by the original, two-colored version of the problem, which called for a binary solution.

作者: QL 时间: 2005-11-11 18:45
标题: 回复：回复：回复：老题改一改

Thanks for the hint. So the first guy can just encode the information of mod(#red,3), and others will be able to deduce the his color.

作者: husonghu 时间: 2005-11-16 06:56
标题: 此题的原设答案已由 constant 在另贴中给出, 有兴趣者可查看。[@};-][@};-]

此题的原设答案已由 constant 在另贴中给出, 有兴趣者可查看。

欢迎光临珍珠湾ART (http://66.160.158.134/)