鸽巢原理 - NOI提高级教程

📖 离散组合基础：鸽巢原理 (又称抽屉原理)

鸽巢原理 (Pigeonhole Principle) 是组合数学中最简单但也是最强大的定理之一。它常常用于证明某种必然性（如必存在两个数相同、必存在某种染色等）。

📐 基础公式与定理陈述

第一抽屉原理：若把 $N$ 个物体放入 $K$ 个抽屉中，且 $N > K$：

$\text{必然存在至少一个抽屉里含有} \ge 2 \text{ 个物体}$

第二抽屉原理 (加强版)：若把 $N$ 个物体放入 $K$ 个抽屉中，则：

$\text{必然存在至少一个抽屉里含有} \ge \left\lceil \frac{N}{K} \right\rceil \text{ 个物体}$

其中 $\lceil x \rceil$ 代表向上取整。例如将 8 只鸽子放入 3 个巢，必然有一个巢含有 $\lceil 8/3 \rceil = 3$ 只或更多鸽子。

鸽子数 N (物件): 8

鸽巢数 K (抽屉): 3

调节上方滑块设置鸽子数 $N$ 与鸽巢数 $K$。点击“放飞鸽子”开始投掷动画。

鸽子总数 N 8

鸽巢总数 K 3

理论极限 ⌈N / K⌉ 3

实际最大落点数 -

🐦 鸽巢放置模型 (Pigeonholes Collision Arena)

// 鸽巢原理应用：检验数组中是否存在重复数字
// 给定一个长度为 N 的数组，元素值都在 [1, N-1] 范围内
bool hasDuplicate(int arr[], int n) {
    // 抽屉数为 N-1，物体数为 N
    // 根据鸽巢原理，必然存在至少一个数字重复
    vector<int> freq(n, 0);
    for (int i = 0; i < n; i++) {
        freq[arr[i]]++;
        if (freq[arr[i]] >= 2) {
            return true; // 碰撞成功，发现重复
        }
    }
    return false;
}

📋 投递分配步骤