无法避免的模式
一个数列可以升跌交替,整列并不单调。子序列不必选取连续项,只须保持所选项的原有次序。数列要多长,才一定含有较长的递增或递减子序列?
以下 均为正整数,所有项是互不相同的实数。互异条件重要:任意长的常数数列都没有长度二的严格递增或递减子序列。
定义 2.2.1
(子序列与严格单调)
设 是有限数列。长度为 的子序列是 ,其中下标满足 ;下标递增,但不必连续。若 ,子序列称为递增;若 ,称为递减。本节的递增和递减均指严格不等。单独一项既是长度一的递增子序列,也是长度一的递减子序列。
论证所用的是鸽巢原理最简单的形式:把多于 个物体放进 个盒子,必有某个盒子至少放了两个。
在每个位置记录两种长度
定理 2.2.2
(单调子序列的精确界)
任意 个互异实数组成的数列,必含长度至少 的严格递增子序列,或长度至少 的严格递减子序列。
证明
(互异的长度对与鸽巢原理)
对每个位置 ,令 为以第 项结尾的最长递增子序列长度, 为以该项结尾的最长递减子序列长度。两者均存在且至少为一。若 ,互异性给出 或 。前者可把 接到以 结尾的最长递增子序列之后,得到 ;后者同理得到 。因此无论哪种情况, 与 都不同。
假设两种所需子序列都不存在,则每个 属于 ,每个 属于 。但只有 种可能的有序对,却有 个位置;鸽巢原理迫使两个有序对相同,矛盾。
证明透视
为什么只记一种长度不够
证明把位置当作鸽子、把长度对当作鸽巢,唯一真正的一步是从位置 到长度对的映射是单射。互异性恰好用在这里:它保证任意两个位置的项必然严格地一大一小。较早一项较小时,递增长度被迫增长;较早一项较大时却不一定,递减长度恰好处理后一情形。只记录其中一种长度,许多位置就会落在同一个鸽巢。“以第 项结尾”也不可少:把较后一项接上去之所以合法,正因为被延长的子序列停在较早的位置。反证假设随后把鸽巢数目限制为 乘 ,所以出现 rs 加一这个数。
结论是至少一种存在;同一数列也可能同时包含两种,而证明并不指出出现的是哪一种。
概念视角结构
把位置分成递减的类
单是递增长度已经把位置分成若干递减子序列。若 且 ,则 ,因为 会给出 。所以每一类 按次序读出都是递减的。若没有长度 的递增子序列,就至多有 类覆盖 个位置,其中一类至少有 个成员。对 ,各类为 与 。
例子与不能改进的界
命题 2.2.3
(界 不能再降低)
对任意正整数 ,存在由 个互异整数组成的数列,既没有长度 的递增子序列,也没有长度 的递减子序列。
证明
(按递增次序排列的递减组)
构造 组、每组 项:每组内把连续整数倒序排列,并使每个较后组的所有数都大于较前各组。例如对 ,第 组可取 。所得 项互异。同组两项递减,所以递增子序列每组最多取一项,长度至多 。较后组的项大于较前组的每一项,所以递减子序列不能跨两组,长度至多 。
因此对任意互异数列,定理中的 不能再减少。
例题 2.2.4
( 时四项不够)
取 ,任何五个互异数必含长度三的递增或递减子序列。四项不够:分组构造给出 。首两项递减,末两项也递减,且首组每项都小于第二组每项。递增子序列每组最多取一项,所以长度至多为二;递减子序列不能从首组移到较大的第二组,所以长度也至多为二。
例题 2.2.5
(在五项上追踪长度对)
取 ,仍设 。计算 时向前找较小的项:,因为 延长 , 延长 或 , 延长 。计算 时向前找较大的项:,因为 延长 或 , 延长 , 延长递减对 。
长度对 两两不同,与证明所预言的一致。 只容得下四个长度对,所以第五个必须越出范围:这里 ,由 见证。
例题 2.2.6
(边界情形 )
当 时,定理谈的是 个互异项,结论是:或者某个较早的项小于某个较后的项,或者整个数列递减。这是显然的,因为没有递增对的数列每一步都下降。 时的分组构造只有一组 ,它没有递增对,递减长度恰为 。在证明中,若没有递增对,每个 都等于 ,长度对便化为各个 ;它们是 个互异正整数,其中必有一个至少为 。
常见错误
反例模式
连续段是另一个问题
断言: 个互异数之中,必有 加一个连续的递增项,或 加一个连续的递减项。取 与 都等于二,以及五项 2、1、4、3、5。相邻各步依次为降、升、降、升,所以每个由连续项组成的单调段长度都是二,断言不成立。定理仍然成立:1、3、5 是长度三的递增子序列,所用的项并不相邻。把锯齿延长为 2、1、4、3、6、5 等等,无论多长,连续段的长度都保持为二,所以对连续段不存在 rs 加一这种形式的界。定理只谈子序列。
下面两个错误涉及如何解读结论与所记录的长度。
常见错误
(把“或”读成“和”)
定理只保证两种子序列之一,而非两者兼有。数列 有长度五的递增子序列,却没有长度二的递减子序列。若尝试从鸽巢那一步同时得出两种子序列,证明的就是错误的命题。
常见错误
(以前缀中的最长代替以该项结尾的最长)
若把 、 换成前 项中任何位置的最长单调子序列长度,长度对就不一定互异。对 ,这些前缀长度为 :第三与第四个位置相撞,尽管 。把 接上去,需要一个在第 项结尾的子序列。
练习
快速检查
(为什么十个互异实数必含长度四的递增或递减子序列?)
选取 与 。
解答 · 答案
取 ,则 ,所以定理给出长度至少 的递增子序列或长度至少 的递减子序列。
快速检查
(给出九个互异数,既没有长度四的递增子序列,也没有长度四的递减子序列。)
使用分组构造。
解答 · 答案
可取 。每个递减组长度三,后组全较大,而递增子序列每组最多取一项,所以两种单调长度都至多为三。
快速检查
(对 ,求四个位置的 。)
求 时向前找较小的项,求 时向前找较大的项。
解答 · 答案
依次为 。例如 见证 , 见证 ,而 或 见证 。
快速检查
(为什么对严格子序列,证明不能不加修改地套用到 ?)
检查比较两个位置的那一步。
解答 · 答案
相等两项既不满足 ,也不满足 ,所以没有任何一种长度被迫增长:每个位置的长度对都是 。事实上常数数列没有长度二的严格单调子序列,所以互异假设不能去掉。