珍珠湾ART

标题: 囚犯戴帽子题的推广 [打印本页]

作者: constant 时间: 2007-2-27 18:59
标题: 囚犯戴帽子题的推广

记得以前出过，找了一下没找着。算三星吧，不是很难。

1）设有N种颜色的帽子，按顺序为颜色1，...，颜色N。将100人分配到100级台阶上站立，每人头上随机分配帽子一顶。每个人能看见他以下的人所带帽子颜色，但看不见他自己或他以上的人的帽子颜色。现在让100人从最顶的人开始按顺序往下，每人说出自己所戴帽子的颜色，说的颜色必须是这N种颜色之一，而且不能说任何别的话。如果有99个人说对自己的颜色，100个人一起释放，否则一起杀头。

2）设有无穷种颜色的帽子，按顺序为颜色1，...，颜色N，...。将100人分配到100级台阶上站立，每人头上随机分配帽子一顶。每个人能看见他以下的人所带帽子颜色，但看不见他自己或他以上的人的帽子颜色。现在让100人从最顶的人开始按顺序往下，每人说出自己所戴帽子的颜色，而且不能说任何别的话。如果有99个人说对自己的颜色，100个人一起释放，否则一起杀头。

作者: yinyin 时间: 2007-2-27 22:31
标题: 回复：囚犯戴帽子题的推广

１）设最顶上的人看到的第k种颜色帽子的顶数为a_k，k=1,2,...。他（她）就报对应于

(a₁+2a₂+...+Na_N)modN

的颜色。前面那人只要将此颜色对应的数对照按自己所见用同一公式算出的数，就知道自己头上帽子的颜色了。依此类推，除了最顶上的人仅以 1/N 的概率猜对外，其余９９人都能准确说出自己头上帽子的颜色。

作者: yinyin 时间: 2007-2-27 22:48
标题: 回复：囚犯戴帽子题的推广

２）更容易。直接报a₁+2a₂+...+Na_N（即所有前面的人的帽子颜色对应数字的总和）所对应的颜色就行。

本贴由[yinyin]最后编辑于：2007-2-27 14:54:19

作者: 怀念北京 时间: 2007-2-27 22:56
标题: 回复：回复：囚犯戴帽子题的推广

N顶帽子的情况下，每个人传送到前面的人的信息是一个N进制的数。传到队伍开头总共需要99个这样的数，而所要求传递的总信息正是100个N进制数，所以只要有一个补充信息（也就是队尾的囚犯所作的自我牺牲），信息量是恰好足够的。我认为有很多种设计方法

作者: yinyin 时间: 2007-2-27 23:02
标题: 回复：回复：囚犯戴帽子题的推广

Sorry。打中文准备帖子时还没看到老兄的解答。