動機
計數論證有時能保證某個對象存在,而不必求出所有安排的總數。十三名學生各選一個月份,必有兩人選中同一月份。我們不需要逐一列舉選擇,只需觀察:如果每個月至多被一人選中,那麼十二個月容納不了十三人。
真正有用的鴿巢原理論證,難點往往在於決定甚麼應當成為「鴿巢」。研究整除時,我們將用前綴和的餘數作為鴿巢;研究有序數列時,我們將用以某個位置結尾的兩種子序列長度作為鴿巢。這些記錄保留了能夠隨著新元素而延伸的資訊。記錄發生碰撞,就能導出想要的數學對象。
我們還要問保證是否尖銳。如果證明某個配置在達到一個門檻時必然出現,最好同時構造一個只比門檻少一項、卻沒有該配置的例子。這樣的構造說明定理究竟保證到甚麼程度。
定義
定義 2.6.1
(對象、鴿巢與佔用量)
設 是由 個帶標號對象組成的有限集, 是整數。把對象分配到 個鴿巢,就是給出函數 。第 個鴿巢的佔用量為 。這些纖維把 分成互不相交的部分,因此
允許空鴿巢。上取整 是不小於實數 的最小整數。
鴿巢不一定是實體容器,也可以是餘數類、區間、顏色,或一對整數標記的可能取值。使用上述求和等式時,每個對象必須恰好屬於一個鴿巢。互相重疊的區域不自動構成劃分;需要交代邊界歸屬,或給出確定的分配規則。
定義 2.6.2
(連續段與子序列)
對數列 ,非空連續段所佔的位置是 ,其中 。子序列所佔的位置為 ,不要求相鄰。若 ,稱其嚴格遞增;若不等號全部反向,稱其嚴格遞減。只有一項的子序列同時滿足兩種定義。
如果某個保證在一個整數門檻處成立,但在比它少一項時可以失敗,就稱這個門檻是尖銳的。這是對最壞情形的保證;某些更短的數列或更小的分配,可能早已包含所要求的配置。
定理/命題
定理 2.6.3
(尖銳的廣義鴿巢原理)
把 個對象放入 個鴿巢,至少一個鴿巢有不少於 個對象。對每一組 ,這個界都不能提高。
更一般地,設 是非負整數容量。如果 ,則存在鴿巢 滿足 。
第二個結論允許各個鴿巢有不同的限制。如果希望某個鴿巢 達到其指定的正整數目標 ,只需對象數超過 。等於該總數還不夠:讓第 個鴿巢恰有 個對象,便沒有一個達到自己的目標。
定理 2.6.4
(存在可整除的連續段之和)
設 是整數。對任意整數 ,存在一個非空連續段,其和能被 整除。
各項可以為零或負數。整除的意思是該和等於某個整數 與 的乘積 ,並不要求這個和為正或非零。
定理 2.6.5
(尖銳的單調子序列保證)
設 是整數。每個由 個兩兩不同的實數組成的數列,都有長度為 的嚴格遞增子序列,或長度為 的嚴格遞減子序列。對每一組 ,都能構造長度為 、卻沒有這兩類子序列的數列。
這裏的「或」允許兩個結論同時成立。定理沒有斷言這樣的子序列很多,也沒有斷言其各項相鄰,更沒有斷言整個原數列單調。
證明思路
把結論失敗轉化為容量限制
證明
(最大佔用量、均衡分配與不同容量)
設 是最大的佔用量。因為每個 都有 ,求和得 ,於是 。再利用 是整數,得到 。當 時所有鴿巢為空,論證仍成立。
為證明界不能提高,對 作帶餘除法:寫成 ,其中整數 ,。在 個鴿巢中各放 個對象,其餘鴿巢各放 個。如果 ,最大佔用量為 ;否則為 。兩種情形都恰等於 。當 時,,構造同樣適用。
對於不同容量,反設每個 都有 。求和便得 ,與假設的嚴格不等式矛盾。這也解釋了為甚麼對象數必須超過總容量,僅僅達到總容量並不夠。
記錄前綴,讓相減產生連續段
證明
(兩個餘數相同的前綴)
定義前綴和
連同空前綴在內,共有 個帶索引的前綴。把前綴索引 放入由 模 的唯一餘數所標記的鴿巢;餘數取自 。即使有負的前綴和,鴿巢仍恰有 個。鴿巢原理保證兩個不同索引有相同餘數。把它們按大小記為 ,則
由 知道這個段非空;由兩個前綴相減知道這個段連續。這是結論中的兩個獨立要求,兩者都依賴於所選的對象,而非僅靠「鴿巢原理」四個字。當 時,兩個前綴給出唯一的一項段,其整數和當然能被 整除。
標記每個位置能結束多長的子序列
對長度為 的數列,令 表示以位置 結尾的嚴格遞增子序列的最大長度, 表示相應的嚴格遞減最大長度。最大值確實存在:以 結尾的子序列只有有限多個,且至少可以選擇只含該項的子序列。因此 。
證明
(互異終點標記對落入 矩形)
取兩個位置 。如果 ,就在一個以 結尾的最長遞增子序列後添加 。索引仍嚴格增加,因此 。如果 ,對遞減子序列做同樣的延伸,就有 。
兩兩不同的條件保證這兩種情形必有一種發生。因此 :至少有一個座標嚴格增加,儘管另一個座標未必增加。
現在反設兩類所需的子序列都不存在,則每個終點標記對都屬於
這個集合只有 個元素。然而 個終點標記對互不相同,相當於將 個對象放入 個鴿巢而沒有發生碰撞,與鴿巢原理矛盾。所以至少一類所需的子序列存在。
證明透視
兩兩不同與項數 rs+1 在哪裏用到
這個證明分開處理三件事。第一件是每個位置都帶有的記錄:由於只含一項的子序列總是可用,兩個最大值都至少是 ,標記對 因而有定義。第二件是映射 的單射性,這是唯一用到兩兩不同的步驟。對 , 與 的比較必須嚴格偏向一方,而每個結果都令一個指定的座標增加。若容許 ,兩種延伸都不合法,記錄便可能重合:在 中每個標記對都是 。
第三件是把結論的否定轉化為取值範圍。若某個 至少為 ,以 結尾的最長遞增子序列的最後 項已經是被排除的對象;所以「沒有長度為 的遞增子序列」恰好表示對每個 都有 ,同理 。項數 只在這裏出現,用的是鴿巢原理最弱的形式: 個位置不能單射到只有 個元素的集合。論證以矛盾收結,並沒有指出哪一種結論成立;構造例子之後描述的遞推才給出明確的見證。
注意,證明並沒有斷言標記對按每個座標同時遞增。較後位置的遞增長度可能較小,而遞減長度較大。證明只需要標記對互不相同。
構造達到界限的例子
證明
(依次連接的遞減區塊)
為證明尖銳性,依次連接 個區塊,每塊長 。對 ,第 塊為
每塊內部遞減,但較後區塊的每個數都大於較前區塊的每個數。遞增子序列因而在每塊中至多取一項,長度至多為 。遞減子序列不能從較前區塊進入較後區塊,只能留在一個區塊內,長度至多為 。這兩個限制證明長度 時兩種結論都可能失敗,也涵蓋了 或 。
終點證明還給出尋找見證的有限過程。對每個位置 ,檢查所有更早的位置。令 等於滿足 且 的各個 的最大值再加一;沒有這樣的 時,用零作為該最大值。用條件 同樣計算 。對於每個非零最大值,保存一個達到它的更早索引。遞推是精確的:從任何較長子序列中刪除末項,會留下一個合格的更早終點;反過來,在達到最大值的較早子序列後添加末項,確實取得遞推給出的長度。當某個標記達到目標時,沿保存的索引向前追溯,再把結果反序即可。追溯中的索引嚴格減小,所以一定終止。直接方法至多比較 對數值;存在性定理本身不需要對任意實數表示法作計算效率保證。
例題詳解
例題 2.6.6
(含負數時的前綴碰撞)
取 ,數列為 。前綴和是 ,模 的餘數是 。
索引 與 的餘數相等,給出 。相應連續段為 。索引 與 的相同餘數也給出整個數列,其和為 。可以同時有多個合法答案,證明只需要一次碰撞。
如果只比較原數列各項的餘數,就得不到這個論證。兩項的餘數相同,說明它們的差可整除;這裏想要的卻是連續若干項之和。
例題 2.6.7
(正方形中的五個點)
在 中任意放置五個點,允許落在邊界上。把每個座標區間分為 和 。它們的四個笛卡爾積(Cartesian product)構成互不相交的鴿巢,所以每個點恰有一個歸屬。至少兩點位於同一鴿巢。
這兩點的兩個座標差的絕對值均不超過 ,歐氏距離(Euclidean distance)因此不超過
這保證有一對近點,但沒有識別最近的一對。四點不足以保證同一個距離界:取四個頂點,任意兩點的距離均至少為 。因此五點這個數量門檻尖銳;這裏並沒有聲稱在所有五點論證中,該距離常數也是最優的。
例題 2.6.8
(讀懂終點長度標記)
對數列 ,終點長度為
例如 ,因為 遞增,但更早的兩個長度為 的遞增子序列都不能接上 。此外 ,可由 或 達到。最後一個遞增長度為 ,見證為 或 。
此時 ,所以五個不同的數必有長度為 的單調子序列。長度為四的 說明門檻尖銳:遞增子序列在每個遞減數對中至多取一項,而遞減子序列只能留在某個數對內。第一個數列中的 是子序列,並不是連續段。
常見錯誤
反例模式
嚴格性與重複值
「嚴格遞增或嚴格遞減」的定理不能刪去兩兩不同的條件。數列 連長度為 的嚴格單調子序列都沒有,更不用說長度為 。
允許重複值時,有一個實用的替代結論:每個長度為 的實數數列,都有長度為 的非遞減子序列,或長度為 的嚴格遞減子序列。把第一個終點標記改為非遞減子序列的最大長度。對於 ,若 ,就能延伸第一個標記;否則 ,能延伸遞減標記。標記對互異的證明因而完全適用。等號情形必須歸到其中一邊,它不能延伸嚴格遞增或嚴格遞減子序列。
常見錯誤
(平均值不是每個鴿巢的下界)
平均佔用量不是每個鴿巢的下界。二十九個對象放入六個鴿巢,保證某個鴿巢至少有五個,但也可能全部二十九個都在同一鴿巢。同樣,一次碰撞不保證見證唯一。存在性證明不能悄悄變成唯一性結論,或精確的解數公式。
常見錯誤
(被 整除不等於每個餘數都出現)
連續和定理保證的是被定理中的 整除,並不保證每個指定餘數都能作為某個連續段之和的餘數。例如,當 時,全零數列沒有任何段和模 餘 。
總結
有效的鴿巢原理論證,先描述結論失敗會怎樣限制可能的記錄。佔用量界限制每個纖維;前綴餘數讓碰撞相減成為連續和;終點長度則保證,除非已有長單調子序列,否則所有標記對互異。每次都應核對記錄的數量、分配規則,以及碰撞究竟能推出甚麼。最後用尖銳例子檢驗哪個門檻必不可少,哪些更強結論並不受保證。
練習
快速檢查
(二十九個帶標號對象放入六個鴿巢。求總能保證的最大佔用量下界,並構造最大佔用量恰好達到該界的安排。是否必有兩個鴿巢各有至少五個對象?)
解答 · 答案
保證為 。佔用量 的總數是 ,最大值為 ,所以不能保證更大的最大值。但不一定有兩個鴿巢各有至少 個對象: 中只有一個這樣的鴿巢。這是不同的極值問題;均衡安排只回答最大佔用量最小能是多少。
快速檢查
(三個鴿巢各自的目標佔用量分別為 。求至少需要多少個對象,才能保證至少一個鴿巢達到自己的目標,並證明少一個對象不夠。)
解答 · 答案
若所有目標都未達到,佔用量至多分別為 ,總數至多為 。因此 個對象必使某個目標達到。只有 個時,向量 沒有達到任何目標。所以最少需要 個。用統一目標取平均會丟失各個容量不同的資訊。
快速檢查
(對每個 ,證明任意 個整數中,有兩個的差能被 整除。說明它與連續和定理有甚麼不同。對於 ,說明 項不足以保證存在被 整除的非空連續段之和。)
解答
把 個帶索引整數放入它們模 的 個餘數類。有兩個索引位於同一鴿巢,相應整數值相減就是 的倍數。原整數不必互異,差可以是零。
這裏的對象是原整數;連續和定理中的對象則是由 項構成的 個前綴和。兩個前綴之差透過消去共同項成為連續段。兩個構造證明的是不同結論。為說明項數門檻的尖銳性,取 項全部為 。每個非空段和都在 與 之間,不能被 整除。該例適用於 ;當 時,空數列同樣沒有非空段。
快速檢查
(證明 中任意七個點必有兩點距離不超過 。給出一個安排,說明不能對所有七點安排保證更小的距離。)
解答
把 分成五個區間 ,其中 ,以及最後一個區間 。這是六個互不相交、直徑均不超過 的鴿巢。七個帶索引點中有兩個落在同一鴿巢,故距離至多為 。
為證明不能提高,取 。任意兩個不同位置之間的最小距離為 ,所以任何嚴格小於 的統一距離界,都會被這個安排否定。
快速檢查
(對十三個兩兩不同的實數,取 、 時,單調子序列定理保證甚麼?構造十二個不同的數,使兩種結論都不成立,並分別解釋兩種限制。)
解答
因為 ,定理保證長度為 的遞增子序列,或長度為 的遞減子序列。長度為 時,取
遞增子序列在每個遞減三元組中至多取一項,因此長度至多為 。遞減子序列不能進入較後三元組,因為其中各項都更大,所以長度至多為 。兩個結論均失敗。僅僅寫出這個安排還沒有完成尖銳性證明,還必須給出這兩個限制的理由。
快速檢查
(解釋反例模組中允許重複值的替代定理為何在 或 時仍成立。當 時,它說的是甚麼?)
解答 · 答案
證明只用到終點標記的正整數範圍,所以其中一個範圍只有一個值時仍適用。若 ,則要麼有兩項按原順序非遞減,要麼每個較早項都嚴格大於每個較後項;後一種情況下,整個長 的數列都遞減。若 ,則要麼某個較早項大於某個較後項,要麼所有較早項都不大於較後項;後一種情況下,整個長 的數列都非遞減。當 時,結論是任意兩個實數項要麼非遞減,要麼嚴格遞減,恰好對應 與 兩種情形。