【专栏】跟波利亚学解题（3）

一些方法

这些一般性的思维方法，就是波利亚用了整整三本书，五卷本（《How To Solve It》、《数学的发现》¹、《数学与猜想》）来试图阐明的。波利亚的书是独特的，从小到大，我们看过的数学书几乎无一不是欧几里德式的：从定义到定理，再到推论。是属于“顺流而下”式的。这样的书完全而彻底的扭曲了数学发现的真实过程。举个例子，《证明与反驳：数学发现的逻辑》在附录一中讲了一个非常有趣的例子：柯西当年试图将函数的连续性从单个函数推广到无穷级数上面去，即证明由无穷多个连续函数构成的收敛级数本身也是一个连续的函数，柯西给出了一个巧妙的证明，似乎漂亮地解决了这个问题。然而傅立叶却给出了一个噩梦般的三角函数的收敛级数，它的和却并不是连续的。这令柯西大为头疼，以至于延迟了他的数学分析教程的出版好些年。后来，赛德尔解决了这个问题：原来柯西在他看似无懈可击的证明中非常隐蔽（他自己也不知觉的情况下）引入了一个潜在的假设，这个假设就是后来被称为的“一致收敛”条件。当时我看到这里就去翻我们的数学分析书，发现“一致收敛”这个概念第一次出现的时候是这样写的：定义——一致收敛……

所以说，从这个意义上，《数学，确定性的丧失》²从历史的角度再现了真实的数学发展过程，是一本极其难得的好书。而事实上，从真实的数学 历史发展的角度去讲授数学，也是数学教学法的最佳方法。不过，《数学，确定性的丧失》的弱点是并没有从思维的角度去再现数学发现的思维过程，而这正是波利亚所做的。

总结波利亚在书中提到的思维方法，尤其是《How To Solve It》中的启发式思考方法，有这样一些：

作者：刘未鹏 出版：电子工业出版社

1. 时刻不忘未知量。（即时刻别忘记你到底想要求什么，问题是什么）莱布尼兹曾经将人的解题思考过程比喻成晃筛子，把脑袋里面的东西都给抖落出来，然后正在搜索的注意力会抓住一切细微的、与问题有关的东西。事实上，要做到能够令注意力抓住这些有关的东西，就必须时刻将问题放在注意力层面，否则即使关键的东西抖落出来了也可能没注意到。

2. 用特例启发思考。一个泛化的问题往往给人一种无法把握、无从下手、或无法抓住里面任何东西的感觉，因为条件太泛，所以看起来哪个条件都没法入手。一个泛化的问题往往有一种 “不确定性”（譬如元素的个数不确定，某个变量不确定等等），这种不确定性会成为思维的障碍，通过考虑一个合适的特例，我们不仅使得问题的条件确定下来从而便于通过试错这样的手法去助探问题的内部结构，同时很有可能我们的特例中实质上隐藏了一般性问题的本质结构，于是我们便能够通过对特例的考察寻找一般问题的解。

