無法避免的模式
一個數列可以升跌交替,整列並不單調。子序列不必選取連續項,只須保持所選項的原有次序。數列要多長,才一定含有較長的遞增或遞減子序列?
以下 均為正整數,所有項是互不相同的實數。互異條件重要:任意長的常數數列都沒有長度二的嚴格遞增或遞減子序列。
定義 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 加一這種形式的界。定理只談子序列。
下面兩個錯誤涉及如何解讀結論與所記錄的長度。
常見錯誤
(把「或」讀成「和」)
定理只保證兩種子序列之一,而非兩者兼有。數列 有長度五的遞增子序列,卻沒有長度二的遞減子序列。若嘗試從鴿巢那一步同時得出兩種子序列,證明的就是錯誤的命題。
常見錯誤
(以前綴中的最長代替以該項結尾的最長)
若把 、 換成前 項中任何位置的最長單調子序列長度,長度對就不一定互異。對 ,這些前綴長度為 :第三與第四個位置相撞,儘管 。把 接上去,需要一個在第 項結尾的子序列。
練習
快速檢查
(為何十個互異實數必含長度四的遞增或遞減子序列?)
選取 與 。
解答 · 答案
取 ,則 ,所以定理給出長度至少 的遞增子序列或長度至少 的遞減子序列。
快速檢查
(給出九個互異數,既沒有長度四的遞增子序列,也沒有長度四的遞減子序列。)
使用分組構造。
解答 · 答案
可取 。每個遞減組長度三,後組全較大,而遞增子序列每組最多取一項,所以兩種單調長度都至多為三。
快速檢查
(對 ,求四個位置的 。)
求 時向前找較小的項,求 時向前找較大的項。
解答 · 答案
依次為 。例如 見證 , 見證 ,而 或 見證 。
快速檢查
(為何對嚴格子序列,證明不能不加修改套用到 ?)
檢查比較兩個位置的那一步。
解答 · 答案
相等兩項既不滿足 ,也不滿足 ,所以沒有任何一種長度被迫增長:每個位置的長度對都是 。事實上常數數列沒有長度二的嚴格單調子序列,所以互異假設不能去掉。