【專欄】跟波利亞學解題（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~這堆里面所有剩下的個橘子，誰拿到最后一個橘子誰贏；問題同上。算法上面很多聰明的算法也都是通過考察所求結論隱藏的性質來減小復雜度的，譬如剛才提到的單純形問題，譬如經典面試題“名人問題”、“和最?。ù螅┑倪B續子序列”等等。倒推法之所以是一種極為深刻的思維方法，本質上是因為它充分利用了題目中一個最不易被覺察到的信息——結論。結論往往蘊含著豐富的條件，譬如對什么樣的解才是滿足題意的解的約束。一般來說，借助結論中蘊含的知識，我們便可以更為“智能地”搜索解空間。舉一個直白的例子，有人要你在地球上尋找一棟滿足如下條件的建筑：__層高（填空自己填），__風格，__年代始建，… （省略若干約束條件）。對于這樣一個問題，最平凡的解法是窮舉地球上每一棟建筑，直到遇到一個滿足條件的為止。而更“智能”的（或者說更“啟發”的）方法則是充分利用題目里面的約束信息，譬如假若條件里面說要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/