易码技术论坛

 找回密码
 加入易码
搜索
查看: 1394|回复: 8

杀猪问题

[复制链接]
发表于 2008-10-26 12:55:24 | 显示全部楼层 |阅读模式
有一个村子家家户户都养猪,每一家就只养一头猪。有一天卫生防疫站通知村民,这些猪里有一部分得病了。假设大家不能看自己家的猪是否生病,但能看别人家的猪病了没有,一天就能看完全部的猪,且看了就知道猪是否得病。看完后村民之间不能交流,只能通过推理判断该不该杀自己家的猪。第一天,没有人杀猪。。。第二天,还是没有人杀猪。。。第三天,有人杀猪了。。。问,死了几头猪?


这其实是模仿一个经典的博弈论问题而出的,但是很不地道,因为漏掉了一个重要条件:当有足够的信息作出判断之后,当天必须行动。
漏了此条件,变成了无厘头的问题。补充了此条件,问题就好解决了。
推理是这样的:
第一天,每个村民这样想:假设只有一头病猪,是某人的(用A表示),那么,第一天,A就会看不到其他人有病猪,而其他人都看到了,都等着A把他的猪杀掉呢,根据当天行动的要求(这个条件很重要!),A必须把猪杀掉。然而,第一天没人杀,为什么呢?因为A事实上看到了别人也有病猪,等着别人杀呢。

第一天过去了,没人杀猪,那么,大家都知道,病猪原来不知一头。

第二天,每个村民这样想:假设只有二头病猪,是某两人的(用A、B表示),那么,第二天,A和B就会只看到一头病猪,而其他人都看到了两头,都等着A和B把猪杀掉呢,根据当天行动的要求(这个条件很重要!),A和B必须把猪杀掉。然而,第二天没人杀,为什么呢?因为A和B事实上看到了别人也有两头病猪,等着别人杀呢。

第二天过去了,没人杀猪,那么,大家都知道,病猪原来不只二头。

接下去,就出来答案了,是三头,为什么,解释如下:
只有三头病猪,是某三人的(用A、B、C表示),第三天,其他人都看到了三头猪,都等着A和B和C把猪杀掉呢,A和B和C就会只看到两头病猪,而他们知道,病猪其实不止两头,既然自己只看到两头,那么自己的就是病猪了,于是有三个人杀掉了猪。

这个解释还是比较复杂,
我附录给出两个通行版本,表达不同,但原理是一样的。可以参考。

附录一
在一个偏僻的山里,有一个村庄。这里是女人掌
权,女人对一切事务说了算。村里有对夫妇。
在这个村里已经形成了约定俗成的规定。如果女
人发现自己的丈夫对自己不忠的话,就会毫不犹
豫地将他杀死,而且就在当天执行。当然,她必
须有确切的证据来证明她的丈夫不忠。由于这个
因素,某个女人发现某个男人不忠,她不会将之
告诉那个不忠男人的妻子。但是,她会告诉其他
人的妻子,并且女人们会相互传递这一信息,因
此最后,一个男人不忠,除了其妻子不知道外,
其他女人都知道。而事实上是,村子里的这对
100夫妇的男人都不忠,但由于女人不会将她知
道的事实告诉不忠男人的妻子,每个女人都不知
道自己的男人不忠。因此,该村子一直很稳定,
而没有发生妻子杀死丈夫的行为。村子里有一个
辈分很高的老太太,她德高望重,诚实可敬。因
每个人都向她汇报村里的情况,因此她对村里的
情况了如指掌,她知道每个男人都不忠。一天,
这位老人对这个女人说了一句很平常的话:“你
们的男人当中至少有一个是不忠的。”于是,村
里发生了这样一个事情:前天,村里风平浪静,
但到了第99天,村里发生了一场大屠杀,所有的
女人都杀死了她们的丈夫
为什么呢?

下面是对这个故事的解释。

"因 此最后,一个男人不忠,除了其妻子不知道外, 其他女人都知道。而事实上是,村子里的这 100对夫妇的男人都不忠"

所以可以知道,每个女人知道不忠的男人一共有99个,就是除了自己丈夫以外的男人不忠,她都知道,只是不知道自己的丈夫而已

