老题改一改

constant · 发表于 2005-11-8 22:34:58

难度：++

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

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

ob · 发表于 2005-11-9 01:23:01

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:21

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:50

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:01

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:18

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

ob · 发表于 2005-11-9 20:01:25

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

只看该作者 · 发表于 2005-11-10 05:26:51

提示: 作者被禁止或删除内容自动屏蔽

QL · 发表于 2005-11-11 06:48:46

good question.

QL · 发表于 2005-11-11 06:50:05

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:55

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:19

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:49

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

		自动登录	找回密码
密码			立即注册

12345 该用户已被删除	8^# 发表于 2005-11-10 05:26:51 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
12345 该用户已被删除
	回复支持反对使用道具举报

动态微博

老题改一改

回复：老题改一改

回复：回复：老题改一改

回复：回复：回复：老题改一改

回复：回复：回复：回复：老题改一改

再加几问

回复：回复：回复：回复：回复：老题改一改

回复：回复：回复：回复：回复：回复：老题改一改

回复：老题改一改

回复：回复：老题改一改

回复：回复：回复：老题改一改

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