第三章 鸽巢原理

3.1 鸽巢原理

定理 3.1.1

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

题 1

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

证

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

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

题 3.1.2

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

第 $\displaystyle{ i }$ 天下 $\displaystyle{ a _{ i } }$ 盘，$\displaystyle{ a _{ 1 } , … , a _{ 77 } }$，要证 $\displaystyle{ \exists \sum _{ i = m } ^{ n } a _{ i } = 21 }$

证

设 $\displaystyle{ S _{ i } = \sum _{ k = 1 } ^{ i } a _{ i } }$，要证 $\displaystyle{ \exists S _{ j } - S _{ i } = 21 }$，有条件

$$\displaystyle{ 1 \leqslant S _{ 1 } < S _{ 2 } < … < S _{ 77 } \leqslant 132 }$$$$\displaystyle{ 22 \leqslant S _{ 1 } + 21 < S _{ 2 } + 21 < … < S _{ 77 } \leqslant 153 }$$

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

另证

三周内最多下 36 盘棋，有 $\displaystyle{ 1 \leqslant S _{ 1 } < S _{ 2 } < … < S _{ 21 } \leqslant 36 }$

• 若 $\displaystyle{ \exists S _{ i } \equiv 0 \operatorname{mod} 21 , 1 \leqslant S _{ i } = 21 \cdot p \leqslant 36 , 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 个数，证在所选的数中存在两个数，一个可以被另一个整除

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

由于取了 101 个数，则必存在两个数 $\displaystyle{ a _{ i } = 2 ^{ p _{ i } } \cdot q _{ i } , a _{ j } = 2 ^{ p _{ j } } \cdot q _{ j } }$，其奇数部分相同，不妨设 $\displaystyle{ p _{ i } < p _{ j } }$，则 $\displaystyle{ \frac{ a _{ j } }{ a _{ j } } = 2 ^{ p _{ j } - p _{ i } } }$

中国剩余定理

$\displaystyle{ m }$ 和 $\displaystyle{ n }$ 是互质的正整数，设 $\displaystyle{ a , b }$ 为整数，其中 $\displaystyle{ 0 \leqslant a \leqslant m - 1 }$ 且 $\displaystyle{ 0 \leqslant b \leqslant n - 1 }$，于是存在正整数 $\displaystyle{ x }$ 使得 $\displaystyle{ x \equiv a \left( \operatorname{mod} m \right) , x \equiv b \left( \operatorname{mod} n \right) }$

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

3.2 加强版

定理 3.2.1

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

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

推论 3.2.2

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

平均原理

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

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

题 3.2.2

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

证明

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

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

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

令 $\displaystyle{ m _{ k _{ 1 } } = m _{ k _{ 2 } } = \ldots = m _{ k _{ n {+ !} } } }$，其中 $\displaystyle{ 1 \leqslant k _{ 1 } < k _{ 2 } < \ldots < k _{ n + 1 } \leqslant n ^{ 2 } + 1 }$

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

3.3 Ramsey 定理

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

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

定理 3.3.1

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

证明 $\displaystyle{ K _{ p } \to K _{ m } , K _{ n } }$ 与 $\displaystyle{ K _{ p } \to K _{ n } , K _{ m } }$ 等价

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

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

$\displaystyle{ p = r \left( m - 1 , n \right) + r \left( m , n - 1 \right) }$，下证 $\displaystyle{ K _{ p } \to K _{ m } , K _{ n } }$

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