作者jeff740212 (孤单旅行)
看板Inference
标题[讨论] 50只狗找病狗...IBM面试问题疑点
时间Wed Feb 22 06:35:23 2012
我凑巧在网路上看到这个问题
跟所谓的黑白机器人问题很相似
但是他的解答让我觉得有很大的问题....
IBM公司向来以高素质人才作为企业持续竞争力的保证。进入IBM公司是差不多每个IT人的
梦想，偶然看到这条IBM公司的面试题，给大家试试看，看看是否具备进入IBM的实力！
国国村子中有50个人，每人有一条狗。在这50条狗中有病狗（这种病不会传染）。於是人
们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病，只有自己的狗不
能看。观察後得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是
病狗就要枪毙自己的狗，而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。
第一天，第二天都没有枪响。到了第三天传来一阵枪声，问有几条病狗，如何推算得出？
======================不想看解答勿往下翻========================
第一种推论：
A、假设有1条病狗，病狗的主人会看到其他狗都没有病，那麽就知道自己的狗有病，
所以第一天晚上就会有枪响。因为没有枪响，说明病狗数大於1。
国国B、假设有2条病狗，病狗的主人会看到有1条病狗，因为第一天没有听到枪响，是病
狗数大於1，所以病狗的主人会知道自己的狗是病狗，因而第二天会有枪响。既然第二天
也没有枪响，说明病狗数大於2。
由此推理，如果第三天枪响，则有3条病狗。
第二种推论:
1 如果为1，第一天那条狗必死，因为狗主人没看到病狗，但病狗存在。
2 若为2，令病狗主人为a，b。 a看到一条病狗，b也看到一条病狗，但a看到b的病
狗没死故知狗数不为1，而其他人没病狗，所以自己的狗必为病狗，故开枪；而b的想法与
a一样，故也开枪。
由此，为2时，第一天看後2条狗必死。
3 若为3条，令狗主人为a，b，c。 a第一天看到2条病狗，若a设自己的不是病狗，
由推理2，第二天看时，那2条狗没死，故狗数肯定不是2，而其他人没病狗，所以自己的
狗必为病狗，故开枪；而b和c的想法与a一样，故也开枪。
由此，为3时，第二天看後3条狗必死。
4 若为4条，令狗主人为a，b，c，d。a第一天看到3条病狗，若a设自己的不是病狗
，由推理3，第三天看时，那3条狗没死，故狗数肯定不是3，而其他人没病狗，所以自己
的狗必为病狗，故开枪；而b和c，d的想法与a一样，故也开枪。
由此，为4时，第三天看後4条狗必死。
5 余下即为递推了，由年n－1推出n。
========================解答结束===========================
已解决 原来是语病问题....
什麽第三天看後....(其实就应该是第四天)
不过如果题目条件加一个当场杀,
都会在第一天死掉.....是否有人跟我有同样想法?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 66.27.219.104
※ 编辑: jeff740212 来自: 66.27.219.104 (02/22 06:36)
1F：→ puzzlez:推论1和推论2还不是一样 02/22 06:40
2F：→ jeff740212:不一样耶 一个是第三天有三只 另一个有四只 02/22 06:46
3F：→ jeff740212:推论一的成立条件应该为各自回家晚上在杀 02/22 06:47
4F：→ jeff740212:推论二的条件如果为当场杀 那我觉得还是不成立 02/22 06:49
5F：→ puzzlez:这跟何时杀没什麽关系 而且推论2只是把答案扩展为n只而已 02/22 06:50
6F：→ puzzlez:例如你第一天看到了3只病狗 那你要杀掉自己的狗吗？ 02/22 06:51
7F：→ jeff740212:那两个推论出的第三天病狗数量怎麽会不同? 02/22 06:52
8F：→ puzzlez:推论二能够告诉你第一天要不要杀自己的狗？ 02/22 06:52
9F：→ puzzlez:哪里不一样？病狗若有三只 当事人只能看到二只不是？ 02/22 06:53
10F：→ jeff740212:原来....看推论2的第4点 他应该改为第四天四条狗必死 02/22 06:58
11F：→ jeff740212:什麽第三天後四条狗必死就怪了 第n天 = n 才是 02/22 07:00
12F：→ puzzlez:它写 第三天看後....是啦...有语病.... 02/22 07:01
13F：→ jeff740212:原来 害我还想那麽久 感谢 不过我还在想当场杀的话 02/22 07:03
14F：→ jeff740212:第一天不管几只病狗都会死光 02/22 07:04
※ 编辑: jeff740212 来自: 66.27.219.104 (02/22 07:07)
15F：→ puzzlez:并不会 02/22 08:42
16F：→ puzzlez:例如你第一天看到了3只病狗 那你要杀掉自己的狗吗？ 02/22 08:42
17F：→ puzzlez:如果你不能确定的话 其他人又怎麽能确定？ 02/22 08:43
18F：→ puzzlez:而且这跟杀狗时间 一~点关系也没有 02/22 08:43
19F：→ puzzlez:不管是哪一天的早上 中午 晚上杀 都没差 02/22 08:44
20F：推 luciferii:错....因为进入IBM才不是每个IT人的梦想 :P 02/22 11:52
21F：推 tp:杀狗时间有关系阿，我看到了1只病狗，过了一会儿还没死 02/22 16:34
22F：→ tp:那我是不是就可以立刻杀掉自己的狗了? 02/22 16:35
23F：→ remvsd:过了一会还没死,那是因为还没过这天啊,病狗的主人在还没过 02/22 19:48
24F：→ remvsd:这天之前就杀的话,那不管几只病狗,第一天都可以全部杀光了 02/22 19:49
25F：→ remvsd:这种题目应该都是预设杀狗时间是在当天最後一刻,不然就没意 02/22 19:50
26F：→ remvsd:义了 02/22 19:50
27F：→ puzzlez:我已经不知道该说什麽了..... 02/22 21:43
28F：推 kuoll:这题目表达的很烂(但是大家依经验都知道它要问什麽) 如果题 02/22 22:58
29F：→ kuoll:目叙述的严谨一点我相信推文的争论就会解开了 02/22 22:59
30F：→ teves:为什麽要进IBM? 我听过微软->google->facebook的演进说法 02/23 13:50
31F：→ teves:可这里面根本没有IBM XD 02/23 13:50
32F：→ jeff740212:哈哈 IBM不是我说的拉 是那个题目上本来说的! 02/23 15:53
33F：推 lovejessie19:假设病狗4只 那二天就可以看出来了不是吗? 03/04 01:32
34F：推 lovejessie19:第二天A假设B只能看到两只 所以就应该杀自己的狗了 03/04 01:35
35F：→ lovejessie19:可是都没人开 代表B有看到3只 所以是4只... 03/04 01:36
36F：→ lovejessie19:这问题真的有解吗.... 03/04 02:11
37F：→ lovejessie19:答案就是4条 lol 03/04 03:28
38F：→ lovejessie19:不对是3条 因为第一天不开枪才会知道有两条以上 03/04 13:02
39F：→ lovejessie19:所以第二天不开才会知道3条以上 正解无误solved 03/04 13:03
40F：→ up1205:想想难吧 03/08 10:32
41F：推 skyfire:为什麽一天只能看一次狗?....一天看十次不行吗? 03/28 15:38
42F：推 waveflower:这题跟背後画圈圈叉叉的题目好像喔 03/31 19:34
43F：推 TAGOSAKU: 推论二的第三条开始就不成立了吧...... 03/11 13:58