鸽巢原理¶

定理 如果把 \(n+1\) 个物体放进 \(n\) 个盒子，那么至少有一个盒子包含两个或更多的物体

【例题】从整数 1, 2, ..., 200 中选取 101 个不同的整数。证明: 所选的数中存在两个整数，使得其中一个是另一个的因子

【证明】任何整数 \(n\) 可以分解为 \(n = 2^k \times a\) ，\(a\) 为奇数，1~200 中有 100 个奇数，所以选 101 个整数必然存在 2 个数的 \(a\) 相同，此时两数能整除

【例题: 中国剩余定理】令 \(m, n\) 是互素的正整数，\(a\) 和 \(b\) 分别是小于 \(m\) 和 \(n\) 的非负整数。那么，存在正整数 \(x\)，使得 \(x\) 除以 \(m\) 余数为 \(a\) 且除以 \(n\) 余数为 \(b\)，即 \(x \equiv a(\mathrm{mod} \space m), x \equiv b(\mathrm{mod} \space n)\)

【证明】

考虑 \(n\) 个除以 \(m\) 余 \(a\) 的整数:

\[ a, m+a, 2m+a,\cdots,(n-1)m+a \]

假设其中存在两个数 \(im+a\) 和 \(jm+a\) (\(0 \leqslant i < j \leqslant n-1\)) 除以 \(n\) 的余数都为 \(r\)，即 \(im+a = kn + r,jm+a = ln + r\) ，两式相减得 \((j-i)m = (l-k)n\) ，由于 \(m,n\) 互素，因此 \(n\) 是 \(j-i\) 的因子，又 \(0 < j-i \leqslant n-1\) ，所以矛盾

故上述 \(n\) 个整数除以 \(n\) 的余数各不相同，所以 \(b\) 也应该在里面

加强形式¶

定理 令 \(q_1, q_2,\cdots, q_n\) 为正整数。若将 \(q_1+q_2+ \cdots +q_n - n+1\) 个物体放进n个盒子内，那么， - 或者第 1 个盒子至少含有 \(q_1\) 个物体 - 或者第 2 个盒子至少含有 \(q_2\) 个物体 - ... - 或者第 n 个盒子至少含有 \(q_n\) 个物体

推论 设 \(n\) 和 \(r\) 都是正整数，如果 \(n(r-1)+1\) 个物体放入 \(n\) 个盒子，则至少有一个盒子含有至少 \(r\) 个物体

【例题】证明: 每个由 \(n^2+1\) 个实数构成的序列 \(a_1, a_2,\cdots,a_{n^2+1}\) 或者含有长度为 \(n+1\) 的递增子序列，或者含有长度为 \(n+1\) 的递减子序列

【证】假设不存在长度为 \(n+1\) 的递增子序列，只需要构造一个长度为 \(n+1\) 的递减子序列

设 \(l_k\) 是以 \(a_k\) 为起始的最长递增子序列长度，则对 \(\forall k\) 有 \(1 \leqslant l_k \leqslant n\)，对 \(l_1, l_2, \cdots, l_{n^2+1}\) 运用鸽巢原理，一定存在 \(\left \lceil (n^2+1)/n\right \rceil = n+1\) 个 \(l_i\) 相等
设 \(l_{k_1} = l_{k_2} = \cdots = l_{k_{n+1}}\) (\(k_i\) 严格单增)，下证 \(a_{k_1},a_{k_2},\cdots, a_{k_{n+1}}\) 是递减序列
假设存在 \(a_{k_{i}} < a_{k_{i+1}}\) ，那么将有 \(l_{k_i} > l_{k_{i+1}}\) ，与 \(l_{k_i} = l_{k_{i+1}}\) 矛盾

Ramsey定理¶

一个实例: 在6个人中， - 或者有3个人，他们中每两个人都互相认识； - 或者有3个人，他们中的每两个人都彼此不认识

可以转化为给完全图 \(K_6\) 的边任意着红色、蓝色后，一定存在一个红色 \(K_3\) 或蓝色 \(K_3\)，记为 \(K_6 \rightarrow K_3, K_3\)

而且使得 \(K_n \rightarrow K_3, K_3\) 成立的最小正整数为 \(6\) ，Ramsey数 \(r(3,3) = 6\)

Ramsey定理 如果 \(m \geqslant 2\) 及 \(n\geqslant2\) 是两个整数，则一定存在正整数 \(p\)，使得 \(K_p \rightarrow K_m, K_n\)