微軟面試題病狗

一個住宅區內有100户人家，每户人家養一條狗，每天傍晚大家都在同一個地方遛狗。已知這些狗中有一部分病狗，由於某種原因，狗的主人無法判斷自己的狗是否是病狗，卻能夠分辨其他的狗是否有病，現在，上級傳來通知，要求住户處決這些病狗，並且不允許指認他人的狗是病狗(就是隻能判斷自己的)，過了7天之後，所有的病狗都被處決了，問，一共有幾隻病狗?為什麼?

7只(數學歸納法證明)

1)若只有1只病狗，因為病狗主人看不到有其他病狗，必然會知道自己的狗是病狗(前提是一定存在病狗)，所以他會在第一天把病狗處決。

2)設有k只病狗的.話，會在第k天被處決，那麼，如果有k+1只，病狗的主人只會看到k只病狗，而第k天沒有人處決病狗，病狗主人就會在第k+1天知道自己的狗是病狗，於是病狗在第k+1天被處決

3)由1)2)得，若有n只病狗，必然在第n天被處決