3. 反过来推导。反过来推导是一种极其重要的启发法，正如前面提到的，Pappus在他的宏篇巨著中将这种手法总结为解题的最重要手法。实际上，反向解题隐含了解题中至为深刻的思想：归约。归约是一种极为重要的手法，一个著名的关于归约的笑话这样说：有一位数学家失业了，去当消防员。经过了一些培训之后，正式上任之前，训练的人考他：如果房子失火了怎么办？数学家答出了所有的正确步骤。训练人又问他：如果房子没失火呢？数学家答：那我就把房子点燃，这样我就把它归约为了一个已知问题。人类思维本质上善于“顺着”推导，从一组条件出发，运用必然的逻辑关系，得出推论。然而，如果要求的未知量与已知量看上去相隔甚远，这个时候顺着推实际上就是运用另一个启发式方法——试错——了。虽然试错是最常用，又是也是最有效的启发法，然而试错却并不是最高效的。对于许多题目而言，其要求的结论本身就隐藏了推论，不管这个推论是充分的还是必要的，都很可能对解题有帮助。如果从结论能够推导出一个充要推论，那么实际上我们就将问题进行了一次“双向”归约，如果原问题不容易解决，那么归约后的问题也许就容易解决了，通过一层层的归约，让逻辑的枝蔓从结论上一节节的生长，我们往往会发现，离已知量越来越近。此外，即便是从结论推导出的必要非充分推论（“单向”归约），对问题也是有帮助的——任何不满足这个推论的方案都不是问题的解：譬如通过驻点来求函数的最值，我们通过考察函数的最值（除了函数边界点外），发现它必然有一个性质，即在这个点上函数的一阶导数为0，虽然一阶导数为0的点未必是最值点，但我们可以肯定的是，任何一阶导数不为0的点都可以排除，这就将解空间缩小到了有穷多个点，剩下的只要做做简单的排除法，答案就出现了。再譬如线性规划中经典的单纯形算法（又见《Algorithms》³），也是通过对结论的考察揭示出只需遍历有限个顶点便必然可以到达最值的。此外很多我们熟知的经典题目也都是这种思路的典范，譬如《How To Solve It》上面举的例子：通过一个9升水的桶和一个4升水的桶在河里取6升水。这个题目通过正向试错，很快也能发现答案，然而通过反向归约，则能够不偏不倚的命中答案。另一些我们耳熟能详的题目也是如此，譬如：100根火柴，两个人轮流取，每个人每次只能取1~7根，谁拿到最后一根火柴谁赢；问有必胜策略吗，有的话是先手还是后手必胜？这个问题通过试错就不是那么容易发现答案了。同样，这个问题的推广被收录在《编程之美》⁴里面：两堆橘子，各为m和n个，两人轮流拿，拿的时候你只能选择某一堆在里面拿（即不能跨堆拿），你可以拿1~这堆里面所有剩下的个橘子，谁拿到最后一个橘子谁赢；问题同上。算法上面很多聪明的算法也都是通过考察所求结论隐藏的性质来减小复杂度的，譬如刚才提到的单纯形问题，譬如经典面试题“名人问题”、“和最小（大）的连续子序列”等等。倒推法之所以是一种极为深刻的思维方法，本质上是因为它充分利用了题目中一个最不易被觉察到的信息——结论。结论往往蕴含着丰富的条件，譬如对什么样的解才是满足题意的解的约束。一般来说，借助结论中蕴含的知识，我们便可以更为“智能地”搜索解空间。举一个直白的例子，有人要你在地球上寻找一栋满足如下条件的建筑：__层高（填空自己填），__风格，__年代始建，… （省略若干约束条件）。对于这样一个问题，最平凡的解法是穷举地球上每一栋建筑，直到遇到一个满足条件的为止。而更“智能”的（或者说更“启发”的）方法则是充分利用题目里面的约束信息，譬如假若条件里面说要60层楼房，你就不会去非洲找，如果要拜占庭风格的，你估计也不会到中国来找，如果要始建于很早的年代的，你也不会去非常新建的城市里面去找，等等。倒推法是如此的重要，以至于笛卡尔当时认为可以把一切问题归结为求解代数方程组，笛卡尔的万能解题法就是首先将问题转化为代数问题，然后设出未知数，列出方程，最后解这组（个）方程。其中设未知数本质上就是一种倒推：通过设出一个假想的结论x，来将题目对x的需求表达出来，然后顺势而下推导出x。仔细想想设未知数这种手法所蕴含的深刻思想，也就难怪笛卡尔会认为它是那个解决所有问题的一般性钥匙了。

（待续；此文的修订版已收录《暗时间》一书，由电子工业出版社2011年8月出版。作者于2009年7月获得南京大学计算机系硕士学位，现在微软亚洲研究院创新工程中心从事软件研发工程师工作。）

参考资料

1 《数学的发现》 http://book.douban.com/subject/1850407/

2 《数学，确定性的丧失》 http://book.douban.com/subject/1049136/

3 《Algorithms》 http://book.douban.com/subject/1996256/

4 《编程之美》 http://book.douban.com/subject/3004255/