鸽巢原理
鸽巢原理（The Pigeonhole Principle）是一个非常显然的原理，但又有一些巧妙的应用。
鸽巢原理描述
鸽巢原理
如果将 N + 1 只鸽子放入 N 个盒子，则存在一个盒子，其中至少有两只鸽子。
广义鸽巢原理
如果将 N 只鸽子放入 k 个盒子，则存在一个盒子，其中至少有 \lceil N / k \rceil 只鸽子。
基本应用
案例
从去除大小王的 52 张扑克牌中选择多少张牌，才能保证至少有三张牌是同一花色（suit）？
鸽巢原理并没有要求放入盒子的方式，任意一种放入方式都适合鸽巢原理。
解：构造四个盒子，每个盒子对应一种花色，每选择一张牌就放入对应花色的盒子；再设选择 N 张牌，则 \lceil N / 4 \rceil \ge 3，解得 N 的最小值为 9。 由于这里放入盒子的选择不是任意的，需要再证明 8 是不可行的：分别选择 2 张梅花、方块、红桃、黑桃，则只有 2 张牌是同一花色，说明 8 不能保证。 由于问题具有单调性（见 （链接未公开）），说明 9 是最小值。
扑克牌问题变式：从去除大小王的 52 张扑克牌中选择多少张牌，才能保证至少有三张牌是红桃（heart）？
鸽巢原理不是万能的，这题就不适合鸽巢原理
解：最差的情况下，选择了 13 \times 3 = 39 种其他花色，然后再加上三张红桃，于是需要选择 42 张牌。
课后题
平面上五个整数点之间，至少有两个点的连线中点是整数点。
解：两个整数点的中点是整点当且仅当两点横、纵坐标的奇偶性都相同。而横纵坐标的奇偶性只有（奇，奇），（奇，偶），（偶，奇），（偶，偶）四种可能，给定五个点，根据鸽巢原理，至少有两个点的奇偶性相同。
空间中九个整数点之间，至少有两个点的连线中点是整数点
同上。
25 个男生和 25 个女生围成一个环坐在圆桌上，则一定有一个人的左右两人都是男生。
证明
这一问题的关键在于 25 是奇数；若是偶数个男生和女生，则可以按 BBGGBBGG…… 围成一个环，而不出现任何人的左右都是男生。 将圆桌的座位按 1, \dots, 50 编号，则男生要么有大于等于 13 人坐在奇数位置，要么有大于等于 13 人坐在偶数位置。假设有超过 13 人坐在奇数位置，则要从 25 个奇数中选择超过 13 个数，此时必定有两个奇数相邻，证明如下： 由于圆环的对称性，假定 1 号位置被选择了，则接下来为了避免出现相邻奇数，至少选择 5 号，接着至少选择 9 号……，于是第 13 人至少选择 49 号，但周长为 50 的圆环上 1 和 49 是相邻的奇数，矛盾。 男生座位的选择必定有有两个相邻奇数或相邻偶数，原命题得证。
巧妙应用
案例
棒球队问题：在
最长严格单调子序列问题
一个包含 n^2 + 1 个两两不同实数的序列至少有一个长为 n + 1 的单调子序列（增或减之一，也可能增减都存在）。
证明
（类似动态规划的状态思想） 设 a_1, \dots, a_{n^2 + 1} 两两不同，令 i_k 表示以 a_k 为起点的最长严格递增子序列，d_k 表示以 a_k 为起点的最长严格递减子序列。
假设原命题不成立，则对任意的 k 有 1 \le i_k \le n, 1 \le d_k \le n，于是至多有 n^2 个不同的 (i_k, d_k) 对。而由于 k 可取 1, \dots, n^2 + 1，由鸽巢原理，必定存在两对元组相同，设 s < t 且 i_s = i_t, j_s = j_t。
但这是不可能的。若 a_s > a_t，则 a_s 接在以 a_t 为起点的最长严格递减子列前，可以形成一个长度为 d_t + 1 的严格递减子列，则 d_s \ge d_t + 1；若 a_s < a_t，则 a_s 接在以 a_t 为起点的最长严格递增子列前，可以形成一个长度为 i_t + 1 的严格递增子列，则 i_s \ge i_t + 1；两种情形都与 i_s = i_t, j_s = j_t 矛盾。
Ramsey 理论
例
在六个人中，两个人之间的关系要么是朋友，要么是仇敌；则一定存在三个人，它们之间两两互为朋友或两两互为敌人。
证明：A 的另外五个人中，要么有三个人和 A 是朋友，要么有三个人和 A 是仇敌（由广义鸽巢原理得）。不妨设 B, C, D 和 A 是朋友，则分为两种情况：
- B, C, D 中存在一对是朋友，不妨设为 B, C，则 A, B, C 三人两两互为朋友；
- B, C, D 中任意一对都为敌人，命题已经成立。
Ramsey 数
Ramsey 数 R(m, n) 描述了在一个聚会中保证存在 m 人互为朋友或 n 人互为仇敌的最小人数。以上的例题证明了 R(3, 3) \le 6。
由于可以举反例证明五个人的聚会中不能保证以上命题成立，以上命题可以推出 R(3, 3) = 6。
读完了，有什么想法？
阅读已保存的问答示例，并循着引用回到原文。