鸽笼原理

鸽笼原理，也称为抽屉原理，是数学中常用于证明 存在性 的基本原理之一。它以朴素的方式揭示了 物多坑少则必有重 的逻辑，被广泛应用于数论、组合、概率等问题中。

---

一、基本原理

经典形式：

若将 $n+1$ 个物体放入 $n$ 个抽屉中，则至少有一个抽屉中含有不少于两个物体。

数学表达：

设 $n, k \in \mathbb{N}^+$，将 $n$ 个物体放入 $k$ 个抽屉中，则至少存在一个抽屉，放入的物体数量不少于：

\[ \left\lceil \dfrac{n}{k} \right\rceil \]

证明方法（反证法）： 假设每个抽屉中最多只能放 $\left\lfloor \dfrac{n}{k} \right\rfloor$ 个物体，则最多可放：

\[ k \times \left\lfloor \dfrac{n}{k} \right\rfloor < n \quad \text{（不等式成立）} \]

矛盾，因此至少存在一个抽屉中包含不少于 $\left\lceil \dfrac{n}{k} \right\rceil$ 个物体。

---

二、典型例子与应用

例 1：生日问题

在 $1500$ 人中，至少有 $5$ 人生日相同。

• 因为一年最多有 $366$ 天（含闰年），可视作 $366$ 个抽屉。
• $\left\lceil \dfrac{1500}{366} \right\rceil = 5$
• 所以至少有一个日期，有 $\ge 5$ 人的生日。

例 2：选数求和问题

从 $1 \sim 8$ 中任选 $5$ 个不同整数，必定存在两个数之和为 $9$。

分析：将 $(1,8), (2,7), (3,6), (4,5)$ 分为 $4$ 对数对（互补为 $9$ 的组合）。如果最多从每组中选一个数字，最多选 $4$ 个。

• 选 $5$ 个必定至少有一对来自同一组。
• 因此必然存在两个数之和为 $9$。

---

三、变形与扩展

强化版：多重鸽笼原理

若 $n$ 个物体放入 $k$ 个抽屉中，且 $n > k \times m$，则至少有一个抽屉中含有不少于 $m+1$ 个物体。

概率论中的鸽笼思想

概率上也常见鸽笼的思想，例如在有限样本空间中证明事件必然发生。

---

四、应用总结

类型	应用方向	示例
存在性证明	数学归纳、构造反例	至少两人生日相同
数论	同余、余数问题	任意 $n+1$ 个整数中，至少有两个模 $n$ 同余
组合与概率	最坏情况分析	抽球问题、抽签问题
编程题常用技巧	存在性+构造题	输入中至少存在重复元素等

---

五、例题

• [ABC200D] Happy Birthday! 2

简化题意：给定一个长度为 $N$ 的正整数序列 $A$，请你构造两个严格递增的下标序列 $B$ 和 $C$，使得：

• $1 \leq |B|, |C| \leq N$

• $B$ 与 $C$ 互不相同（长度不同，或某一位下标不同）

• $\sum A[B_i] \equiv \sum A[C_j] \pmod{200}$

也就是说，你要从 $A$ 中挑出两个不一样的子序列（按下标），它们在模 $200$ 意义下的元素和相等。

鸽笼原理应用：如果可以生成至少 $201$ 个子序列，则必然有两个子序列的和 $\bmod 200$ 是相同的。

因此，使用 DFS 或二进制枚举对于前 $8$ 个元素进行枚举，直接生成 $2^8$ 个子序列，然后判断是否有两个子序列和 $\bmod 200$ 相等。

• 若 $n<8$ 相当于生成所有的子序列。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 205;
int n, a[N];
bool vis[N];
map<int, vector<vector<int>>> mp;
void dfs(int dep)
{
    if (dep == n + 1)
    {
        int sum = 0;
        vector<int> t;
        for (int i = 1; i <= n; i++)
        {
            if (vis[i] == 1)
            {
                sum = (sum + a[i]) % 200;
                t.push_back(i); // 存储下标 
            }
        }
        mp[sum].push_back(t);
        return ;
    }
    vis[dep] = 1;
    dfs(dep + 1);
    vis[dep] = 0;
    dfs(dep + 1);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    n = min(n, 8);
    dfs(1);
    for (int mod = 0; mod < 200; mod++)
    {
        if (mp[mod].size() > 1) // 说明有两个以上了
        {
            cout << "Yes\n";
            vector<int> x = mp[mod][0];
            cout << x.size() << " ";
            for (auto it : x) cout << it << " ";
            cout << "\n";
            vector<int> y = mp[mod][1];
            cout << y.size() << " ";
            for (auto it : y) cout << it << " ";
            cout << "\n";
            return 0;
        } 
    }
    cout << "No";
    return 0;
}

---

六、小结

• 鸽笼原理是一种常用于证明 必然存在某种情况 的有力工具。
• 不局限于物体与抽屉的直观形式，也可泛化为分组、映射、分类等问题中。
• 常与反证法、组合数、数学归纳法联用，灵活性强、应用广泛。