bitworld 的博客
【数论】鸽巢原理
bitworld 最强壮的男人 SU @ 2025-4-26 10:01:38

鸽巢原理

鸽巢原理，亦称抽屉原理，是一种简单却强大的数学工具，广泛应用于组合数学、概率论、算法设计等领域。其核心思想是：若将n+1个物体放入n个抽屉中，则至少有一个抽屉包含两个或更多的物体。该原理被广泛用于证明问题的存在性，分析最坏情况下的解，或解决复杂的组合问题。

鸽巢原理的定义

鸽巢原理的基本表述为：如果将n+1个物体放入n个抽屉中，那么至少有一个抽屉里含有两个或更多的物体。其形式化的数学表述是：

将n+1个物体划分为n组，至少有一组包含两个或更多的物体。

证明方法

这个定理的证明可以通过反证法实现：

假设每个抽屉最多只有一个物体，那么最多可以有n个物体。
然而，我们实际有n+1个物体，显然与假设矛盾，因此至少有一个抽屉包含两个或更多的物体。

推广

鸽巢原理也可以推广到更多的分组情况。具体地，如果将n个物体划分为k个组，那么至少有一个分组包含不小于⌈n/k⌉个物品。这一推广也可通过反证法证明。

证明过程

若每个分组包含小于⌈n/k⌉个物品，则对于总和S有：

$ S \leq ( \left\lceil \frac{n}{k} \right\rceil - 1 ) \times k = k \left\lceil \frac{n}{k} \right\rceil - k < k\left(\frac{n}{k}+1\right) - k = n $

因此，假设不成立，必须有一个分组包含至少⌈n/k⌉个物品。

现象解释

鸽巢原理可以解释多个有趣的现象：

头发数量相同的两人： 在世界上，肯定有两个人的头发数量相同，因为人类的头发数量最多约为12万，而全球人口已超过80亿。
生日相同的人： 在1500人中，至少有5个人的生日相同，因为 $\left\lceil \frac{1500}{366} \right\rceil = 5$ 。
握手次数相同： 在n个人中，必定有两个人握手次数相同。这是因为，若每个人的握手次数介于0到n-1之间，必然有重复。

相关例题

例题1：hdu1205 吃糖果

问题描述：给定多种糖果，每种糖果的数量有限，且每个人不喜欢连续两次吃相同种类的糖果。问是否存在可行的吃糖方案。

解题思路

利用鸽巢原理来解决，找出最多的一种糖果，按“隔板法”将其数量设为隔板数，其他糖果依次填入这些隔板中。若满足条件，则有解。

具体解法：

设糖果数量最大的糖果的数量为N，其他糖果的总数量为S。
如果S ≥ N - 1，则可行；否则不可行。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);             
    cout.tie(0);            
    
    int T;
    cin >> T;  

    while (T--) {
        int K;
        LL S = 0, N = 0, x;
        
        cin >> K;
        // 遍历输入的每个数，更新总和和最大值
        for (int i = 0; i < K; i++) {
            cin >> x;
            N = max(N, x);  // 更新最大值
            S += x;          // 累加总和
        }

        // 判断总和是否大于或等于最大值-1
        cout << (S - N >= N - 1 ? "Yes" : "No") << '\n';
    }

    return 0;
}

CF1774B Coloring

题目描述

Cirno_9baka 的纸条上有 $n$ 个格子，他觉得空白的纸条看着有点无趣，于是想在纸条的格子上涂上 $m$ 种颜色。同时，他认为第 $i$ 种颜色必须要用 $a_i$ 次，且每连续 $k$ 个格子里涂的颜色必须互不相同。

Cirno_9baka 想知道有没有这样的一种涂色方案能符合他的要求。

输入格式

第一行，一个整数 $t$ ( $1 \leq t \leq 10\,000$ ) 表示测试用例的个数。

对于每组测试用例：

第一行，输入三个整数 $n$ , $m$ , $k$ ( $1 \leq k \leq n \leq 10^9$ , $1 \leq m \leq 10^5$ , $m \leq n$ ) $\\$

第二行， $m$ 个整数 $a_1,a_2,\cdots,a_m$ ( $1\leq a_i\leq n$ ) 并且保证 $a_1 + a_2 + \ldots + a_m = n$

保证每组测试用例中的 $m$ 的和不超过 $10^5$ 。

输出格式

对于每组测试用例，如果有至少一种涂色的方案，输出"YES"；否则输出"NO"。

输出不区分大小写。

输入输出样例 #1

输入 #1

2
12 6 2
1 1 1 1 1 7
12 6 2
2 2 2 2 2 2

输出 #1

NO
YES

说明/提示

第一个测试用例中，没有任何涂色的方案满足所有要求。

第二个测试用例中，可以将纸条涂成 $(1,2,1,2,3,4,3,4,5,6,5,6)$ ，对于每两个连续的格子，颜色都是互不相同的。

参考代码

#include<bits/stdc++.h>
using namespace std;

int a[100001];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t, n, m, k;
    cin >> t;  // 读取测试用例数
    while(t--){  // 对每个测试用例进行处理
        cin >> n >> m >> k;  // 读取n, m, k
        int c = ceil(n*1.0/k);  // 计算每组最大人数
        int cnt = 0;  // 记录人数等于c的情况
        bool flag = true;  // 标记是否所有输入符合要求
        
        // 读取每个房间的人数并进行判断
        for(int i = 1; i <= m; i++){
            cin >> a[i];
            if(a[i] > c){  // 如果某个房间人数超过最大人数
                flag = false;
            }
            if(a[i] == c){  // 如果某个房间人数等于最大人数
                cnt++;
            }
        }
        
        // 判断是否符合条件并输出结果
        if(!flag){
            cout << "NO" << endl;
        }else if(cnt > (n-1)%k + 1){
            cout << "NO" << endl;
        }else{
            cout << "YES" << endl;
        }
    }
    return 0;
}

思路

首先，题目要求每种颜色的使用次数为 $a_i$ （ $1 \leq i \leq m$ ），并且每连续 $k$ 个格子涂的颜色不得相同。我们可以通过将颜色的分配视为将 $a_i$ 个颜色“放入”相应的格子中，利用抽屉原理来推导解决方案。

根据抽屉原理，若存在某个 $a_i$ （ $1 \leq i \leq m$ ）使得 $a_i > c$ （其中 $c$ 为段数，即 $c = \frac{n}{k}$ ），则根据抽屉原理，至少有一个段的颜色数量 $\geq 2$ ，这显然不符合题目的要求。

此外，如果存在 $x$ 个 $a_i$ 满足 $a_i = c$ ，并设最后一段有 $y$ 个格子。如果 $x > y$ ，则根据抽屉原理，也会导致至少有一个段的颜色数量 $\geq 2$ ，同样不符合要求。

排除了这两种不可行的情况后，其余情况即为可行方案。

【数论】鸽巢原理