Skip to content

第三章 鸽巢原理

3.1 鸽巢原理

定理 3.1.1

如果要将 n+1\displaystyle{ n + 1 } 个物体放进 n\displaystyle{ n } 个盒子,那么至少有一个盒子包含两个或更多的物体

题 1

给定 m\displaystyle{ m } 个整数 a1,a2,am\displaystyle{ a _{ 1 } , a _{ 2 } , \ldots a _{ m } },存在 0k<lm\displaystyle{ 0 \leqslant k < l \leqslant m } 的整数 k,l\displaystyle{ k , l },使得 i=k+1lai\displaystyle{ \sum _{ i = k + 1 } ^{ l } a _{ i } } 能够被 m\displaystyle{ m } 整除。

考虑 m\displaystyle{ m } 个前序和 Sk=i=1kai\displaystyle{ S _{ k } = \sum _{ i = 1 } ^{ k } a _{ i } },如果和中任意一个能被 m\displaystyle{ m } 整除,则结论成立。

假设这些和中的每个除以 m\displaystyle{ m } 都有一个非零余数,则余数为 1,2,,m1\displaystyle{ 1 , 2 , \ldots , m - 1 }. 而实际上,余数有 m1\displaystyle{ m - 1 } 种选择,但和有 m\displaystyle{ m } 个,所以必然有两个不同的和,它们的余数相等,假设这两个和分别为 Sk,Sl,k<l\displaystyle{ S _{ k } , S _{ l } , k < l },则 SlSk\displaystyle{ S _{ l } - S _{ k } } 除以 m\displaystyle{ m } 的余数为 0.

题 3.1.2

柯洁有 11 周时间备战比赛,每天至少下一盘棋,但每周不超过 12 盘,证明存在若干天,这期间恰好下了 21 盘

i\displaystyle{ i } 天下 ai\displaystyle{ a _{ i } } 盘,a1,,a77\displaystyle{ a _{ 1 } , … , a _{ 77 } },要证 i=mnai=21\displaystyle{ \exists \sum _{ i = m } ^{ n } a _{ i } = 21 }

Si=k=1iai\displaystyle{ S _{ i } = \sum _{ k = 1 } ^{ i } a _{ i } },要证 SjSi=21\displaystyle{ \exists S _{ j } - S _{ i } = 21 },有条件

1S1<S2<<S77132\displaystyle{ 1 \leqslant S _{ 1 } < S _{ 2 } < … < S _{ 77 } \leqslant 132 }22S1+21<S2+21<<S77153\displaystyle{ 22 \leqslant S _{ 1 } + 21 < S _{ 2 } + 21 < … < S _{ 77 } \leqslant 153 }

那么这两个不等式的 154 项在 1~153 之间,那么就有两个 X=Si,Y=Sj+21\displaystyle{ X = S _{ i } , Y = S _{ j } + 21 } 两者相等,即 SiSj=21\displaystyle{ S _{ i } - S _{ j } = 21 }

另证

三周内最多下 36 盘棋,有 1S1<S2<<S2136\displaystyle{ 1 \leqslant S _{ 1 } < S _{ 2 } < … < S _{ 21 } \leqslant 36 }

  • Si0mod21,1Si=21p36,p=1\displaystyle{ \exists S _{ i } \equiv 0 \operatorname{mod} 21 , 1 \leqslant S _{ i } = 21 \cdot p \leqslant 36 , p = 1 }
  • Si≢0mod21,SiSj0mod21,SiSj=21p35,p=1\displaystyle{ \forall S _{ i } \not\equiv 0 \operatorname{mod} 21 , S _{ i } - S _{ j } \equiv 0 \operatorname{mod} 21 , S _{ i } - S _{ j } = 21 \cdot p \leqslant 35 , p = 1 }

题 3.1.3

从整数 1~200 中选 101 个数,证在所选的数中存在两个数,一个可以被另一个整除

证:将集合划分为奇数和偶数,每个数都能表示为 ai=2piqi\displaystyle{ a _{ i } = 2 ^{ p _{ i } } \cdot q _{ i } },其中 q\displaystyle{ q } 为奇数

由于取了 101 个数,则必存在两个数 ai=2piqi,aj=2pjqj\displaystyle{ a _{ i } = 2 ^{ p _{ i } } \cdot q _{ i } , a _{ j } = 2 ^{ p _{ j } } \cdot q _{ j } },其奇数部分相同,不妨设 pi<pj\displaystyle{ p _{ i } < p _{ j } },则 ajaj=2pjpi\displaystyle{ \frac{ a _{ j } }{ a _{ j } } = 2 ^{ p _{ j } - p _{ i } } }

