你不知道的数学归纳法
游戏内容是这样的:
有一个老师,想辨别出他的3个得意门生哪一个更聪明,他采用了一下方法,事先准备好5顶帽子,其中3顶是白的,2顶是黑的.实验前,他让他的3个学生看了帽子,然后要他们闭上眼睛,替每一个学生带上一顶白色的帽子,并把剩下的两顶黑帽藏起来.最后让他们睁开眼睛,请他们说出自己头上帽子的颜色,(他们不能看自己的帽子,但可以看到其他两个人头上的帽子).
三个学生互相看了一下,踌躇了一会,然后他们异口同声地说,他们头顶上的帽子是白色的.
现在问题是,他们是怎么推算出来的?
有兴趣的读者可以自己先想一想,把书搁下来,回头再往下看答案.
一般答案会这样跟你说:
甲乙丙三个同学是怎么想的: 甲是这样想的:要是我头上的帽子是黑色的,那么乙一定会这样想: 要是我的也是黑色的,那么丙一定会立即说出他的帽子是白色的.可是他踌躇了.这样乙就会知道他其实是白帽子,可是乙他也踌躇了.想到这里,甲就会知道,他头上的帽子不是黑色的.
经过这样的思考,三个人都知道他们头上的帽子都是白色的.
以上是很绕口的思考,想通了没?很费劲是吧! 而且,我第一次看到答案会想, 第一次就能得出正确答案的人得多聪明呀. 直到有一天看到了华老先生的一本书 数学归纳法, 我才发现这么这是典型数学归纳问题,这跟智商无关, 重要的是你要能意识地知道可以运用这样的思考模式.这本书不厚,就一小册子, 这本书的书名虽然是数学归纳法,但里面更多是华老先生个人的思考方式,十分有趣.强烈推荐阅读. 我也决定摘录其中的内容作为自己的学习笔记.
什么是数学归纳法?
首先我们有理解什么是数学归纳法, 我们看看 wiki是怎么描述的:
- 首先证明P(1)成立,即公式在n = 1时成立.
- 然后证明从P(m) 成立可以推导出P(m+1) 也成立.(这里实际应用的是演绎推理法)
- 根据 1) 和 2) 我们可以知道 P(2)成立, 不断重复推导下一命题成立的步骤,(这就是所谓”归纳”推理的地方)
- 最后我们便可以下结论:对于任意自然数n,P(n) 成立.
这是数学化的描述, 读者可以类比多诺米骨牌: 我们想象一下第一个多骨诺米牌会倒.
然后我们知道,要是某个多骨诺米牌到了,它后面的也会被推倒. 这样就可以得出:所有的骨牌都会倒这一事实.
或许读者会觉得这太简单了,但换个角度想, 要是我们面对的不是多诺米骨牌, 而是浩瀚如海的知识呢? 穷尽我们一生的精力或许在知识的海洋里不过是一片浪花. 这时候出现的救命稻草就是数学归纳法, 一个降维神器.变无限为有限.其实这也是归纳法的本源: 先从少数的示例摸索出规律来,再从理论上来证明这一规律的一般性. 它用有限的步骤,推导出适用一般情况的准则. 愣是把无限这一抽象的东西变成了有限步骤能够被具体化的东西. 这才是它神奇的地方.
书中举了一个这样的例子:
以识数为例,小孩子识数,先学会数1,2,3,过些时候就可以数到10了,又过些时候到20,30…100.但后来,却不是这样一段一段地增长了,而是飞跃前进.到了某些时候,他领悟了,他会说”我什么数都能数出来”.这一飞跃,竟从有限到了无限!怎么会这样呢?首先,他知道要从头数,其次,他知道一个一个是有序的,而且不用担心数会数得完,也就是说他领悟了下一个数的表达方式—可以由上一个数来决定,于是他也就会数任何一个数了. 设想一下,要是这个飞跃现象不出现,那么人们一辈子就只能学数数了,而且人生有限,数目无限,就是学了一辈子,也决不会学尽.
.
但数学归纳法也不是万能的.
我们知道,要是给你正确的公式,用数归来证明是很容易的,但问题是,一开始的公式谁来提供? 我高中做数列题的时候,最怕参考答案这样写: “我们可以观察…进一步猜想数列的形式为… “ 我一般看到是哭笑不得, 因为这个过程中”观察..得知”是很难”重现的”. 运气好一点灵感闪现让你看出模式了,运气差一点, 憋了一天愣是没憋出来. 对某些人显而易见的东西对某些人来说就是盲点.
华老在书中是这样说的:
….但是呢,我后来仔细想想,却感到有些不满足,问题不是由于证明错了,而是对上面这个归纳式是怎么得来的,也就是对前人是怎么发现这个恒等式的,难道是从天上掉下来的?当然不是!是有”天才”的人直观地看出来的吗?也不尽然!这个问题启发了我,难处不在于有了公式去证明,而在于没有公式之前,怎么样去找出公式来.要知道要点在言外,而我们以前学到的,仅仅是其中一个方面而已.
说回文章开始的那道题
书中提供了这样的一个思路,或者说一个思维方式让我们知道,这道题原来还可以这样解决. 我只能用叹为观止来形容,不记下来不行呀!!!!
大家都知道,数学归纳法有助于我们”进”的一面,现在我想谈谈数学归纳法帮助我们”退”的一面.把一个比较复杂的问题,”退”成最简单最原始的问题,再把它想通透了,然后再用数归来一个飞跃上升,于是问题也就迎刃而解了.
什么意思?我们来看看学过数学归纳法的人会怎么文章开头的那个问题:
他会先退一步,(善于”退”,足够的”退”,”退”到最原始而不失去重要性的地方,是学好数学的一个诀窍!) 不考虑3个人,而考虑2个人一顶黑帽的问题,这样问题谁都会解,黑帽只有一顶,我戴了,对方会立即说他戴的是白帽,可是对方踌躇了,可见我的是白帽.这就是说”两个人,一顶黑帽,若干白帽”的问题十分简单.
现在可以考虑进了,”三个人,两顶黑帽,很多白帽”的问题其实很容易了,为什么呢?如果我头上的帽子是黑帽,那对于他们两个人来说,这就变成了” 两个人,一顶黑帽,若干白帽”的问题,从而直接解决问题,可是他们没有,所以说我的是白帽.(向华老致敬,最近看过最暴力的思考方式!).
这里可以看到,学会数归,就会用”归纳技巧”从原来的问题减去”一个人,一顶黑帽”,把它转化为一个简单的问题. 倘若我们再把原来的问题搞得再复杂一点”四个人,3顶黑帽,若干白帽”,要是用我们一开始的叙述方式,一定是:甲想…(乙想…(丙想….(丁想)))…..这样说起来多费事呀,简直是”拗口令”,使人听不清,不易搞懂.但是掌握了数归,善于”退”,那么只要几句话就了事了”要是我的是黑帽,那对于他们3个人来说就退化成 ‘3个人,2顶黑帽子’的问题”,这个问题他们可以立即解决而不用都踌躇,所以我的是白帽.在这里,”如果我头上的是黑帽”就是归纳法假定.
看到这里,问题就算变成”N 个人,N-1顶黑帽”这样复杂的问题我们也可以很简单地解决.
这只是一个有趣的数学游戏,但它充分说明了,一个人会不会数归,在思考问题上就会有很大的差异.不会数归的人想要解决这个问题需要耍些”聪明”,但是融会贯通地掌握了数归,耍”聪明”或许就不是必要的手段了.
最后: 两道搞笑的题
大鱼吃小鱼游戏
话说在某一个弱肉强食的海域里,有编号1,2,3….N共N条鱼,正所谓大鱼吃小鱼,现在我们假定:这些鱼有病,挑食病,对于编号N的鱼只喜欢吃编号N-1的鱼 ;还有,这些鱼也还有点神经质, 要是 N-1的鱼很有义气,不吃掉编号N-2的鱼,那编号N的鱼会被感动,然后就不会吃掉编号N-1的鱼了
现在我们假设每条鱼策略是:尽可能吃掉小鱼同时不被吃掉
好了,现在问题是: 编号1的鱼的命运会是怎么样的?
解答如下:
1 考虑一下,要是只有1 条鱼,那它肯定可以欢快地与小伙伴玩耍,不怕被吃;
2 要是N=2,那编号1 的鱼肯定被吃;
3 要是N=3 ,那为了顾及自己的生命,2不会吃1 .这样的思考是可以的.但是我们可以换一种方式来描述: 对于编号2来说,他会想,要是我吃掉1,那就剩下我编号2 和编号3, 这样跟情况2 是一样的,这样我必然被吃.所以我不能吃掉编号1的鱼.
4 当n = 4的时候就有趣了,这时第 2 条鱼可以大胆地吃掉第 1 条鱼,因为根据前面的结论,它知道第 3 条鱼是不会吃它的
各位看官,得出结论了吧,结论就是:当Ｎ是奇数的时候,第一条鱼可以存活下来;(这时候谁也动不了谁,我称这情况是均衡)不然,当Ｎ是偶数的时候,第二条鱼会吃掉第一条鱼从而使鱼的总数变成奇数(因为这达到了均衡状态,所以第二条鱼没有任何顾虑)
最后一道: 真的是搞笑. 这里谁能看出里面推理的漏洞?
话说有一天老师在讲台宣布,下周一到周五将有一天要考试,不过他是不会说是哪一天的,老师只说了,考试那天一定让同学们大吃一惊! !!!
下课后,我们聪明可爱的罗一刀流童鞋这样跟其他人说: 大家淡定,我们采用倒退来思考,考试一定不会在周五,不然周四那晚我们都会知道是周五考试,这样就不可能让我们大吃一惊.所以考试只能是在下周一到周四之间. 这样递推下去,周四也不可能,周三也不可能…..所以下周要考试是不可能的,老师在跟我们开玩笑.
一刀流同志说完,掌声响起,女生们投来花痴的目光….(一下省略意淫3000字).
后来呀,下周一第一节就考试了,同学们的确大吃一惊!
而罗一刀流他只在考完试后被打得半死,从此遁入空门,俗称:归纳僧
