题目:50人有50条狗,有病狗。每个人只能看到其他人的狗(不能看到自己的狗),只有狗的主人才能打死狗。相互不能交流,不能通知狗的主人。如果推断出自家狗是病狗,就要枪毙,只能枪毙自家狗。第一天没有枪声,第二天有一阵枪声。请问有几只病狗?
听说这是小升初的考试题,这实在是太难了,怀疑那些出题的老师第一次看到这个题能不能做出来。这应该是离散数学中典型的逻辑分析题,我想除了专门修过离散数学和少数天才外应该很少有人在规定时间内算出答案,反正我算不出。下面的分析过程,是我参考了网上的答案,再按照自己的理解写出来的。
其实我认为这个题之所以难,我觉得是题目表达的不够清晰。理解这个问题首先有几个隐含的条件要搞明白。
a、50只狗里面至少有1只病狗。
b、病狗是一眼就能分辨出来的,但是狗的主人无法观察判断自己的狗是不是病狗。
c、狗的主人推断出自己的狗是病狗后,一定要在当天杀死狗,在当天中的0:00到24:00任何时候都行。
从而还能得到一个推论d:如果病狗的主人看到N只病狗,那么好狗的主人能看到N+1只病狗,也就是说病狗的主人看到的病狗的数量是实际病狗数量再减1.
明确了上述的3个条件和1个结论,再去解答这个问题,就会简单很多。
1, 假设只有1只病狗,所有人在观察完其他人的狗后,那么根据推论d,病狗的主人不会看到病狗,再根据条件a,从而能够推断出自己的狗是病狗,于是会在当天24点之前杀死自己的狗。
2, 但是第一天没有枪声,说明至少有2只病狗(把这个结果当成推论e)。于是从第二天0:00开始,所有人都应该知道至少有两只病狗。假设只有2只病狗,根据推论d,病狗的主人只看到1只病狗,说明剩下的那只没有看到的病狗就是自己的狗,于是在第二天可以从0:00到24:00选择任何一个时间点杀死自己的狗,第二天就会听到枪声。
3, 继续假设有3只病狗的话。由根据推论d,病狗的主人能观察到2只病狗,再根据推论e,所以无法判断自己的狗是否为病狗,所以在第二天不可能杀狗,也就不会有枪声,综合1和2,答案为2只狗。
4, 把题目改一下,改成是第三天听到枪声。第二天0:00一到,大家都知道有2只病狗了,那么第二天一直到24:00都没有枪声的话,说明每个人都看到至少2只病狗。根据推论d,那么从第三天0:00开始,每个人会知道至少有3只病狗。假设也只有3只病狗,那么病狗的主人只能看到2只病狗,说明剩下的那只没有看到的病狗就是自己的狗,于是在第三天肯定要杀死自己的狗,第三天就会有枪声。
5, 以此类推,第几天听到枪声,就有几只狗。