工具都讲完了,现在面对一道陌生题——你怎么知道该掏哪一件?

这一章不教新工具,教调度:卡住时,脑子里该按什么顺序自问。匈牙利数学家波利亚(George Pólya)把解题拆成四步,朴素得近乎常识,但常识恰恰是新手最容易跳过的。


一、波利亚四步(用人话说)

  1. 看懂题在问什么。 已知是什么?要求的是什么?把条件一条条抄下来,把结论用自己的话复述一遍。一大半"做不出",其实是"没读懂"。
  2. 找一条路。 这一步最难,也是七件工具上场的地方——下一节给你一张"翻路口的牌子"。
  3. 照路走,每步都站得住。 把想法落成一步步严谨的推导(怎么写,第 16 章细讲)。
  4. 回头看。 答案对吗?拿小情形验(第 2 章)。有没有更短的路?这套法子还能解别的题吗?回顾这一步,新手几乎全跳过,而它正是把"做对一道"变成"会做一类"的关键。

二、卡在第二步时,按这张牌子翻

第二步"找路"最让人干瞪眼。给你一份自问清单,从上往下问,对上哪条就往哪条走——这等于把前面十四章压成一页路标:

先看题目要你做什么:

  • 要证"一定存在 / 必有两个 / 至少有一个"?→ 抽屉原理(第 4 章):谁当鸽子、谁当笼子。
  • 要证"办不到 / 不可能 / 变不过去"?→ 不变量(第 6 章)找一个怎么折腾都不变的量;或同余(第 8 章)找一个让目标余数现原形的模。
  • 要证"办得到 / 存在某种构形"?→ 构造法(第 9 章):亲手造一个,逐条验。
  • 要证"不存在 / 无穷多 / 唯一 / 无理"?→ 反证法(第 7 章):假设反面,推到撞墙。

再看题目长什么样:

  • 一堆地位平等、无从下手的对象?→ 极端原理(第 5 章):先拎出最大或最小的那个。
  • 交换不变的对称?→ 不妨设排队 / 配对求和(第 10 章),省掉一半。
  • \(n\) 太大、太抽象?→ 笨办法(第 2 章):拧小到 1、2、3,摆一排找规律。
  • 正面走岔路太多?→ 逆推(第 7 章):从目标倒着走,用目标那头的硬限制砍枝。

还卡着? 那就回到最笨的两条:算几个小情形(第 2 章),和把图标满 / 把条件列全(第 14 章)。规律和路口,常常就在你老实动手之后才现身。


三、现场演示:看我把一道题想出来

光给清单是纸上谈兵。下面我把上面的流程真用一遍,连带我中途的犹豫,都摊给你看。

例 15.1(☼☼☼,经典:六人聚会) 证明:任意 6 个人里,要么有 3 个人两两都认识,要么有 3 个人两两都不认识。 (“认识"是相互的:\(A\) 认识 \(B\),则 \(B\) 也认识 \(A\)。)

第一步,看懂。 已知:6 个人,每两人之间,非"认识"即"不认识”,二选一。要证:必能挑出 3 个人,他们之间要么全是"认识",要么全是"不认识"。

第二步,找路。 翻牌子:题目要证"必有 3 个……",是个"一定存在"型——抽屉原理(第 4 章)该上。可鸽子笼子怎么设?6 个人两两配对关系太多,乱。这时第二条提示响了:对象太多无从下手,先拎一个特殊的出来(第 5 章的破对称起手)。

那就随便盯住一个人,叫他甲。甲跟其余 5 个人之间,每段关系非"认识"即"不认识"——5 段关系(鸽子)装进"认识 / 不认识"两个类(笼子)。\(5\) 只鸽子 \(2\) 个笼子,由抽屉原理,必有一类至少占 \(3\) 段(因为 \(5=2+2+1\) 顶多让每类 2 个,第 5 个逼出 3)。

两类是对称的(第 3 章"不妨设"),不妨设甲"认识"的人里至少有 3 个,挑出其中三个,叫乙、丙、丁。

现在只剩乙丙丁三人之间的关系要看,分两种情况:

  • 若乙丙丁中有任意两个互相认识(比如乙和丙),那么甲、乙、丙三人两两认识——找到"3 个互相认识",成。
  • 若乙丙丁中没有任何两个互相认识,那乙、丙、丁三人就是两两都不认识——找到"3 个互不认识",也成。

两种情况都落进了结论。

第三步,照路走。 上面这段已经是完整推理了,誊清即可(第 16 章教誊法)。

第四步,回头看。 答案站得住吗?站得住。能不能更短?这条已经很干净。还能解什么?把“认识/不认识”换成“红边/蓝边”,这就证明了图论中拉姆齐数 \(R(3,3)\) 不大于 6。要证明它恰好等于 6,还须另举一个五人反例。就这样。

请你回看我刚才的动作:抽屉(找存在)卡住 → 极端/破对称(先拎一个人出来)解套 → 不妨设(对称省一半)→ 分类讨论收尾。 一道吓人的题,是四件工具接力打下来的,没有一处靠"灵感"。这就是清单的用法——不是背它,是卡住时一条条往下问,让工具自己跳出来举手。


这一章要带走的东西:

  • 波利亚四步:看懂题 → 找路 → 照走每步站得住 → 回头看。新手最爱跳的是第一步和第四步,恰恰最值钱。
  • 卡在"找路"时,按清单自问:先看题目要你证什么(存在/办不到/办得到/不存在),再看题目长什么样(地位平等/有对称/\(n\)太大/岔路多)。
  • 实战里一道题常是几件工具接力,不是单打——抽屉卡住就破对称起手,再用不妨设省力。
  • 还卡着,就回到最笨两招:算小情形、把条件列全。

就这样。


本书目录 · 上一章 · 下一章