节选张顺燕主编的《心灵之花》.doc

节选张顺燕主编的《心灵之花》 面试中的数学归纳法 ——论一道微软面试题的数学思考 在微软的一次面试中，面试官出了一道非常让人意外、非常经典的题目，就是“一个屋子里面有五十个人，每个人领着一条狗，而这些狗中有一部分病狗(不少于一条)。假定有如下条件：一、狗的病不会传染，也不会不治而愈。也就是说病狗的数量一直不会改变；二、狗的主人不能看见自己的狗是否有病，但是狗的主人只有通过别人的狗是否有病才可以看出自己的狗生病了没有；三、一旦主人发现自己的狗肯定是一只病狗，就会在当天开枪打死这 条狗；四、狗必须由他的主人亲自动手开枪杀死。如果他们在一起第一天没有枪声、第二天没有枪声、第三天发出了一片枪声，问有几条狗被打死。” 所有的人面面相觑，都哑然。这是一道什么样的题目呢？几乎都在思考，都在想这是一个什么样的脑筋急转弯?还是一个什么样的智力游戏?很多人面对这个问题就是束手就擒，甚至就直接由此退出了面试。这时开始有人抱怨微软竟然拿这道非常无聊的题目来刁难大家。也许是因为当时太紧张，也许是因为大家的思路没有被打开，不自觉地大家开始了讨论，但是于事无益。几乎没有几个人答出了这道题。很多人都因为这道题目的怪异而思路主要在于想为什么会有这道题?为什么微软的面试官会出这种题?为什么会在微软的面试中出现这种几乎是与微软的世界不相关的把戏?大家惟独没有想清楚的是这道题与微软到底有何干 系?为什么微软出了这道让大家颇为郁闷的题。这其实是一道数学题，一道非常标准的数学推断题。有数学的头脑，有明确的思路，解这道题其实是一件非常简单的事情。 这道题本来是一个很简单的数学归纳法的应用。我们先来审题，将其题设变成我们的语言和思维，这是解题必须的步骤。题设条件解读结果如下：一、肯定有狗生病，也就是说病狗的数量大于零；二、病狗的数量不会发生变化；三、狗的主人只有通过看别人的狗来确定自己的狗生病了没有；四、如果主人发现自己的狗病了，绝对不会当天不杀死它。 下面讲解一下如何得出结果。第一天，大家都没有开枪杀狗，说明一个问题，就是绝对不只一条狗有病。试假设只有一条狗有病，那么就会有一个人看不见病狗，他根据题设中说一定有病狗就可以推断自己的狗是病的，于是第一天就该响起枪声。第一天的结果已经证明了不只一条狗有病，而且不难看出假设只有一条狗有病就一定可以在第一天响起枪声，击毙那一条生病的狗。此时我们不妨大胆猜测一下：第几天开枪就有几条狗是病的。 到了第二天，我们就可以开始验证我们的结论了。试想，如果只有两条病狗，狗的主人必然看不见其他狗生病，于是发现自己的狗是生病的，那么第一天看到一条病狗的人就会在第二天根据如果有一条病狗，那么第一天就会响起枪声，而第一天没有人开枪，则有不少于一条狗有病。再看看发现自己只看见一条狗生病了，那么想来，自己的狗就是一条病狗。于是就会根据上面的方法推断得到自己的狗病了。于是开枪，响起的枪声应该是两声。 但是到了第二天仍然没有枪声，于是到了第三天。第三天的时候响起枪声了。前面已经说了，绝对不是有三条以下的狗有病，否则枪声早就响了。但是，如果是四条狗有病，他们可以判断自己的狗是病的吗？根据前面所讲，每个病狗的主人都看见三条病狗，而每个人都想自己可以看见三条狗有病，由前面的推导谁也不能肯定自己的狗是病的，就不能判断自己是否该开枪打死自己的狗，于是应该不会响起枪声。于是我们判断出了应该是三条狗有病。 有人问了，如果第四十九天响起枪声，你是不是也就这样推导 四十九步？当然不必要啊。其实根据数学归纳法的思想，我们只要开动脑筋，根据前面的三步推导的结果的特殊性很容易可以得到一个更加一般的推论——只要是符合上述题目条件一到四假设的，无论总共是多少条狗或者无论是哪一天响起了枪声，我们都可以得到是多少条狗倒下。前面已经大胆猜测第几天开枪对应的打死的狗的数目就是几。现在这个答案似乎得到了更加充分的肯 定。但是有的朋友仍然要求我们的答案的绝对正确性，那么我们可以根据归纳总结的方法证明如下： 证明： 1．第一天的枪响了， 说明有一个人看不见病狗， 但是最少有一条狗有病， 于是得到病狗是自己的， 于是开枪杀死自己的狗。 根据这个结论，我们从数字上得到了规律，于是我们猜测规律，用来寻找方便的解决问题的办法。不妨设第N天开枪，必然就是有N条狗倒下。 2．假设，第N天枪响了， 有N条狗是有病的， 而如果第N天没有枪声， 根据小于或等于N的数字n变成n=N，直到n=l的论证，于是得到了答案是第N天没有开枪不可能是少于或等于N条狗生病了， 就说明有多于N条狗有病。 · 3．证明的重点在于第N+1天的情况： 假设第N+1