挑战≈ 15 分钟未开始
极端原理
核心概念
极端原理:在一个有限集合里,总存在最大(或最小)的元素。抓住这个极端元素,常能推出有力的结论或导出矛盾。
典型用法:
- 取"最大的那个 / 最小的那个 / 最长的那条 / 最靠边的那点";
- 假设结论不成立,对极端元素分析,得到一个"还能更极端"的对象,从而矛盾;
- 常与反证法、无穷递降配合使用。
直观理解 · 动手试试
极端原理的精髓是:别盯着一般情形,去看最极端的那个。最大的、最小的、最边上的元素往往"无路可退",它的处境受到最强的限制,因此能逼出最强的信息。
比如要证"存在某种好的对象",可以取一个"最优的"候选;如果它还不够好,就利用它构造出一个"更优"的,这与"它已是最优"矛盾——于是它必定足够好。这种"取极端 → 推矛盾"的套路,是组合证明里最优雅的招式之一,常常一句话就锁死全局。
极端原理
抓住最大 / 最小的那个
4
7
2
9
5
1
6
最大元素是 9(第 4 个)。在证明中,它常常「无路可退」,能逼出最强的结论或矛盾。
第 1 组
有限个数里必有最大、最小者。极端原理就是盯住这个极端元素,利用它「受限最强」的特点推出结论。
平面上 个点,任意两点距离都不相同。每个点都把"离它最近的点"用箭头指向。证明:不存在三个点互相指来指去成环。(思路)
▸查看解答步骤
答: 取最近点对推矛盾
一个班里每个人的朋友数互不相同(共 人,)。说明为什么这不可能。(思路)
▸查看解答步骤
答: 利用最大度推性质
即时练习
任何有限个互不相等的实数中,一定存在最大的一个。
有限集必有最大元,这是极端原理的基础。
在 个人的聚会中,可能每个人的朋友数都两两不同。
取最大(n−1,和所有人是朋友)与最小(0,无朋友)会矛盾,故不可能。
极端原理常用来?
抓住最大/最小元素推结论或导矛盾把式子裂项相消给棋盘黑白染色用特征方程解递推极端原理的核心是考察集合中的极值元素。
极端原理常与下列哪种方法配合?
反证法错位相减韦达定理裂项相消常假设结论不成立,对极端元素分析导出矛盾,即反证法。
易错点
- 忘了"有限"前提。 无限集未必有最大/最小元(如开区间),极端原理需有限性或良序性保证。
- 取错极端对象。 要根据问题选"最大边""最近点""最小计数"等恰当的极端量。
- 只取极端不推矛盾。 取出极端元素只是第一步,关键在于由它推出有用结论或矛盾。
下一步
前置知识点
—接下来学习