鸽巢原理
一、课上练习
编程练习
（暂无）
二、知识总结
✨ 核心思想
鸽巢原理（Pigeonhole Principle），又称抽屉原理，是组合数学中最简单却最强大的工具之一。其核心思想朴素至极：如果要把多于 n 个物品放进 n 个容器，那么至少有一个容器里有不少于两个物品。看似简单，但灵活运用可以解决很多看起来毫无头绪的竞赛问题。
✨ 定理内容
基本形式：将 n+1 个物品放入 n 个容器中，则至少有一个容器包含至少 2 个物品。
一般形式：将 n 个物品放入 k 个容器中，则至少有一个容器包含至少 ⌈n/k⌉ 个物品。
加强形式：若将 n₁ + n₂ + ... + nₖ - k + 1 个物品放入 k 个容器中，则存在某个 i，使得第 i 个容器至少含有 nᵢ 个物品。
逆向使用：如果每个容器最多放 m 个物品，k 个容器最多放 mk 个物品。若物品数超过 mk，则不可能每个容器都不超过 m 个。
✨ 经典问题与证明
问题 1：在任意 13 个人中，至少有 2 个人的生日在同一个月。
证明：12 个月（容器），13 个人（物品），13 > 12，由鸽巢原理至少有 2 人同月。
问题 2：在任意 n+1 个 1 到 2n 之间的整数中，必有两个数互素。
证明：将 1~2n 分成 n 组：{1,2}, {3,4}, {5,6}, ..., {2n-1,2n}。选 n+1 个数，由鸽巢原理至少有两个数在同一组，同组两数相邻，gcd=1。
问题 3：在任意 n+1 个 1 到 2n 之间的整数中，必有一个能整除另一个。
证明：任意正整数可以唯一写成 2^a × b 的形式（b 为奇数）。1~2n 中的奇数有 n 个：1, 3, 5, ..., 2n-1。每个选出的数的"奇数部分"必属于这 n 个之一。选 n+1 个数，由鸽巢原理至少两个数有相同的奇数部分 b，设为 2^a₁ × b 和 2^a₂ × b，若 a₁ < a₂ 则前者整除后者。
问题 4：任意 5 个点在边长为 1 的正方形内，则至少有两个点的距离不超过 √2/2。
证明：将正方形分成 4 个边长为 1/2 的小正方形。5 个点放入 4 个小正方形，由鸽巢原理至少有 2 个点在同一个小正方形中。小正方形的对角线长为 √2/2，所以这两点的距离不超过 √2/2。
✨ 代码实现
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// 在 n+1 个取值范围为 [1, n] 的数中找到重复的数
6// 利用鸽巢原理保证一定存在重复
7// Floyd 判圈法：O(n) 时间 O(1) 空间
8int findDuplicate(vector<int>& nums) {
9 // 将数组看作链表：i -> nums[i]
10 // 由鸽巢原理，必存在重复值，即链表中必有环
11 int slow = nums[0];
12 int fast = nums[nums[0]];
13
14 // 第一步：快慢指针找到环中的相遇点
15 while (slow != fast) {
16 slow = nums[slow];
17 fast = nums[nums[fast]];
18 }
19
20 // 第二步：找到环的入口（即重复的数）
21 slow = 0;
22 while (slow != fast) {
23 slow = nums[slow];
24 fast = nums[fast];
25 }
26
27 return slow;
28}
29
30int main() {
31 int n;
32 cin >> n;
33 vector<int> nums(n + 1);
34 for (int i = 0; i <= n; i++) {
35 cin >> nums[i];
36 }
37 cout << "重复的数是: " << findDuplicate(nums) << endl;
38 return 0;
39}1#include <iostream>
2#include <vector>
3using namespace std;
4
5// 给定 n 个正整数，证明并找出存在连续子序列的和能被 n 整除
6void findDivisibleSubsequence(vector<int>& a, int n) {
7 // 前缀和 s[0]=0, s[1]=a[0], s[2]=a[0]+a[1], ...
8 // 共 n+1 个前缀和，模 n 后取值范围 [0, n-1]
9 // 由鸽巢原理，至少有两个前缀和模 n 相同
10 vector<int> prefix(n + 1, 0);
11 vector<int> seen(n, -1); // seen[r] = 前缀和模 n 为 r 的最早下标
12
13 seen[0] = 0; // s[0] = 0, 模 n 为 0
14 for (int i = 1; i <= n; i++) {
15 prefix[i] = prefix[i-1] + a[i-1];
16 int r = ((prefix[i] % n) + n) % n;
17
18 if (seen[r] != -1) {
19 // 找到了！从 seen[r]+1 到 i 的子序列
20 int l = seen[r];
21 cout << "子序列 a[" << l+1 << ".." << i << "] 的和为 "
22 << prefix[i] - prefix[l]
23 << "，能被 " << n << " 整除" << endl;
24 return;
25 }
26 seen[r] = i;
27 }
28}
29
30int main() {
31 int n;
32 cin >> n;
33 vector<int> a(n);
34 for (int i = 0; i < n; i++) cin >> a[i];
35 findDivisibleSubsequence(a, n);
36 return 0;
37}✨ 应用示例
示例：给定 5 个整数 3, 7, 11, 15, 20，证明并找出连续子序列的和能被 5 整除。
前缀和：s[0]=0, s[1]=3, s[2]=10, s[3]=21, s[4]=36, s[5]=56
模 5 后：0, 3, 0, 1, 1, 1
s[0] 和 s[2] 模 5 都为 0，所以 a[1]+a[2] = 3+7 = 10，能被 5 整除。
或者 s[3] 和 s[4] 模 5 都为 1，所以 a[4] = 15，能被 5 整除。
✨ 解题步骤详解
- 识别"鸽子"和"巢"：确定哪些是物品（要分配的对象），哪些是容器（分类依据）
- 构造分类：这是最关键也最有技巧的一步，需要根据问题巧妙设计"巢"
- 比较数量：物品数 > 容器数 × 每巢容量，则存在某巢超过容量
- 得出结论：在同一"巢"中的元素必定满足某种共同性质
常见"巢"的构造方法：
- 按模运算分类（余数相同）
- 按区间分段
- 按几何区域划分
- 按某种属性分组（如奇数部分相同）
✨ 常见错误
- 不会确定"鸽子"和"巢"，问题建模失败
- "巢"的数量计算错误，导致无法应用鸽巢原理
- 忽略了一般形式，只记得基本形式（n+1 个物品 n 个巢）
- 混淆"存在性证明"和"构造性求解"——鸽巢原理通常用于证明存在，不直接给出具体方案
- 在编程题中，用鸽巢原理确认解的存在后，忘记实际找出解的具体位置
✨ 总结
鸽巢原理的魅力在于：
- 简洁性：定理本身极其简单，几乎不需要任何前置知识
- 广泛性：应用范围覆盖数论、几何、图论、分析等多个领域
- 技巧性：困难之处不在定理本身，而在于如何巧妙构造"巢"
在竞赛中，鸽巢原理常用于：
- 证明存在性问题
- 前缀和 + 模运算找连续子序列
- 几何问题中的距离约束
- 数论问题中的整除关系
掌握鸽巢原理的关键是大量练习不同类型的问题，培养"看到数量关系就想到鸽巢"的直觉。