“你们的男人当中至少有一个是不忠的。”
所以每个女人都会想,是别人的丈夫,那么别人会杀掉她自己的丈夫的。
A女人这么想,所以没有杀自己的丈夫
B女人也没有杀,也是这么想的
C女人也是这么想
D.E.F.....
所以第一天没有发生杀丈夫的事
第二天,A想,B之所以没杀,可能是因为B以为C会杀,所以她没动手;C之所以没杀,可能是因为C以为D会杀,所以她没动手;....
这是A想的,同样BCDEF....都是这么想
第三天,A想,B昨天之所以没杀,应该是以为D会杀吧?因为B发现C没有杀啊,所以肯定是在和自己一样想的。而C昨天之所以没杀,应该是以为E会杀吧?因为C发现D昨天没有杀啊,所以肯定是在和自己一样想的。
(发现什么?A的想法是:开始是B,后来是C,后来是D.....)
第四天,依此类推,知道第99天,她怀疑的所有人都没有杀,所以她知道了,大家在等她杀,于是她知道了,是自己的丈夫不忠了,于是就把自己的丈夫杀掉了
同时,别的女人也是这么想的,所以大家同一时间都把自己的丈夫给杀掉了


附录二

故事发生在一个村庄,村里有100对夫妻,他们都是地道的逻辑学家(智能的);村里有一些奇特的风俗:每天晚上,村里的男人们都将点起篝火,绕圈围坐举行会议,议题是谈论自己的妻子。在会议开始时,如果一个男人有理由相信他的妻子对他总是守贞的,那么他就在会议上当众赞扬她的美德。另一方面,如果在会议之前的任何时间,只要他发现他妻子不贞的证据,那他就会在会议上悲鸣怯哭,并企求神灵严厉地惩罚她。再则,如果一个妻子曾有不贞,那她和她的情人会立即告知村里除她丈夫之外所有的已婚男人(奇异的传统风俗)。所有这些传统和风俗都是村民的共同知识。
事实上,每个妻子都已对丈夫不忠。于是每个丈夫都知道除自己妻子之外其他人的妻子都是不贞的女子,因而每个晚上的会议上每个男人都赞美自己的妻子。
这种状况持续了很多年,直到有一天来了一位传教士。传教士参加了篝火会议,并听到每个男人都在赞美自己的妻子,他站起来走到围坐圆圈的中心,大声地提醒说:“这个村子里有一个妻子已经不贞了。”在此后的99个晚上,丈夫们继续赞美各自的妻子,但在第100个晚上,他们全都悲鸣怯哭,并企求神灵严惩自己的妻子。

为什么会有这样的结果?先对共同知识common knowledge作以解释。
解释一:共同知识指“所有参与人知道,所有参与人知道所有参与人知道,所有参与人知道所有参与人知道所有参与人知道…”。
解释二:如果每个参与人都知道某个事实,每个参与人都知道每个参与人都知道它,如此等等,从而形如“(每个参与人都知道)k (k次方)每个参与人都知道它”的语句对k=0,1,2,…都是正确的,那我们就称这个事实为参与人中间的共同知识。
解释三:这是一个“由己及人,由人及己”的无限推理过程,是k→∞时的高阶知识((每个人)k-1) (k-1次方)。一件事一旦在某个群体中成为共同知识,则从任何一个个体出发,他对这件事的理解等等都已达到了完全的统一,不再有任何层面的不确定性(奥曼,1976)。