中国剩余定理

m\displaystyle{ m }n\displaystyle{ n } 是互质的正整数,设 a,b\displaystyle{ a , b } 为整数,其中 0am1\displaystyle{ 0 \leqslant a \leqslant m - 1 }0bn1\displaystyle{ 0 \leqslant b \leqslant n - 1 },于是存在正整数 x\displaystyle{ x } 使得 xa(modm),xb(modn)\displaystyle{ x \equiv a \left( \operatorname{mod} m \right) , x \equiv b \left( \operatorname{mod} n \right) }

  • 考虑 n\displaystyle{ n } 个整数 a,m+a,2m+a,,(n1)m+a\displaystyle{ a , m + a , 2 m + a , \ldots , \left( n - 1 \right) m + a },这些整数中的每一个除以 m\displaystyle{ m } 都余 a\displaystyle{ a }
  • n\displaystyle{ n } 个数中的每一个数除以 n\displaystyle{ n } 都有不同的余数
    • 设其中两个除以一n\displaystyle{ n } 有相同的余数 r\displaystyle{ r },令这两个数为 im+a,jm+a\displaystyle{ i m + a , j m + a },其中 0i<jn1\displaystyle{ 0 \leqslant i < j \leqslant n - 1 },于是存在两个整数 qi,qj\displaystyle{ q _{ i } , q _{ j } } 使得 im+a=qin+r\displaystyle{ i m + a = q _{ i } n + r }jm+a=qjn+r\displaystyle{ j m + a = q _{ j } n + r }
    • 两式相减得 (ji)m=(qiqj)n\displaystyle{ \left( j - i \right) m = \left( q _{ i } - q _{ j } \right) n },即 n\displaystyle{ n }ji\displaystyle{ j - i } 的因子,矛盾
  • 根据鸽巢原理,n\displaystyle{ n } 个数 0,1,,n1\displaystyle{ 0 , 1 , \ldots , n - 1 } 中的每一个都要作为余数出现,特别是 b\displaystyle{ b } 也是如此

3.2 加强版

定理 3.2.1

q1,q2,qn\displaystyle{ q _{ 1 } , q _{ 2 } , \ldots q _{ n } } 是正整数,如果将 q1++qnn+1\displaystyle{ q _{ 1 } + \ldots + q _{ n } - n + 1 } 个物体放入 n\displaystyle{ n } 个盒子内,则第 1 个盒子至少含有 q1\displaystyle{ q _{ 1 } } 个物体,或者 2 至少含有 q2\displaystyle{ q _{ 2 } } 个物体,…,或者 n\displaystyle{ n } 至少含有 qn\displaystyle{ q _{ n } } 个物体。

证明:反证法,假设其反命题为真,即使得第一个盒子少于 q1\displaystyle{ q _{ 1 } } 个物体,且……,且第 n\displaystyle{ n } 个盒子少于 qn\displaystyle{ q _{ n } } 个物体。该情况下最多有 i=1nqin\displaystyle{ \sum _{ i = 1 } ^{ n } q _{ i } - n } 个物体,与上述条件矛盾。

推论 3.2.2

n\displaystyle{ n }r\displaystyle{ r } 都是正整数,如果把 n(r1)+1\displaystyle{ n \left( r - 1 \right) + 1 } 个物体分配到 n\displaystyle{ n } 个格子中,那么至少有一个盒子含有 r\displaystyle{ r } 个或更多的物体。

平均原理

如果 n\displaystyle{ n } 个非负整数 m1,,mn\displaystyle{ m _{ 1 } , \ldots , m _{ n } } 的平均数大于 r1\displaystyle{ r - 1 },即 1ni=1nmi>r1\displaystyle{ \frac{ 1 }{ n } \sum _{ i = 1 } ^{ n } m _{ i } > r - 1 },那么至少有一个整数大于或等于 r\displaystyle{ r }.

如果 n\displaystyle{ n } 个非负整数 m1,,mn\displaystyle{ m _{ 1 } , \ldots , m _{ n } } 的平均数小于 r+1\displaystyle{ r + 1 },即 1ni=1nmi<r+1\displaystyle{ \frac{ 1 }{ n } \sum _{ i = 1 } ^{ n } m _{ i } < r + 1 },那么至少有一个整数小于 r\displaystyle{ r }.

题 3.2.2

