k**y
发帖数: 320 | 1 好久不来BBS了，不知道这种文章发在哪，就放在这里，既然这的版主我
还认识。如果不合适，麻烦转到其他版去，别删了啊。
最早的问题：十个人排队，给他们一人一顶帽子，红的或者蓝的。每个人
能看到前面人的帽子，看不到自己的和后面的。(也就是说，第十个人能
看到前九个人的帽子，第九个能看到前八个人的帽子，第八个能看到谁的
帽子？如果你回答不出来，这题肯定不是出给你的)注意红帽子可能有十顶
，也可能根本没有。现在从第十个人开始问，“你的帽子是什么颜色的？”
，然后问第九个，第八个。。。假设分配帽子时每个人得到帽子颜色是随
机独立的，红蓝可能性各一半。这十个人可以事先商量怎么样的一个办法，
使得他们的回答正确数目最多。当然，每个人都可以听到所有其他人的回
答。(没被问的时候不许讲话)现在给你两分钟。
两分钟没找到正确办法的人看下面的解答。找到办法的人跳过解答看后面
的问题。办法很多，都可以让答对率为95%。其中一个是，第十个人牺牲自
己，如果看到的九顶帽子，红的为奇数就回答红，红的为偶数就回答蓝，
那么他有50%可能性撞对答案。而第九个根据他的回答和前面看到的八顶可
以说出自己的颜色；第八个通过看 |
c********n
发帖数: 7 | 2 One general way:
Set colors to numbers: red=1, yellow=0, blue=-1.
Suppose all the 10 people's cap = x10, x9, x8, ...x1.
The #10 say the number: X9+...+x1.
Then #9 say the number: X9 after knowning the X9+...+x1 from
#10's saying and counting x8+...x1.
It is possible that the sum will not be in the range of -1, 0, 1.
Then say the number which is in the range and differ by the real
number by 3*interger, for example, if X9+X8+...+X1=4,
then #10 announces: red which stands for 1 (4-1=3*1) |
r***g
发帖数: 5 | 3
设颜色为1,2,...,m, W(i)为第i个人的颜色，
那计算W(1)+W(2)+..+W(n-1)除m後的馀数，
第n个人就答是这个值的颜色(但如是0答m)，
那其馀n-1必答对，所以答中率为(n-1)/n+1/(mn)
因第一个人完全没有办法知自己是什麽色，所以
这个答案已是最优的。
【在 k**y 的大作中提到】
: 好久不来BBS了，不知道这种文章发在哪，就放在这里，既然这的版主我
: 还认识。如果不合适，麻烦转到其他版去，别删了啊。
: 最早的问题：十个人排队，给他们一人一顶帽子，红的或者蓝的。每个人
: 能看到前面人的帽子，看不到自己的和后面的。(也就是说，第十个人能
: 看到前九个人的帽子，第九个能看到前八个人的帽子，第八个能看到谁的
: 帽子？如果你回答不出来，这题肯定不是出给你的)注意红帽子可能有十顶
: ，也可能根本没有。现在从第十个人开始问，“你的帽子是什么颜色的？”
: ，然后问第九个，第八个。。。假设分配帽子时每个人得到帽子颜色是随
: 机独立的，红蓝可能性各一半。这十个人可以事先商量怎么样的一个办法，
: 使得他们的回答正确数目最多。当然，每个人都可以听到所有其他人的回
|
r***g
发帖数: 5 | 4
换一下题目吧，如果每次询问是主持人轻声地问，只有主持人和被问者
知道问的颜色，然後主持人公布答案是或否给所有人知，那又是怎样算呢？
我心目中已有初步的答案。
【在 k**y 的大作中提到】
: 好久不来BBS了，不知道这种文章发在哪，就放在这里，既然这的版主我
: 还认识。如果不合适，麻烦转到其他版去，别删了啊。
: 最早的问题：十个人排队，给他们一人一顶帽子，红的或者蓝的。每个人
: 能看到前面人的帽子，看不到自己的和后面的。(也就是说，第十个人能
: 看到前九个人的帽子，第九个能看到前八个人的帽子，第八个能看到谁的
: 帽子？如果你回答不出来，这题肯定不是出给你的)注意红帽子可能有十顶
: ，也可能根本没有。现在从第十个人开始问，“你的帽子是什么颜色的？”
: ，然后问第九个，第八个。。。假设分配帽子时每个人得到帽子颜色是随
: 机独立的，红蓝可能性各一半。这十个人可以事先商量怎么样的一个办法，
: 使得他们的回答正确数目最多。当然，每个人都可以听到所有其他人的回
|
k**y
发帖数: 320 | 5 我的第一反应：牺牲前面logm个人，把后面人的sum(color) mode m找出来。
作为完全有把握说出帽子颜色的人数，这应该是最优的吧。因为少于logm个
人是不可能确定某顶帽子颜色的。
不过作为整体概率，不知道这样好不好，因为还存在别的办法。
另外是当n
(比如那几种)，然后大家瞎猜来得准。总体说这个问题很复杂啊。。。
题外话：
版主还记得我，很感动。
大家还是一如即往的牛。
科学和物理分版，很高兴。不过不会常来，最多也是潜水作业。
考试考得不好了，前两天游戏打得太多：((。考试题(也是脑筋急转弯之类
的)就不泄露了。
【在 r***g 的大作中提到】
:
: 换一下题目吧，如果每次询问是主持人轻声地问，只有主持人和被问者
: 知道问的颜色，然後主持人公布答案是或否给所有人知，那又是怎样算呢？
: 我心目中已有初步的答案。
|
