§9 鸽巢原理之二 §9 鸽巢原理之二 鸽巢原理二 m1 , m2 , … , mn都是正整数， 并有m1 + m2 +… +mn－n + 1个鸽子住进n个鸽巢，则至少对某个 i 有第 i 个巢 中至少有mi个鸽子，i = 1 , 2 , … , n． 上一小节的鸽巢原理一是这一原理的特殊情况，即 m1 = m2 = … = mn= 2， m1 + m2 +… +mn－n + 1 = n + 1 如若不然，则对任一 i， 都有第 i 个巢中的鸽子数≤mi－1 则 鸽子总数≤ m1 + m2 +… +mn－n ，与假设相矛盾 [推论１] m只鸽子进n个巢，至少有一个巢里有 src="3_9_1.gif" align="middle" width="33" height="45">只鸽子． [推论２] n(m－1) + 1只鸽子进n个巢，至少有一个巢内至少有m只鸽子． [推论３] 若m1 , m2 , … , mn是正整数，且 src="3_9_2.gif" align="middle" width="122" height="42">, 则 m1,… , mn至少有一个不小于r 例 设A= a1a2···a20是10个0和10个1 组成的 ２进制数．B=b1b2···b20是任意的２进制数． C = b1b2···b20 b1b2···b20 = C1C2···C40， 则 存在某个i ，1≤ i ≤20，使得 CiCi+1···Ci+19与a1a2···a20至少有10位对应相等． 证 在C = C1C2···C40中，当 i 遍历1 , 2 , … , 20时，每一个bj历遍 a1 , a2 , … , a20．因A中 有10个0和10个1，每一个bj都有10位次对应相等．从而当 i历遍1 , … , 20时，共有 10 · 20=200位次对应相等．故对每个 i平均 有200／20 = 10位相等，因而对某个 i 至少 有10位对应相等． 定理 若序列S ={ a1 , a2 , … , amn+1}中的各 数是不等的．m , n 是正整数，则 S有一长 度为m+1的严格增子序列或长度为n+1的减 子序列，而且 S有一长度为m+1的减子序列 或长度为n+1的增子序列． [证１] 由S中的每个 ai 向后选取最长增子序列，设其长度为li ，从而得序列 L = { l1 , l2 , … , lmn+1 }．若存在 lk≥m+1 则结论成立． 否则所有的 li ∈[ 1 , m]，其中必有 [证２] 从ai 向后取最长增子列及减子列，设 其长度分别为 li ，l’i . 若任意 i ，都有li ∈[ 1，m], l’i∈［１，n］, 不超过mn种对．则 存在 j ＜k，( lj , l’j ) = ( lk , l’k ) 若aj＜ak，则 lj >lk， 若aj＞ak，则 l’j >l’k ，矛盾． [例] 将[ 1 , 65 ]划分为４个子集，必有一个子集中有一数是同子集中的两数之差． [证] 用反证法． 设此命题不真．即 存在划分P1∪P2∪P3∪P4＝[ 1，65 ]，Pi 中不存在一个数是Pi中两数之差，i=1,2,3,4 因 align="middle" width="69" height="45">，故有一子集，其中至少有17 个数，设这17个数从小到大为a1 , … , a17 ． 不妨设 A={a1 , … , a17 } height="17">P1。 令bi－1= ai－a1，i = 2，···，17。 设 B＝｛b1, ··· , b16}，B src="3_9_7.gif" align="middle" width="18" height="14">[ 1 , 65 ]。 由反证法假设B∩P1 = ф。因而 B( P2∪P3∪P4 )。 因为，不妨设{b1 , ··· , b6} height="17">P2 ， 令Ci－1=bi－b1，i = 2， ···，6. 设C＝{ C1 , ··· , C5 }，C src="3_9_7.gif" align="middle" width="18" height="14">[ 1 , 65 ] 由反证法假设C∩( P1∪P2 ) =ф，故有 C(P3∪P4 ) 因为，不妨设{C1 , C2 , C3 } height="14">P3 令 di－1= Ci－C1，i = 2 , 3． 设 D＝{ d1 , d2 } , D width="18" height="14">[ 1 , 65]。 由反证法假设 D∩( P1∪P2∪P3 )=ф，因而 DP4 。 由反证法假设 d2－d1P1∪P2∪P3 且d2－d1 height="18">P4 ， 故 d2－d1 height="18">[ 1 , 65 ]，但显然 d2－d1 ∈ [ 1 , 65 ]， 矛盾。
