MBA On Line 论坛
作者 心情 主题
peanut 发表于: 10月7日 23:22 作者 寄信 编辑 回复 删除 转移 精华区 隐藏IP
--------------------------------------------------------------------------------
一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。然而所有主人和他们的狗都不能够离开自己的房子，主人与主人之间也不能通过任何方式进行沟通，他们能做的只是通过窗户观察别人家的狗是否生病从而判断自己的狗病否。（就是说，每个主人只能看出其他49家的狗是不是生病，单独看自己的狗是看不出来的）
第一天没有枪声，第二天还是没有枪声，第三天传出一阵枪声，问有多少条狗被枪杀。
（绝非脑筋急转弯，有答案的朋友请详细说出你的解答思路）
James_GZ 回复于：10月8日 0:36 删除 隐藏IP
--------------------------------------------------------------------------------
总共有三条狗被杀，听到三声枪响。
这个题和中大岭南IMBA 2001 Orientation中的一个游戏“谁是外星人”是一样的，如果这里有我们“太行队”的成员应该都知道这个题的答案。当时我们是用数点数的方法解决的，每5秒数一点，让大家做判断，数到4就顺利完成。
解题思路如下。因为至少有一条狗有病，所以：
1. 假设只有一个狗有病，必然有某个人在第一天就会看见另外49条狗都没有病，立即就能判断是自己的狗有病，那么他一定会开枪，第一天这个问题就解决了。如果所有人都能看见别的49只中有病狗，则没人可以做出判断是否自己的狗也有病，因此等到第二天。
2. 如果第一天没有枪声，所有的主人都会明白病狗多于一只。到了第二天如果有人看见另外49只狗中只有一只有病，他立即就能判断出自己的狗也必然有病，这样有病的狗才会多于一只，他就可以做出判断然后开枪，这样如果是两只狗有病，在第二天必然会有两个人可以做出这种判断，两声枪响，问题结束。注意：在第二天枪响，则只可能有两只病狗，不可能是三只或以上，否则每个人都会看到至少两只病狗，则没人能做出判断，也就不可能有枪声。
3. 如果第二天仍然没有枪响，说明病狗多于两只。第三天时如果有人看见另外49只狗中有两只有病，必然自己那只也会有病，他就可以立即判断然后开枪。必将会有三个人可以做出这种判断，三声枪响，问题结束。
4. 如果第三天仍然没有人开枪，说明所有的人看到别的49只狗中都至少有三只病狗，没人能做出判断，则要等到第四天。
5. 综上所述，第几天听到枪声就说明总共有几只狗有病。第三天听到枪响必然是三只狗有病，听到三声枪响。
看来M记的面试题也不过如此，什么时候也找点俺们I记的面试题给大家玩玩。
Edited by - James_GZ on 2001-10-8 0:52:57
谁倚西楼淡月 回复于：10月8日 11:14 删除 隐藏IP
--------------------------------------------------------------------------------
我看不明白呀！怎么回事？
如果有三只狗生病了，第三天里主人能判断出自己的狗生病了，那么第一天里主人也会发现的呀。我就是想不明白，还望解释。
潇潇女 回复于：10月8日 14:39 删除 隐藏IP
--------------------------------------------------------------------------------
TO：James_GZ。你太厉害了！我还没有开始想，你的答案就出来了，思路如此清晰，佩服！
谁倚西楼淡月 回复于：10月9日 8:53 删除 隐藏IP
--------------------------------------------------------------------------------
潇潇女，你是真弄懂了James_GZ的解释？指教一下了。
我不明白主人是怎样知道够生病了，只要发现自己的狗和别人的狗不一样？也不对呀，如果只有一条狗没生病，那岂不是错杀49只了？
明白人，请解惑。我这里多谢了。
潇潇女 回复于：10月9日 9:31 删除 隐藏IP
--------------------------------------------------------------------------------
呵呵呵，我也认为是3或47
清蓝 回复于：10月9日 9:56 删除 隐藏IP
--------------------------------------------------------------------------------
请注意题目中有这样一段话：“（就是说，每个主人只能看出其他49家的狗是不是生病，单独看自己的狗是看不出来的）”
这就是为什么只是3而不是47，因为到了第三天，病狗的主人只能看到两只病狗，其余主人看到的是三只，所以病狗的主人可以判断出自己的狗有病，然后开枪杀死自己的狗。
当然，我个人认为，这道题出得不是太好，不如岭院今年ORIENTATION中的“WHO IS ET”的游戏，其实这两道题道理是一样的，但在“WHO IS ET”的游戏中，是在每个人的额头上贴一张纸条，所有人的纸条分两种颜色，假定为红色和蓝色，而贴红色纸条的人为外星人。然后大家围成一圈，每个人能看到其他人纸条的颜色，但看不到自己的，也不许大家用任何方式进行沟通，让大家想一个办法在某个时候所有外星人都退后一步出这个圈子，就算找出了所有外星人，当然不能多也不能少。
病狗这道题可能的毛病在：
1、主人单独看自己狗是看不出来是否有病，但这不合生活常理，就象前面兄弟说的一样，主人会去比较。但其实这道题的（）内的前提就是想表达：就当主人看不见自己的狗，狗藏在自己身后，需要的时候回手一枪把它干掉就行了，呵呵。这里也引出第二个可能的毛病：
2、一定要强调枪响是主人干掉自己的狗，否则有可能大家能互相看见别人的病狗，熬到第三天，一阵乱枪射杀别人的狗，就谁也不知道有几只病狗了，呵呵。
我想大家看看“WHO IS ET”这道题会更明白些的。
潇潇女 回复于：10月9日 10:32 删除 隐藏IP
--------------------------------------------------------------------------------
我把这个题目发给一位朋友做，一小时后，回复过来：主题是“一群疯狗”，内容是“我猜50只狗全死了。”呵呵呵。
James_GZ 回复于：10月9日 11:20 删除 隐藏IP
--------------------------------------------------------------------------------
这道题的其实在考你对别人反应的理解能力。不过整个思路描述起来比较费劲（本人本科是学计算机的，语文没学好，
sorry!），这里再补充描述一遍，希望你能明白，如果哪位网友看明白了我的思路，又能用更易理解的方式描述出来，本人不胜感激。
根据题目的要求，并不是要看自己的狗和别人的狗有什么区别来判断自己的狗是否是病狗，如果题目更严密一点，甚至可以说每个主人都不能看到自己的狗。这个问题实际是要你根据别人的反应和作出反应的时间来判断出病狗的数目以及自己的狗有没有病。当然前提是所有的狗主人都要明白这个题的解决思路，而且每做出一步判断前必须有一个约定好一致的等待时间间隔来保证所有人的行动同步，否则任何一个人提前开枪或者该开枪的时候没有开枪，其他人就再也无法作出正确判断了。本题这个时间间隔实际是假定1天。
假设你是一个主人。
1. 在第一天，如果你从别的49只中没有看到病狗，那么必然只可能是你自己那只有病。但是如果你从别的49只中可以看到1只以上病狗，你就无法马上判断自己的狗是不是有病了，这时候你就就需要等待别人的反应（等待时间间隔为1天）。你自己应该明白如果只有1只病狗，那么必然有另外一个人可以看到其他的49只中没有病狗，他可以做出判断，第一天就会开枪，如果第一天结束时还没有枪声，则说明因为其他所有人也都可以看到病狗，所有人都无法第一时间作出判断，这时候你就应该明白病狗的总数肯定大于1个。
2. 到了第二天，因为根据第一天大家的反应你已经知道了病狗总数肯定大于1，这时候如果你面前的另外49只狗中只有1只病狗，你就可以轻松的判断出自己的狗肯定有病，这样病狗总数才能大于1，但是如果你面前49只中有2只或以上的病狗，你就无法立即判断自己的狗是否有病了，因为你所看到的已经大于1了。此时你就什么也不能做，只能继续等待别人的反应（等待时间间隔仍然为1天）。你自己应该明白，在第二天你自己如果无法判断并不意味着别人无法判断，如果只有两只病狗，则这两只病狗的主人分别可以看到另外49只中只有1只病狗，他们可以判断。如果第二天也没有枪声，说明所有人看到的另外49只狗中都至少有2条病狗，这时候你就应该明白病狗的总数肯定大于2个了。
3. 依次类推，每天结束时你都可以判断出病狗的最少可能数量，后一天你就可以根据看到另外49只中的病狗数和上一天结束时判断出的病狗最少可能数，对自己的狗是否生病做判断。如果看到的病狗数等于最少可能数减1，立即就可以判断出自己的狗有病；如果看到的病狗数大于等于这个最少可能数，你就不能判断，需要再等一天。
这道题实际上暗示了大家每一步判断的时间间隔是一天，实际上，大家都明白思路后，不一定每一步判断需要一天，可以找一个人来数点数也一样，例如：待所有人就位后，裁判开始数1,2,3...，每10分钟数一下，每个人心里坚持一个原则，就是你看到的另外49只中有n只病狗，那你就在裁判数到n+1后开枪，不能快也不能慢，如果在数到n+1前已经有人开枪了（前提是开枪的人也明白这个思路，不是乱开枪），恭喜你，你不用开枪了，你的狗没问题，问题已经解决了。
潇潇女说的47只这种可能性我不明白是怎么推断出来的，能解释一下吗？我个人觉得不可能啊。你是不是这样想的，如果条件明确说至少有一只狗没有病，用类似方法倒着推算，如果第一天有人看到另外49只狗全有病，他的确立即可以判断出自己那只肯定没病，但是这种情况下他能做的就是不开枪（而不是发出开枪这个信号），另外49个人因为无法判断，也不会开枪。在这种思路下，因为首先能够做出判断的人发不出任何信号，问题实际上是无法解决的。除非说一旦判断出自己狗没有病的可以发出个特别信号，例如举个旗子什么的，这样别人才能继续判断，才可能用递减的方法在第3天判断出47只病狗，如果没有特别信号，是无法作出47只这个结论的，只能是3只。
好了，已经写晕菜了，越写越乱。如果还没明白，俺就没办法了。
潇潇女 回复于：10月9日 11:43 删除 隐藏IP
--------------------------------------------------------------------------------
你又没有给生病和不生病的区别，只能判断处于两种状况的狗各有几只，这两种状况哪种是生病，哪种是不生病又没有标准，我怎么知道？题目说的是“每个主人只能看出其他49家的狗是不是生病，单独看自己的狗是看不出来的”，也许第三天打死的正好是全部没有病的狗呢！呵呵呵！
