《面试中的数学归纳法》由会员分享，可在线阅读，更多相关《面试中的数学归纳法（15页珍藏版）》请在金锄头文库上搜索。
1、节选张顺燕主编的心灵之花面试中的数学归纳法论一道微软面试题的数学思考在微软的一次面试中，面试官出了一道非常让人意外、非常经典的题目，就是“一个 屋子里面有五十个人，每个人领着一条狗，而这些狗中有一部分病狗(不少于一条)。假定 有如下条件：一、狗的病不会传染，也不会不治而愈。也就是说病狗的数量一直不会改变； 二、狗的主人不能看见自己的狗是否有病，但是狗的主人只有通过别人的狗是否有病才可 以看出自己的狗生病了没有；三、一旦主人发现自己的狗肯定是一只病狗，就会在当天开 枪打死这 条狗；四、狗必须由他的主人亲自动手开枪杀死。如果他们在一起第一天没有 枪声、第二天没有枪声、第三天发出了一片枪声，问有几条
2、狗被打死。 ”所有的人面面相觑，都哑然。这是一道什么样的题目呢？几乎都在思考，都在想这是 一个什么样的脑筋急转弯?还是一个什么样的智力游戏?很多人面对这个问题就是束手就擒， 甚至就直接由此退出了面试。这时开始有人抱怨微软竟然拿这道非常无聊的题目来刁难大 家。也许是因为当时太紧张，也许是因为大家的思路没有被打开，不自觉地大家开始了讨 论，但是于事无益。几乎没有几个人答出了这道题。很多人都因为这道题目的怪异而思路 主要在于想为什么会有这道题?为什么微软的面试官会出这种题?为什么会在微软的面试中 出现这种几乎是与微软的世界不相关的把戏?大家惟独没有想清楚的是这道题与微软到底有 何干 系?为什么微软出
3、了这道让大家颇为郁闷的题。这其实是一道数学题，一道非常标 准的数学推断题。有数学的头脑，有明确的思路，解这道题其实是一件非常简单的事情。这道题本来是一个很简单的数学归纳法的应用。我们先来审题，将其题设变成我们的 语言和思维，这是解题必须的步骤。题设条件解读结果如下：一、肯定有狗生病，也就是 说病狗的数量大于零；二、病狗的数量不会发生变化；三、狗的主人只有通过看别人的狗 来确定自己的狗生病了没有；四、如果主人发现自己的狗病了，绝对不会当天不杀死它。下面讲解一下如何得出结果。第一天，大家都没有开枪杀狗，说明一个问题，就是绝 对不只一条狗有病。试假设只有一条狗有病，那么就会有一个人看不见病狗，他根据
4、题设 中说一定有病狗就可以推断自己的狗是病的，于是第一天就该响起枪声。第一天的结果已 经证明了不只一条狗有病，而且不难看出假设只有一条狗有病就一定可以在第一天响起枪 声，击毙那一条生病的狗。此时我们不妨大胆猜测一下：第几天开枪就有几条狗是病的。到了第二天，我们就可以开始验证我们的结论了。试想，如果只有两条病狗，狗的主 人必然看不见其他狗生病，于是发现自己的狗是生病的，那么第一天看到一条病狗的人就 会在第二天根据如果有一条病狗，那么第一天就会响起枪声，而第一天没有人开枪，则有 不少于一条狗有病。再看看发现自己只看见一条狗生病了，那么想来，自己的狗就是一条 病狗。于是就会根据上面的方法推断得到自己
5、的狗病了。于是开枪，响起的枪声应该是两 声。但是到了第二天仍然没有枪声，于是到了第三天。第三天的时候响起枪声了。前面已 经说了，绝对不是有三条以下的狗有病，否则枪声早就响了。但是，如果是四条狗有病， 他们可以判断自己的狗是病的吗？根据前面所讲，每个病狗的主人都看见三条病狗，而每 个人都想自己可以看见三条狗有病，由前面的推导谁也不能肯定自己的狗是病的，就不能 判断自己是否该开枪打死自己的狗，于是应该不会响起枪声。于是我们判断出了应该是三条狗有病。 有人问了，如果第四十九天响起枪声，你是不是也就这样推导 四十九步？当然不必要 啊。其实根据数学归纳法的思想，我们只要开动脑筋，根据前面的三步推导的结果
6、的特殊 性很容易可以得到一个更加一般的推论只要是符合上述题目条件一到四假设的，无论 总共是多少条狗或者无论是哪一天响起了枪声，我们都可以得到是多少条狗倒下。前面已 经大胆猜测第几天开枪对应的打死的狗的数目就是几。现在这个答案似乎得到了更加充分 的肯 定。但是有的朋友仍然要求我们的答案的绝对正确性，那么我们可以根据归纳总结 的方法证明如下： 证明：1第一天的枪响了，说明有一个人看不见病狗，但是最少有一条狗有病，于是得到病狗是自己的，于是开枪杀死自己的狗。根据这个结论，我们从数字上得到了规律，于是我们猜测规律，用来寻找方便的解决 问题的办法。不妨设第 N 天开枪，必然就是有 N 条狗倒下。2假设，
7、第 N 天枪响了，有 N 条狗是有病的，而如果第 N 天没有枪声，根据小于或等于 N 的数字 n 变成 n=N，直到 n=l 的论证，于是得到了答案是第 N 天 没有开枪不可能是少于或等于 N 条狗生病了，就说明有多于 N 条狗有病。 3证明的重点在于第 N+1 天的情况：假设第 N+1 天想起了枪声，根据第 N 天没有枪声，得到了多于 N 条狗有病；再假设有多于 N+1 条狗有病，根据多于 N 条狗有病的时候，第 N 天所有人的人均不能判断自己的狗一定生病，现在多于 N+1 条狗生病，那么大家就无法在 N+l 天确认自己的狗是否生病，无法决 定自己是否应该开枪。我们得到了结论在 N+1 天也
8、是无法响起枪声的。于是与题设以及我们的假设中 N+1 天响起了枪声发生冲突，冲突的原因在于我们假设了多于 N+1 条狗有病，就说明不可能多于 N+I 条狗生病了，于是得到证明有 N+1 条狗有病。综上，在第几天开枪就会有几条狗有病被杀得以证明。在数学的世界里，我们有很多不同的思想方法，比如说，我们常常遇到的统筹的思想 方法；我们也常常需要根据一些已知的东西推断一些未知的东西，这就用到我们所讲的总 结法；而为了证明判断的正确，我们又用到了归纳法来证明。数学的思想方法无处不在， 很多的事物与规律都与数学的思想方法直接或者间接地相关。在未来，科技更加发达，我 们的头脑中必定需要有更多的数学的思维出现
9、；为了在社会中生存，为了在竞争中取胜， 综合地培养自己的能力时也需要不断地培养数学的思维。我们的生活中，也常常会用到数学的思想方法，也常常会思考一些数学问题。我们在 思考这些方法的同时，也得到了进步。在我们的学习工作中，不仅要把数学学好，还要把数学的精髓学到手，这就是了解和掌握数学的思想方法。并且还要加强自己应用的能力， 因为熟练的应用，可以直接为我们的生活和学习工作带来意想不到的好处和方便。甚至在 一次重要的权威面试中，直接关系到自己一辈子的发展的，也就是这么一个简单的数学归 纳法。本文写于匆忙之中，试想在一周之内要上交七篇论文，且又多为资料众多需要考查的 类型，其质量可想而知。但是接到张顺
10、燕教授的任务后的那个苦恼不已的晚上却听到了一 个很不错的题材，就是微软的面试官给出的这道题目。忙乎差不多一个夜晚，整理了各种 信息，与同学们分析了好一阵，终于执笔将此文的雏形写出，但是又因为时间关系，没有 修改，甚至错别字到处都是，也没有按照数学模型的论文格式，甚至都没有涉及到使用数 学的语言，所以终究也不是一篇好论文。但是，张教授却选择本文要出书，我确实兴奋不已。也许确实此文写得简单易懂还颇 有新味吧。修改前我想到要用严格的数学方法和证明来将本文章论证等趋于完美，经过提 炼推导过程以标准的数学语言给予表达。但是又一想，反而不妥，此书系为所有爱好数学 的朋友所编，读书者不一定是我们数学界内的人
11、士，写得满是数学符号恐怕不如就这样叙 述性的讨论。我荣幸可以有朋友读到这篇文章，我也希望此文可以激起大家的思考，激发 大家的数学 灵感，培养数学思维，但是我的推断也有不明朗或不严密的地方甚至可能出现推导中的错 误和叙述上的纰漏，望各位友人批评指正。浅论数学、文学与音乐中复调形式美的一致性数学、文学、音乐常常以某种形式的默契向人们昭示世界的对称，宇宙的神秘与魅力。 让我们来看下面一串看似无法解释，而实际上却深刻暗示了我们要讨论的数学、文学与音 乐三者之间神秘关系的问题：我写完一篇小说，而恰恰其中的字词、句法或者标点的排列组合刚好适合于证明一道 数学题，我是在计算还是在创作?用所有表示声音的字词按
12、照某种规律排列，并且配备合适的节奏，然后将它演奏，它 是不是可以称之为音乐?还仅仅是一篇文章？如果我们引用适当的一个排列组合公式，而其中每个数字代表着一个不同的音符，然 后我们加入另几个数学公式的节奏进行排列，然后进行演奏，如果悦耳的话，这是不是音 乐?或者我们却恰恰是在做一个方程，我们是不是在编曲?我们将标点、文字、词汇、句子通过某种数学方法进行排列，而恰好讲述了一个故事 或者是一首诗。我们是不是在创作？文学的梁祝与音乐的梁祝中间的区别与共通性是什么? 如果我有足够优秀的电脑能将音乐的某个最细微的颤动翻译成文字或者将文字翻译成 音乐，我是在作文还是在谱曲？ 文字以同样的可能在音符上体现，是数
13、学还是音乐？或者就按着数学的规则对音符进 行排列，这更接近现在的谱曲吗？种种的问题，使得人们对宇宙的一致性产生了浓厚的兴趣。众多的研究在深入地开展， 不同学科之间的神秘共性是研究所关心的问题。我们还不敢断言，宇宙是否存在惟一的一 条普遍真理，能够用来解释人们关于世界的所有疑问，使得任何学科的划分都是多余的。 那么，我们只能从现实的现象出发，去探询这样的问题。在这些现实存在的现象之中，最 为明显并且极具代表性的要属数学、文学与音乐领域存在的一致性，特别是它们各自具有的复调形式美的一致性。复调形式本是音乐领域中的一个基本概念，指的是两个或几个旋律的同时结合。运用 复调形式，可以丰富音乐形象，加强音
14、乐发展的气势和声部的独立性，造成前呼后应、此 起彼落的效果。同样，在数学与文学领域，也存在这种要素的多重组和，与音乐的复调有 着异曲同工之妙。在这里，我们更为广义地定义复调形式，即两个或多个组成要素按照一 定的逻辑与结构构成有规律的、彼此照应的和谐的整体结构。这种形式因其具有的呼应性 与和谐性而成为一种美学形式。无论在音乐、文学、数学领域，我们都能感受到这种美的存在。数 学家研究数的时候，同文学家创作诗歌、散文、小说，作曲家创作曲子时一样，需要有自 己的语言，一套表情达意的体系。如同文学需要文学语言，音乐需要音乐语言一样，数学 也需要数学语言。而无论在音乐语言、文学语言抑或数学语言中我们都可以
15、找到这种具有 复调形式的美的存在。音乐中复调的例子不胜枚举。古典意义上的音乐，只是典型的单一主旋律，音乐的美 感来自和谐。但是，在现代的音乐美学中，和谐不再是美学的最高追求。现代哲学打破了 古典哲学的决定论的宏大结构，而认为，在工业时代和后工业时代，人的灵魂被撕裂开来， 存在着人与人、人与自我、人与社会、人与自然的普遍分裂。人在自我意识和潜意识里， 有着多重的构造。所以古典美学中的单一的旋律就无法表现现代人的心灵深度。于是 10 世 纪初 出现了无调性音乐。用迷乱的音响组合表现人的复杂的灵魂世界。著名的作曲家巴赫的协 奏曲比较接近于现代协奏曲，堪称复调音乐的大师。如a 小调小提琴协奏曲 ，共分
16、三个 乐章：第一乐章，a 小调，24 拍子，虽然没有速度指示，但一般都以快板演奏；第二乐 章，行板，C 大调，44 拍子，是本曲中最著名的乐章，体现出巴赫艺术特征中严肃的一 面；第三乐章，甚快板，a 小调，98 拍子。我们从中可以感受到巴赫复调音乐的精致巧 妙的手法。同样，文学艺术中也存在这种复调的美，而且形式多样。例如，现代小说创作中流行 一时的复调小说。一个作家，作为一个叙述者，也就是一个讲故事的人，就不再是一个全 知全能的上帝，可以把一个故事讲述得非常完整，因为他自己的灵魂深处也可能是割裂的， 在他的人物设计和情节讲述中，无意识地把自己的内心的矛盾在故事中流露出来，因此也 就把自己表露得更加深刻。复调小说，其实，就是作者自己多个人格的对话。 泡沫之恋 可以被看作复调小说的代表。小说中爱不爱，自爱爱别人，漂泊安定，现实理想 的旋律回环交错构成了一种复调。而主人公的性格：超越年龄的沧桑感和冷静与实际的岁 数应该具有的天真、纯洁、浪漫、幻想，又构成了一个多重的调性。数学语言中的复调是我想重点讨论的内容。数学之所以可以成为一门足以