n2+1\displaystyle{ n ^{ 2 } + 1 } 个不同的实数构成的序列一定含有长度为 n+1\displaystyle{ n + 1 } 的单调子序列

证明

假设 a1,a2,,an2+1\displaystyle{ a _{ 1 } , a _{ 2 } , \ldots , a _{ n ^{ 2 } + 1 } } 的增序列长度不超过 n\displaystyle{ n },去找长度为 n+1\displaystyle{ n + 1 } 的降序列

mk\displaystyle{ m _{ k } } 为从 ak\displaystyle{ a _{ k } } 开始的最长递增子序列的长度,k=1,2,,n2+1\displaystyle{ k = 1 , 2 , \ldots , n ^{ 2 } + 1 }

1mkn\displaystyle{ 1 \leqslant m _{ k } \leqslant n }m1,mn2+1\displaystyle{ m _{ 1 } , \ldots m _{ n ^{ 2 } + 1 } } 是 1 和 n\displaystyle{ n } 之间的 n2+1\displaystyle{ n ^{ 2 } + 1 } 个整数,因此其中至少有 n+1\displaystyle{ n + 1 } 个数是相等的。

mk1=mk2==mkn+!\displaystyle{ m _{ k _{ 1 } } = m _{ k _{ 2 } } = \ldots = m _{ k _{ n {+ !} } } },其中 1k1<k2<<kn+1n2+1\displaystyle{ 1 \leqslant k _{ 1 } < k _{ 2 } < \ldots < k _{ n + 1 } \leqslant n ^{ 2 } + 1 }

akiaki+1\displaystyle{ a _{ k _{ i } } \geqslant a _{ k _{ i + 1 } } }ak1,ak2,,akn+1\displaystyle{ a _{ k _{ 1 } } , a _{ k _{ 2 } } , \ldots , a _{ k _{ n + 1 } } } 是长度为 n+1\displaystyle{ n + 1 } 的递减子序列

3.3 Ramsey 定理

6 个节点的完全图,使用两种颜色来染边,要么存在红色三角形,要么存在蓝色三角形 K6K3,K3\displaystyle{ K _{ 6 } \to K _{ 3 } , K _{ 3 } }

点 A 为起始节点, BCDEF 边一定有三条是同色的,选出这三条同色边,不妨是 AB, AC,假设 BC 为红边,则存在红色三角形。假设 BC 为蓝边,则 BCD 可以尝试去构造一个蓝色三角形。

定理 3.3.1

如果 m2,n2\displaystyle{ m \geqslant 2 , n \geqslant 2 } 是两个整数,则存在正整数 p\displaystyle{ p },使得 KpKm,Kn\displaystyle{ K _{ p } \to K _{ m } , K _{ n } }

证明 KpKm,Kn\displaystyle{ K _{ p } \to K _{ m } , K _{ n } }KpKn,Km\displaystyle{ K _{ p } \to K _{ n } , K _{ m } } 等价

设染色空间 C=2(p2)\displaystyle{ \left| C \right| = 2 ^{ { p \choose 2 } } },将原先 C\displaystyle{ C } 中的任意边 c\displaystyle{ c } 蓝边变为红边,原先的红边变为蓝边,这个映射 f:CC\displaystyle{ f : C \to C } 是单射,也是满射,所以是双射,有 cC\displaystyle{ \forall c \in C }f(c)C\displaystyle{ \forall f \left( c \right) \in C }.

r(2,n)=r(n,2)=n\displaystyle{ r \left( 2 , n \right) = r \left( n , 2 \right) = n }

p=r(m1,n)+r(m,n1)\displaystyle{ p = r \left( m - 1 , n \right) + r \left( m , n - 1 \right) },下证 KpKm,Kn\displaystyle{ K _{ p } \to K _{ m } , K _{ n } }

以某个点 x\displaystyle{ x } 为起始,有 p1\displaystyle{ p - 1 } 条出边。将 p1\displaystyle{ p - 1 } 边分为两类,即蓝边和红边,表示为 Rx+Bx=p1\displaystyle{ \left| R _{ x } \right| + \left| B _{ x } \right| = p - 1 }Rx+Bx=r(m1,n)+r(m,n1)2+1\displaystyle{ \left| R _{ x } \right| + \left| B _{ x } \right| = r \left( m - 1 , n \right) + r \left( m , n - 1 \right) - 2 + 1 },由鸽巢原理加强版,要么 Rx\displaystyle{ \left| R _{ x } \right| } ……或者 Bx\displaystyle{ \left| B _{ x } \right| } ……