病狗的推理

西部者

五十个人每人有一条狗，五十条狗中必然有病狗存在。
( L! T3 Y/ U: V; P/ }) t. ~每个人只有能力直接观察并判断别人的狗是否有病，但无法直接判断自己的狗是否有病（只能靠推理），并假设一个人观察一遍别人的狗需要一整个白天的时间。
每个人只有权利杀死自己的病狗，无权杀别人的狗也无权帮助别人判断其狗是否有病。
第一天，无任何事情发生
5 o7 F5 N4 U" f) x第二天，也没有任何事情发生
第三天，响起一阵枪声
( z" k( P: }& f7 E问有几条病狗？

afish1984

这貌似是个双循环编程题，以前做过，记得答案是3。

西部者

正解　

prefix

这种题没什么意义，第三天全部都是病狗，而且人都有可能被咬了。直接上医院检查才符合逻辑。

网虫

貌似没有了吧

三生石

主要是病狗的攻击性太强了，改病猫吧。
6 Q5 U  X4 L% @9 c+ x答案是：3只。

兴奋

有好狗的人看到的病狗数比有病狗的人看到的多1条。
$ U7 V2 y6 n% V
等我去百度一下 记得有一个制度和逻辑的讨论就用的是这个题。

兴奋

http://blog.chinaunix.net/u1/43206/showart_1796899.html
( P+ D  m  A1 ]. G1 k$ c3 Z( r9 @. @/ D
& a3 b3 d* ^+ G' @+ C' Y问题提出后，引发了各种各样的结论。这是有趣的，说明人和人的思维方式竟然可以如此不同。也有人的兴趣不在解决这个问题上，而以寻找问题本身的破绽为乐趣。在找出的破绽中，有一些显然是思考者自己的误解，但有两个问题确实存在：
4 C7 u+ g6 X* ?0 Q; P1、该题目中没有事先约定做出一轮判断的时间周期，因而这不是预设的公共知识。题目中也没有对众人是否可以就这个问题进行讨论做出规定，因而我们也无法确认人们是否能在这个过程中形成这样的公共知识。而事实上，这一公共知识是解决问题的关键之一。
4 V) x) U" [* d+ r2 G2、有人指出，既然每个人都不准观察自己的狗，那么他们如何枪毙自己的狗？这并不是一个严重的错误，但确实有必要增加一点约束条件：比如，每个人都知道自己的狗在哪里，并且在决定打死自己的狗之后不得后悔，即使是第一眼就发现自己的判断失败也不能例外。
也有一些比较熟悉推理题的朋友指出，其实这个问题有很多变种，比如有颜色的帽子、额头上的泥巴、不忠的妻子或丈夫，还有朋友重新设计了这一题目。这些都是有道理的。
+ x0 K3 `& x( C; v7 M+ s6 }/ [事实上，所谓“病狗问题”可以用以下的形式化语言描述：
1、存在N个具有完全理性能力的人；
2、存在一种可被识别的特征，每个人都可以立刻发现别人、但永远不能发现自己是否具有这种特征；
# b  x7 d% {: V. q) z" S$ M) K) _3、至少有一个人具有这种特征；
' L% V" n2 r" f7 ?; Y4、具有特征的人一旦确定自己具有该特征，就应该立即采取某种行动；
6 Y" v2 K+ g+ j0 x5、约定一个判断周期，在每一个判断期内，每个人只做出一次判断；
6、在整个过程中，所有人彼此不得通过语言（包括形体语言和文字等形式）进行交谈；
" W2 h6 F" q7 o3 t2 |7、任何人一旦决定采取行动，就不得后悔。
+ n$ p' U2 W& O, ~# y& y  n) e' ]在以上的约束条件下，这个问题在逻辑上是有解的。那就是，假如有X个人具备该特征，那么他们将在第X天做出正确的判断并采取行动。反之亦然，如果在第X天有人采取了行动，那么具有该特征的人也就是X个，他们将不约而同地采取一致行动。
: k) F) A# r8 w得出这个结论的人，大多数具有较多的逻辑知识或较强的逻辑能力。他们的推导过程，大概是这样的：
《推理方式一》
7 r5 v$ G9 s1 E7 q【第一天】
1.0 至少有一条病狗（预设条件）；
1.1 如果有人没有看到病狗，那么他将在第一天开枪；
( p7 X; U! \- \7 d1.2 如果第一天结束仍没有人开枪，说明所有人都看到了病狗；
1.3 有病狗的人看到的病狗比有好狗的人少一条，所有人都看到了病狗，说明至少有两条病狗。
【第二天】
2.0 至少有两条病狗（上一天结论）；
  e1 W$ b7 A0 @8 Z0 k7 T2.1 如果有人只看到一条病狗，那么他将在这一天开枪；
2.2 如果这一天结束仍没有人开枪，说明所有人都看到了两条以上的病狗；
$ M3 Y2 Z* X$ G9 U3 G# v2 y2.3 有病狗的人看到的病狗比有好狗的人少一条，所有人都看到了两条以上的病狗，说明至少有三条病狗。
( A' d+ B" m. A0 K. J8 H" h……
6 l5 G+ K+ {# B【第X天】
X.0 至少有X条病狗（上一天结论）；
X.1 如果有人只看到X-1条病狗，那么他将在这一天开枪；
6 @  k7 D' `# x- E. T2 bX.2 如果这一天结束仍没有人开枪，说明所有人都看到了X条以上的病狗；
X.3 有病狗的人看到的病狗比有好狗的人少一条，所有人都看到了X条以上的病狗，说明至少有X+1条病狗。
1 b8 ]- m6 B; w9 O* Z9 r) y( Q0 H……
上面的推理过程可以一直延续到最后一天（第N天）。但在实际只有X条病狗的情况下，它将在第X天，准确来说是在第X.1这一步终结。因为有病狗的那些人，在这一步已经可以做出开枪的决定。
" x: ?, o* }* F, R4 H9 P$ t4 ?从纯粹形式化方法的角度看，上述推理似乎是严密的，没有任何问题。在某种程度上，它也说明了形式化系统对于构建人类公共知识和帮助人们做出行为选择的重要意义。
2 j1 T2 o- U# }* M/ m( Z但这个推理过程也会遭遇各种质疑，最有力的一种，在于对游戏成员的“聪明程度”做出了更高的估计（根据我们的初始假设，对他们的理性程度做出任何高估都是不过分的）：
" [" n) l6 @, ]" m( C《推理方式二》
/ z( ^, K* [$ P* v3 o8 X$ D1、假如有人看到了4只病狗。
2、那么，他本人可以确信，至少有4只病狗，而且不是4只就是5只。
2 ~( Z- T/ O  W; v: R3、他也可以确信，有一些人的情况和他完全相同，包括掌握的信息和做出的判断。
4、他还可以确信，和他不一样的那些人，也至少确信有三只病狗，并至少确信其他人看到了两只以上的病狗。
2 ~% V! v7 O. }( c* n+ W5、所以，他可以确信：所有人都确信、并确信其他人也都确信有两只以上的病狗。
& F) m- R  s+ {7 a1 O6、所以，至少有两只病狗，从第一天开始就是公共知识。
2 A) {' l0 [- l( u( b# l  n6 W- h% f7、既然有两只病狗是公共知识，那么我们的推理可以跳过第一天，直接从2.0开始，这样在第3天，而不是在第4天，看到4只病狗的人将开枪射杀他们的狗。
推广到更普遍的情况，在X>3的情况下：
4 h" g8 ^* Y9 z, Z# m( w; u4 U2 D" V1、假如有人看到了X只病狗。
2、3、4、5、同上。
( v  K  H9 L( r! P+ b$ U3 P6、所以，至少有X-2只病狗，从第一天开始就是公共知识。
7、既然有X-2只病狗是公共知识，那么我们的推理可以跳过前X-3天，直接从X-2.0开始，这样在第3天，而不是在第X天，看到X只病狗的人将开枪射杀他们的狗。
也就是说，在假设这些人更聪明的情况下，他们反而可能作出错误的决定。最后的结论是：
1、在X不超过3（包括3）的情况下，病狗的主人将在第X天正确地射杀他们的狗，而好狗的主人也将正确地按兵不动，事后所有人都将获得全部的正确信息。
2、在X超过3（从4开始）的情况下，无论病狗或好狗的主人，都将在第3天开枪射杀所有的狗，而且事后大家只知道别人是否犯了错误，不知道自己是否犯了错误。
这一推理看上去更加严密，并似乎说明了人类理性的某种极限或缺陷。但事实上，它的推论过程是有问题的。原因在于它对公共知识的定义漏了一步。严格来说，只有在满足以下约束条件的情况下，一种知识才能称为“公共知识”：
  {% h- U" r! `' v* O" [. F1、所有人都知道它；
; E. r! g/ e6 Q3 a( ~/ o7 s1 ^: @# S- }7 g9 j2、所有人都确信其他人也都知道它；
) v. ^1 k- V; C( t. {3、所有人都确信其他人也都确信其他人都知道它；
4、所有人都确信其他人也都确信其他人都确信其他人都知道它；
) |4 Q, V6 D0 ~" G……
5 e+ |$ x# z6 M) o! s, G' i/ U这个约束条件可以一直写下去，直到无穷无尽为止。
确定了这个约束条件，我们就可以知道，第一种推理方式是没有问题的，它里面引入的每一个公共知识都能满足上述的条件。而第二种推理方式有问题，问题发生在第5步到第6步。“至少有X-2只病狗”不是公共知识，它只能满足约束条件的前两步，到了第三步就会有问题。不仅如此，“至少有X-m只病狗”也不是公共知识，它会在第m+1步遇上问题。所以，任何提前启动、跳过推理方式一中任何一天的想法都是自作聪明的。
& x2 E9 b: g. ~% R7 S这个例子并不能说明人类理性的缺陷，因为真正满足无限理性假设的人将会认识到这个陷阱，并避免不切实际的超前想法。他们将严格按照推理方式一的步骤进行，直到最终得到正确的结果。
但这个例子说明了建构公共知识的困难。任何一种知识，只要不是通过公开的、面向大众的方式来进行，它就无法成为真正的公共知识。小道消息和猜测产生的公共知识，其根基是不稳固的，即使我们所有人最后都知道了关于事实的真相，但我们无法知道他人对真相的掌握程度，因而难以进行有效的行为选择。为什么公众言论的自由、新闻发布的自由是重要的？我想这个例子能够说明一些问题。
但在我看来，解决这个问题还有更简单的方式，它甚至不需要“所有人都具备完全理性”这一在现实中根本不可能的假设条件。而在上述方式中，这一假设是至关重要的，因为只要有任何一个人认识不到推理方式二中的陷阱，他就有可能发生错误。而假如他不能建立象推理方式一那样严密的形式系统的话，他就很有可能茫然不知所措。
我说的这种简单方式，就是每个人不是通过逻辑推理，而是通过假想一种制度安排来实现。
5 M  e' H' m: D( A4 ?2 k也就是说，每个人都这样设想：
4 b- j  {3 V6 r/ n! X1、无论我的狗是病狗还是好狗，总之好狗的主人看到的病狗多一条。
2、只要有一种方法，能让看到病狗少的人先动手，就能杀死所有的病狗。
3、如果我们看到了X只病狗，就在第X天动手；这样看到病狗少的人就会提前一天轮到。
4、只要大家都这样做，就一定不会出错。
解释清楚这样一种制度安排，显然比普及推理方式一中的逻辑知识要容易，与澄清推理方式二的难度更是不可同日而语。只要在向每个人说清楚规则之后、在让他们看到狗之前允许一个简单的沟通，他们中间的少数聪明人就极有可能提出这种安排，并获得其他人的同意。而这些人，显然不需要个个都是逻辑专家。
由此我们可以看出，制度安排为传递知识提供了机会。即使在初始设定6的苛刻限制下，人们仍有方法和他人交流信息。“看到X只病狗就在第X天动手”，这种制度安排提供了一种通过时间而不是通过语言，来传递“我看到了多少只病狗”这一信息的方式。
所以，这个例子告诉我们，一种好的制度安排，比每个人都聪明绝顶可能更为重要。它也告诉我们，人类的创造力和必要的沟通，是好的制度安排出现的原因。而无论现存的制度多么苛刻，只要它还能为个人选择和人际沟通留下一点点空间，突破限制的新的安排、或者说自发的秩序就一定会出现。就像被巨石压迫的种子，只要春天来临，它就一定会生根发芽，破土而出。

lilymoon

看晕了，我是动物保护主义者，有病也不一定要杀呀