2014年12月25日星期四

用数学归纳法证明病狗问题

《数学文化》课程的第一个作业,是用数学归纳法证明病狗问题的病狗数等于枪声响起的天数。

题目如下:

一个屋子里面有一群人(人数>1),每人领着一条狗,而这些狗中有一部分病狗(数目>0)。假定有如下条件:

1、狗的病不会传染,也不会不治而愈;
2、狗的主人不能直接看出自己的狗是否有病,也不能互相交流,只能靠看别人的狗和推理,来发现自己的狗是否有病;
3、一旦主人发现自己的狗是一只病狗,就会在当天开枪打死这条狗;
4、狗只能由他的主人开枪打死。

如果他们在一起,第一天没有枪声、第二天没有枪声……第n天发出了一片枪声,问有几条狗被打死?



证明:

引理 若一个人看到m只病狗,则有以下两种可能:

(1)这个人的狗也是病狗,即实际有m+1只病狗;

(2)这个人的狗不是病狗,即实际有m只病狗。

根据题目的条件,引理是显然成立的。

下面用数学归纳法证明,若有n只病狗,则会在第n天发出枪声。

(1)当n=1时,病狗的主人看到0只病狗,而由题目可知,病狗数目大于0,故由引理,病狗的主人可以推知自己的狗是病狗。所以第1天就会响起枪声。

(2)假设当n=k(k>=1)时,会在第k天发出枪声。下面证当n=k+1时,会在第k+1天发出枪声。

根据引理,因为有k+1条病狗,所以前k天,病狗的主人们都只看到k只病狗,其余人都看到k+1只病狗。因不能交流,一直到第k天,他们都不知道到底有k只还是k+1只病狗。所以,前k天都没有枪声响起。而到了第k+1天,病狗的主人们意识到病狗的数目应不等于k(若等于k,则第k天就会有枪声响起了,矛盾),即引理的第(1)种情况,所以病狗的数目为k+1。所以,第k+1天,病狗的主人们知道了自己的狗是病狗,就会在当天开枪打死这条狗。

(3)由(1)、(2)可知,若有n只病狗,则会在第n天发出枪声。




 

后记: 在为这篇文章选择分类的时候竟然犯了难。以前(高中)将博文分成三类,“技术谈”存放技术类的文章,“杂文集”存放自己表达的一些看法或感受,“生活记”用来存放一些生活记录和总结。而这篇文章,证明一个数学问题,我想到的第一个名字竟然是“学术”。“技术”和“学术”,一字之差,个中滋味,非身处学术类培养计划之下而热爱技术之人所能理解。

2 条评论:

  1. Buy Titanium Frame Hammer | ITN:Ti-CITY-START | INN:TITanium-ART
    Titanium Frame Hammer is one of the micro touch titanium trimmer best crafted titanium earrings hoops aluminum frames made from titanium steel with a implant grade titanium earrings top notch titanium sponge finish. Our w88 top-rated aluminum frame

    回复删除