有善始者实繁，能克终者盖寡。

# 基本的抽屉原理

将 $k+1$ 个物品放入 $k$ 个盒子，则至少有一个盒子中有一个物体。

# 推论：广义抽屉原理

将 $n_1 + n_2 + \dots + n_k$ 放入 $k$ 个盒子，则必存在一个 $i$, 使得第 $i$ 个盒子里不少于 $n_i$ 个物体。

# 例题

例 1 在一次会议中，参加会议的人中至少有两人认识的人数相等。(假设认识是相互的)

证明 假设有 $n$ 人，则认识的朋友数有 $0,1,\dots,n-1$ 共 $n$ 种情况。又，认识 $0$ 人与认识 $n-1$ 人不可能同时出现，于是共 $n-1$ 种情况。根据抽屉原理，即证。

例 2 从 $1$ 到 $2n$ 的正整数中任取 $n+1$ 个，则至少存在两个数，其中一个是另一个的倍数。

证明 设 $k=2^t(2l-1) \in \{1,2,\dots,2n\}$, 考虑对子 $(l,k), \, k=1,2,\dots,2n$. 则 $2l-1$ 共 $n$ 个不同取值。于是根据抽屉原理，必存在两对子 $(l_1,k_1)$ 及 $(l_2,k_2)$ 使得 $k_1 \neq k_2$ 而 $l_1 = l_2$, 则 $k_1$ 与 $k_2$ 间存在倍数关系。

证明 根据反证法易证。

例题 3 最少连接缆线问题：有 15 台工作站和 10 台服务器，每个工作站可以用一条电缆直接连到某个服务器，同一时刻的每个服务器只能接受一个工作站的访问。任何时刻，任选一组工作站$W_1,…,W_k,\,k\leq10$，需要保证这组工作站可以连接到不同的服务器。问最少需要多少缆线？

解 缆线条数 $N_{\min} = 60$. 首先构造 $N=60$ 的情况。

将工作站 $W_1,W_2,W_3,W_4,W_5$ 与服务器 $S_1,S_2,S_3,S_4,S_5$ 对应连接，共 $5$ 条缆线；再将工作站 $W_{11},W_{12},W_{13},W_{14},W_{15}$ 与服务器 $S_6,S_7,S_8,S_9,S_{10}$ 对应连接，共 $5$ 条缆线；最后将 $W_6,W_7,W_8,W_9,W_{10}$ 与其余所有服务器两两连接，共$5\times10=50$ 条缆线。则共耗费$60$ 条缆线。这种情况是显然符合要求的。

下面证明$N=60$ 为最小值。采用反证法，不妨$N=59$。根据抽屉原理，必存在一个服务器，只连接了$5$ 个工作站。于是考虑剩余的$10$ 个工作站，不满足要求。

例题 4 设$a_1,a_2,\dots,a_m$ 是正整数序列，则存在$k$ 和$l$，$1≤k≤l≤m$，使得$a_k + … + a_l$ 是$m$ 的倍数。

证明 考虑前项和序列$S_k=\sum_{i=1}^ka_i$ 若存在两项模$m$ 同余，不妨设为$S_k,S_l$ 且$k<l$，则$m|(S_l-S_k)$ 即$m|\sum_{i=k+1}^la_i$。否则，必存在某项$r$ 使得$m|S_r$，则$m|\sum_{i=1}^ra_i$。

例题 5 设$a_1,a_2,…,a_{100}$ 是由$1$ 和$2$ 构成的序列，且从任意数开始的连续$10$ 个数的和不超过$16$，即$a_i+a_{i+1}+…+a_{i+9}≤16,\,i=1,2,…,91$。则存在$h$ 和$k$，使得$a_{h} + a_{h+1} + \dots + a_{k}=39$。

例 6 在 $n^2+1$ 个不同实数构成的序列中，一定存在长为 $n+1$ 的严格单调子列。

证明 采用反证法，假设只存在长度不超过$n$ 的严格单调子列。对每个实数$a_i$，构造数对$(s_i,t_i)$。其中$s_i$ 为以$a_i$ 为首项的最长单调增子列的长度，$t_i$ 为以$a_i$ 为首项的最长单调减子列的长度。于是$s_i,t_i∈\{1,2,…,n\}$。根据抽屉原理，存在$i≠j$ 使得$(s_i,t_i)=(s_j,t_j)$，此时考虑$a_i$ 与$a_j$ 的大小关系，则矛盾！

这是一个相当有趣的问题！我们可以将其推广为一个组合数学中的基本定理：Erdos-Szekeres 定理。该定理的内容如下：

对$mn+1$ 个互不相同的实数组成的序列，其中必定存在长度为$m+1$ 的递增子列或长度为$n+1$ 的递减子列。

进一步地，如果我们引入偏序集的相关概念。那么我们可以将定理重新描述为：

$m,n \in \mathbb{N}_+$，$(S,\prec)$ 是一个偏序集，$|S|=mn+1$，那么$S$ 中总存在长度为$m+1$ 的链或长度为$n+1$ 的反链。

我们可以证明一个引理，即 Dilworth 定理。

偏序集最少的链划分数等于其最长反链长度。

采用数学归纳法即可证明。

例题 7 假设认识是相互的，证明$6$ 人中必存在$3$ 人相互认识或者相互不认识。(Ramsey 问题)

证明 转化成$K_6$ 红蓝而染色的同色三角形存在性问题，细致讨论即可，略。