跟波利亚学解题(rev#3)

跟波利亚学解题(rev#3)
Pappus，亚历山大学派最后一位伟大的几何学家，就曾在他恢弘的八卷本《数学汇编》中描述了其中的一种法则，他将它称为"分析与综合"，大意如下：
首先我们把需要求解的问题本身当成条件，从它推导出结论，再从这个结论推导出更多的结论，直到某一个点上我们发现已经出现了真正已知的条件。这个过程称为分析。有了这条路径，我们便可以从已知条件出发，一路推导到问题的解。
波利亚在他的三卷本中把这种做法叫做Working Backwards（倒过来解）。

欧拉是最重数学思维的教学的，欧拉认为如果不能把解决数学问题背后的思维过程教给学生的话，数学教学就是没有意义的。

这些一般性的思维方法，就是波利亚用了整整三本书，五卷本（《How To Solve It》、《数学的发现》、《数学与猜想》）来试图阐明的。波利亚的书是独特的，从小到大，我们看过的数学书几乎无一不是欧几里德式的：从定义到定理，再到推论。是属于“顺流而下”式的。这样的书完全而彻底的扭曲了数学发现的真实过程。

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

• 时刻不忘未知量（即时刻别忘记你到底想要求什么，问题是什么。）莱布尼兹曾经将人的解题思考过程比喻成晃筛子，把脑袋里面的东西都给抖落出来，然后正在搜索的注意力会抓住一切细微的、与问题有关的东西。事实上，要做到能够令注意力抓住这些有关的东西，就必须时刻将问题放在注意力层面，否则即使关键的东西抖落出来了也可能没注意到。
• 用特例启发思考。一个泛化的问题往往给人一种无法把握、无从下手、或无法抓住里面任何东西的感觉，因为条件太泛，所以看起来哪个条件都没法入手。一个泛化的问题往往有一种 “不确定性”（譬如元素的个数不确定，某个变量不确定等等），这种不确定性会成为思维的障碍，通过考虑一个合适的特例，我们不仅使得问题的条件确定下来从而便于通过试错这样的手法去助探问题的内部结构，同时很有可能我们的特例中实质上隐藏了一般性问题的本质结构，于是我们便能够通过对特例的考察寻找一般问题的解。
• 反过来推导。反过来推导是一种极其重要的启发法. 人类思维本质上善于“顺着”推导，从一组条件出发，运用必然的逻辑关系，得出推论。然而，如果要求的未知量与已知量看上去相隔甚远，这个时候顺着推实际上就是运用另一个启发式方法——试错——了。虽然试错是最常用，又是也是最有效的启发法，然而试错却并不是最高效的。对于许多题目而言，其要求的结论本身就隐藏了推论，不管这个推论是充分的还是必要的，都很可能对解题有帮助。如果从结论能够推导出一个充要推论，那么实际上我们就将问题进行了一次“双向”归约，如果原问题不容易解决，那么归约后的问题也许就容易解决了，通过一层层的归约，让逻辑的枝蔓从结论上一节节的生长，我们往往会发现，离已知量越来越近。此外，即便是从结论推导出的必要非充分推论（“单向”归约），对问题也是有帮助的——任何不满足这个推论的方案都不是问题的解：譬如通过驻点来求函数的最值，我们通过考察函数的最值（除了函数边界点外），发现它必然有一个性质，即在这个点上函数的一阶导数为0，虽然一阶导数为0的点未必是最值点，但我们可以肯定的是，任何一阶导数不为0的点都可以排除，这就将解空间缩小到了有穷多个点，剩下的只要做做简单的排除法，答案就出现了。再譬如线性规划中经典的单纯形算法（又见《Algorithms》），也是通过对结论的考 察揭示出只需遍历有限个顶点便必然可以到达最值的。此外很多我们熟知的经典题目也都是这种思路的典范，譬如《How To Solve It》上面举的例子：通过一个9升水的桶和一个4升水的桶在河里取6升水。这个题目通过正向试错，很快也能发现答案，然而通过反向归约，则能够不偏不倚的命中答案。另一些我们耳熟能详的题目也是如此，譬如：100根火柴，两个人轮流取，每个人每次只能取1~7根，谁拿到最后一根火柴谁赢；问有必胜策略吗，有的话是先手还是后手必胜？这个问题通过试错就不是那么容易发现答案了。同样，这个问题的推广被收录在《编程之美》里面：两堆橘子，各为m和n个，两人轮流拿，拿的时候你只能选择某一堆在里面拿（即不能跨堆拿），你可以拿1~这堆里面所有剩下的个橘子，谁拿到最后一个橘子谁赢；问题同上。算法上面很多聪明的算法也都是通过考察所求结论隐藏的性质来减小复杂度的，譬如刚才提到的单纯形问题，譬如经典面试题“名人问题”、“和最小（大）的连续子序列”等等。倒推法之所以是一种极为深刻的思维方法，本质上是因为它充分利用了题目中一个最不易被觉察到的信息——结论。结论往往蕴含着丰富的条件，譬如对什么样的解才是满足题意的解的约束。一般来说，借助结论中蕴含的知识，我们便可以更为“智能地”搜索解空间

• 调整题目的条件（如，删除、增加、改变条件）。有时候，通过调整题目的条件，我们往往迅速能够发现条件和结论之间是如何联系的。通过扭曲问题的内部结构，我们能发现原本结构里面重要的东西。譬如这样一个题目（感谢alai同学提供）：A国由1000000个岛组成，岛与岛之间只能用船作为交通工具，有些岛之间有船来往，从任意一个岛都可以去到另外任一个岛，当然其中可能要换船。现在有一个警察要追捕一个逃犯，开始时他们在不同的岛上，警察和逃犯都是每天最多乘一次船，但这个逃犯还有点迷信，每个月的13日不乘船，警察则不迷信。警察每天乘船前都知道逃犯昨天在哪个岛上，但不知道他今天会去哪个岛。请证明，警察一定可以抓到逃犯（即到达同一个岛）。通过拿掉题目中一个关键的条件，观察区别，然后再放上那个条件，我们就能“感觉”到题目的内在结构上的某种约束，进而得到答案。
• 求解一个类似的题目。类似的题目也许有类似的结构，类似的性质，类似的解方案。通过考察或回忆一个类似的题目是如何解决的，也许就能够借用一些重要的点子。然而如何在大脑中提取出真正类似的题目是一个问题。所谓真正类似的题目，是指那些抽象结构一样的题目。很多问题表面看是类似的，然而抽象结构却不是类似的；另一些题目表面看根本不像，然而抽象层面却是一致的。表面一致抽象不一致会导致错误的、无效的类比；而表面不一致（抽象一致）则会阻碍真正有用的类比。《Psychology of Problem Solving》里面对此有详细 的介绍。后面也会提到，为了便于脑中的知识结构真正能够“迁移”，在记忆掌握和分析问题的时候都应该尽量抽象的去看待，这样才能够建立知识的本质联系，才能够最大化联想空间。
• 列出所有可能跟问题有关的定理或性质。这个不用说，我们在最初学习解题的时候就是这么做的了。
• 考察反面，考察其他所有情况。很多时候，我们在解题时容易陷入一种特定的手法，比如为什么一定要是构造式的来解这个题目呢？为什么不能是逼近式的？为什么一定要一步到位算出答案？为什么不能从一个错误的答案调整到正确答案？为什么这个东西一定成立？不成立又如何？等等。经典例子：100个人比赛，要决出冠军至少需要赛多少场。
• 将问题泛化，并求解这个泛化后的问题。刚才不是说过，应该通过特例启发思考吗？为什么现在又反倒要泛化呢？实际上，有少数题目，泛化之后更容易解决。即，解决一类问题，比解决这类问题里面某个特定的问题还要容易。波利亚称之为“发明者悖论”，关于“发明者悖论”，《数学与猜想》第一卷的开头有一个绝妙的例子

充分挖掘题目中蕴含的知识，是解题的最关键步骤。本质上，所有启发式方法某种意义上都是为此服务的。这些知识，有些时候以联想的方式被挖掘出来，此时启发式方法充当的便是辅助联想的手段。有时候则以演绎和归纳的手法被挖掘出来，此时启发式方法则充当助探（辅助探索）工具。

3. 好题目、坏题目

在我看来，好题目即测试一个人思维的习惯的题目（因为知识性的东西是更容易弥补的，尤其是在这样一个年代；而好习惯不是一朝一夕养成的），它应有这样一些性质：

• 不需要用到未知的知识，或者
• 需要用到未知的知识，但一个敏锐的解题者可以通过对题目的分析自行发现这些所需的知识。
• 考察解题的一般性思路，而不是特定（ad hoc）的解题技巧，尤其是当这个技巧几乎不可能在短时间内通过演绎和试错发现的时候。譬如题目需要用到某种性质，而这个性质对于不知道它的人来说几乎是无法从对题目的考察中得出来的。
• 考察思维能力：联想能力、类比能力、抽象能力、演绎能力、归纳能力、观察能力、发散能力（思维不落巢臼的能力）。
• 考察一般性的思维方法：通过特例启发思考、通过试错寻找规律、通过泛化试探更一般性命题、通过倒过来推导将问题进行归约、通过调整（分解、删除、增加等等）题目的条件来感知它们之间的联系以及和结论的联系、通过系统化的分类讨论来覆盖每种可能性。
• 好题目举例：烙饼排序问题（考察特例启发法以及观察能力）、Nim问题（还有简单版本的取火柴问题）（烙饼排序问题和Nim问题可参见《编程之美》）、9公升4公升水桶倒6公升水的问题（考察倒过来思考问题的能力）、9点连线问题、6根火柴搭出4个面的问题、“木板”问题（考察思维定势，此外《心理学与生活》的第九章也有好几个经典的问题）、许多数论问题（观察能力、演绎能力、归纳能力）。此外，我们最近也在讨论好题目。

出题的误区：

• 最大的误区就是把知识性的题目误当成能力型的题目。如果题目中需要用到某个重要的定理或性质，而对于一个原本不知道这个定理或性质的人来说是无法通过题目本身到达这个性质的，那这就属于知识性的题目。
• 虽然几乎所有题目归根到底都是知识性的，但有些题目更为知识性，尤其是当解题中需要用到的定理或性质并不那么trivial的时候。
• 一个最好的题目就是问题明明白白，而且最终的解也没有用到什么神秘的定理，但要想获知到解，取决于你会不会思考一个问题（参见“好问题”）。譬如烙饼问题和Nim问题，还有许许多多问题简洁明确但很锻炼思考的算法问题。

Read full article from 跟波利亚学解题(rev#3)