博奕论题目：屠夫砍人

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

有一个屠夫,抓了100个人,让他们面朝一个方向排成一坚列,然后给这100个人分别戴上帽子,帽子只有黑和白两种颜色,屠夫是随机给他们带上的,且自己看不见自己帽子的颜色,也不能回头,只能看到自己前面人的颜色.

他们的视力很好,排最后的那个人(100号)可以看见前面所有人的帽子颜色.
他们的听力都很好,最前面的那个人(1号),可以听见后面所有人说的话.

屠夫会从100号开始要他猜自己帽子的颜色,如果猜中,则生,否,则死.然后又问99号,以此类推.
这些人只能回答"黑"或"白"两种答案,如果说这两个字以外的字,所有人都得死.

他们都很团结,为了能让最多的人生存,他们愿意牺牲.

问题就是,你给他们想一个方法,能让尽量多的人生存.

[此贴子已经被nie于2005-5-6 23:04:52编辑过]

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏12 回帖

关键词：屠夫砍人 所有人 看不见 题目 屠夫

这么好的题目怎么没有人响应？我个人奖励楼主金钱50！大家跟贴讨论才有趣啊。

感觉这个是个纯粹的数学问题，似乎和博弈论关系不大

最简单的办法是后面一个人给前面一个人报颜色，这样最少活50个，其数学期望是75人

我的一个想法可能比较偏：

黑帽子和白帽子分别代表二进制里面的0，1

100个人就像100bit的空间，分成前后两段，前一段是由人的帽子颜色作为一个串，然后后一段就用一种特殊的压缩算法对前一段编码，这样前一段的人必然能存活，而后一段人活的概率是50％，由于采用压缩算法，所以比上面那种无压缩的编码方式效率更高，存活的人一般比较高的。

又想到一个更好点的算法
最后7个人牺牲自己，用一个7位的串来表示前93个人中黑帽子的数量（当然白帽子也行）
这样93号由于能看到前92个人，那么他能答对，由此类推上去，这93个人都能活下来

总的活的人的期望是：93＋7/2=96.5
不知道还有没有更好的算法？？

博奕论主要有
完全信息静态博奕：纳什均衡
完全信息动态博奕：子博弈精练
不完全信息静态博奕：叶贝斯纳什均衡
不完全信息动态博奕：精炼叶贝斯纳什均衡
如果要回答上面问题``
应该先确定要属于哪一个项~``

其实这是不是典型的博弈还值得商榷。因为这里个体的收益就是集体的收益（就是存活人数最多）。很像是一个单主体面对既定信息集的决策问题。不过本人倒是支持这个问题用博弈论来分析。

上次曾经讨论过博弈论适合分析什么问题。

https://bbs.pinggu.org/thread-16966-1-1.html

这里相当用最少的字符传递最多的信息。这里最为关键的是对信息集的假设。

如果达到Xaero的要求：

1、这里应该是完美信息（也是完全信息，但这里没有自然的因素，所以应该不用讨论完全不完全的问题）静态博弈。

2、而且大家都是聪明人，并且这是共同知识。在Xaero的基础上还能在多救0.5个人(其中一个人只有0.5的概率存活，现在可以变为1）。因为白和黑都可代表0或1，首先报黑或白的人就可以用白或黑再传递一个信息。比如第99个人是黑帽子，100就可以选第一个报黑。

3、Xaero假设了他的算法是最佳的，而且是共同知识。

[此贴子已经被作者于2005-5-7 20:30:13编辑过]

这个问题非常有意思。这里最关键的是信息集的问题，如果大家都是学计算机的，可能Xaero的第二个算法是最佳的。

如果大家曾经有过特殊的经历可能还会有更好的算法。比如一些研究密码学的人可能会用最少字符传递最多的信息（仅仅是猜测）。

但是感觉Xaero的第一个算法可能更符合常理 。第二个算法也是非常巧妙。

[此贴子已经被作者于2005-5-7 20:29:30编辑过]

做下xaero的补充吧

应该6个就够了吧，因为2的6次方大于94/2

只要那6个人表示颜色少的那种颜色，比如白色少的话，第100个人就说白色，并默认白色为2次算法中的0

这样期望就是94+6/2=97

屠夫1个人，其他人是100人，100人暴动反抗屠夫生存的概率最大。

（题目怎么都这么血腥？）

信息是没法传递的，说“生”“死”的其他的话，都得死。