下面是对这个故事的解释。
首先要明确,任何一个丈夫都知道除自己妻子以外的其他女人的真实忠贞状况,若只有一个妻子不贞,她的丈夫能够立刻知道这个不贞的女人就是自己的妻子,因为他的丈夫知道没有另外的不贞女人,若有的话他是知道的。既然如此,那么在传教士访问后的第一个晚上,丈夫A1没有哭,那就意味着确实存在一个女子不贞,若这个女人是丈夫A1的妻子,那么他当晚便会哭泣。但事实是他并没有哭,说明A1推断这个不贞的女人是他所知道的除自己妻子外的99个女子其中之一。对每一个丈夫An均是如此,他们既知道这个不贞的女子不是自己的妻子,也知道其他丈夫知道这个女子也不是他们的妻子。由此,从“第一个晚上没有男人哭”中可推断出:有两个女子已经不贞。在传教士走后的第二晚上,既然已推断出有两个女子不贞,而A1只知道一个,那另一个就是自己的妻子,故丈夫A1应该在“第二个晚上哭”。然而第二个晚上“丈夫A1也没有哭”,由此丈夫们推断出:已有三个女子不贞。由归纳法可以证明,对于1和100之间的任意正整数k,如果恰有k个妻子不贞,那么在传教士走后的连续k-1个晚上,所有的丈夫照样各自称赞自己的妻子,但在第k个晚上,k个不贞妻子的丈夫会悲鸣怯哭,于是,在99个赞扬之夜过后的第100个晚上,每个丈夫都知道一定有100个不贞的妻子。不幸的是包括自己的妻子在内!

传教士究竟告诉了丈夫们什么?每个丈夫都知道有99个不贞的妻子,故传教士所说的已经有一个女子不贞的话对任何人来说都不是什新闻。但“传教士对所有100个男人做了一个声明”是common knowledge,从而这个传教士所声明的内容(有一个妻子不贞)也就成了100个男人之间的common knowledge。在传教士宣告之前,每个形如“(每个丈夫知道)k有一个妻子不贞”的判断对于k≤99都是正确的,但对于K=100就不正确了。例如,若从1到100对丈夫们进行编号,则1已经知道2已经知道3已经知道……99已经知道100的妻子是不贞的,但1不知道2已经知道3已经知道……99已经知道100已经知道1的妻子是不贞的。因而从这个寓言中引申出的含义是,从一个共同知识的事实推出的结果与从只知道每个人已经知道每个人已经知道的事实推出的结果可以非常不同。

评分

参与人数 1小红花 +10 收起 理由
jason + 10 恶意灌水

查看全部评分

发表于 2008-10-26 12:57:01 | 显示全部楼层
数列啊,报纸上说了貌似。
发表于 2008-10-26 13:07:09 | 显示全部楼层
大一的时候听说过,以一道“微软面试题”的形式。
发表于 2008-10-26 14:05:08 | 显示全部楼层
已经明白了。
其实,大致是因为:
假设有一头病猪的情况:
有病猪的村民看到所有猪都是健康的,而限定条件是肯定有病猪,所以他必须要杀猪。

假设有两头病猪的情况:
第一天,无病猪的村民看到两头病猪(不理他们了)
有病猪的俩村民看到的是对方的一头病猪,于是他们俩等着对方杀猪。
但是第二天,他们看到的还是对方有一头病猪,于是知道自己的猪也是病猪。杀之。
所以,有两头病猪的情况是第二天死两头猪。

假设有三头的情况:
大部分村民看到的是有三头病猪。(不理他们了,肯定不杀猪)
有病猪的村民看到的是有两头病猪,所以,他们认为应该是有两头。
于是第一天,没人会杀猪。
第二天,有病猪的仨村民觉得,既然就俩病猪吧,这俩有病猪的家伙,一看对方各自有一头病猪,而且第一天没人杀猪,那还不就给杀了?
第三天,有病猪的仨村民一看,还没人杀猪,只有一种可能,就是自己有一头病猪。
所以。。。杀之。
发表于 2008-10-26 14:11:34 | 显示全部楼层
加精了,希望论坛多一些这样有内容的帖子~竹子是不会吝啬精华的
发表于 2008-10-26 15:39:21 | 显示全部楼层
好帖
发表于 2008-10-26 16:29:17 | 显示全部楼层
字多晃眼……吃碗泡面慢慢看~
 楼主| 发表于 2008-10-26 17:37:27 | 显示全部楼层
jason你才恶意灌水-。- 我明明是在百度知道里找到然后转过来的。
发表于 2008-10-26 18:31:55 | 显示全部楼层
原帖由 叉烧饭 于 2008-10-26 17:37 发表
jason你才恶意灌水-。- 我明明是在百度知道里找到然后转过来的。

小红花 +10
您需要登录后才可以回帖 登录 | 加入易码

本版积分规则

Archiver|手机版|小黑屋|EMAX Studio

GMT+8, 2024-3-29 02:25 , Processed in 0.010053 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表