囚犯戴帽子题的推广

constant · 发表于 2007-2-27 18:59:19

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

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

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

yinyin · 发表于 2007-2-27 22:31:19

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

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

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

yinyin · 发表于 2007-2-27 22:48:57

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

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

怀念北京 · 发表于 2007-2-27 22:56:34

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

yinyin · 发表于 2007-2-27 23:02:26

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

yinyin · 发表于 2007-2-28 03:00:53

干脆，帽子上直接写上数字，更好理解，也省得要大家记住颜色的编号。万一有人记错了某个编号，１００人统统完蛋，太惨了点吧。

康兄发发慈悲，把题改改，给前头的兄弟留点活路。

直接写上数字的话，问题２就成一星的了。

狐 · 发表于 2007-3-1 19:53:26

还是跟是谁在叫有关系?

色盲 · 发表于 2007-3-1 22:38:54

HU兄管他叫康MM，其他人都叫他康大帝

因为康兄是灰色的。。。

www.ddhw.org---

据说这世界是彩色的？

只看该作者 · 发表于 2009-5-24 06:36:46

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

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

85 该用户已被删除	9^# 发表于 2009-5-24 06:36:46 \| 只看该作者提示: 作者被禁止或删除内容自动屏蔽
85 该用户已被删除
	回复支持反对使用道具举报

动态微博

囚犯戴帽子题的推广

回复：囚犯戴帽子题的推广

回复：囚犯戴帽子题的推广

回复：回复：囚犯戴帽子题的推广

回复：回复：囚犯戴帽子题的推广

回复：囚犯戴帽子题的推广

我看了几天,一会儿康兄,一会儿康MM,说的都是同一个人吗?

是同一个人[:-K][:-K]