鸽巢原理

1 基本形式

把 n+1n+1 个对象放入 nn 个盒子,至少有一个盒子含有两个或更多对象。这就是鸽巢原理,也称抽屉原理。

证明只需反设每个盒子至多放一个对象,那么总数至多为 nn,与有 n+1n+1 个对象矛盾。

盒子不一定是实际容器,也可以是一种分类。例如 1313 个人按出生月份分为 1212 类,必有两个人的出生月份相同。

原理保证的是某个类别发生重复,不要求每个类别都非空。

2 一般形式

把 NN 个对象分入 MM 个类别,其中 M≥1M\ge1,则至少有一类包含:

⌈NM⌉ \left\lceil\frac NM\right\rceil

个对象。否则,每一类都少于这个数量,所有类别的总容量就不足 NN。

等价地,要保证某类至少有 kk 个对象,只需对象总数达到:

M(k−1)+1. M(k-1)+1.

如果只有 M(k−1)M(k-1) 个,可以恰好每类放 k−1k-1 个,因此这个界限不能再减少。

例如 1010 个对象分成 33 类,某类至少有 44 个。这里没有声称每类都至少有 44 个。

3 构造分类

应用时需要同时说明三件事:有哪些对象、最多有多少类、同类对象能推出什么结论。

仅有“对象多于类别”还不够,分类必须保留题目要求的关系。下面分别使用相邻数对、奇数部分和余数作为类别。

3.1 相邻数对

从 1∼2n1\sim2n 中任取 n+1n+1 个不同的数,证明其中必有两个数互质。

将所有数分成 nn 类:

{1,2},{3,4},…,{2n−1,2n}. \{1,2\},\{3,4\},\ldots,\{2n-1,2n\}.

选出的数超过类别数,必有一类中的两个数同时被选中。它们相邻,公因数必须整除两者之差 11,所以互质。

3.2 奇数部分

仍从 1∼2n1\sim2n 中任取 n+1n+1 个不同的数,证明其中必有一个数整除另一个数。

把每个正整数唯一写成:

x=2tq,q 为奇数. x=2^tq,\qquad q\text{ 为奇数}.

按奇数部分 qq 分类。qq 只能取 1,3,…,2n−11,3,\ldots,2n-1,共 nn 种,因此必有两个选中的数属于同一类。

设它们是 2aq,2bq2^aq,2^bq,不妨令 a<ba<b,则后者是前者的 2b−a2^{b-a} 倍,整除关系成立。

例如在 1∼61\sim6 中,可以这样分类:

奇数部分 类中的数
11 1,2,41,2,4
33 3,63,6
55 55

每类中的数相差若干次乘 22,因此同类的任意两个不同数都存在整除关系。分类依据来自需要证明的结论。

4 同余前缀

给定任意 nn 个整数 a1,…,ana_1,\ldots,a_n,证明存在一个非空连续区间,其元素和能被 nn 整除,并构造出这个区间。

要让区间和被 nn 整除,可以先把区间和写成两个前缀和之差:

P0=0,Pi=∑j=1iaj. P_0=0,\qquad P_i=\sum_{j=1}^i a_j.

若两个前缀满足 Pi≡Pj(modn)P_i\equiv P_j\pmod n,其中 i<ji<j,则:

Pj−Pi=∑k=i+1jak≡0(modn). P_j-P_i=\sum_{k=i+1}^{j}a_k\equiv0\pmod n.

现在对象是 P0,P1,…,PnP_0,P_1,\ldots,P_n,共 n+1n+1 个;按模 nn 的余数分类,只有 0∼n−10\sim n-1 共 nn 类。由鸽巢原理,必有两个不同位置的前缀同余,因此所求非空区间一定存在。

例如 n=5n=5,数组为 [2,4,1,3,6][2,4,1,3,6]:

六个前缀按五种余数分类,前缀位置 1、3 的余数同为 2,得到区间 2 到 3

前缀 P1=2P_1=2、P3=7P_3=7 的余数同为 22,所以区间 [2,3][2,3] 的和为 7−2=57-2=5,可被 55 整除。

4.1 代码实现

存在性证明已经给出了构造方法:扫描前缀余数,保存每个余数首次出现的位置。一旦某个余数再次出现,就能输出两次前缀位置之间的区间。

约定输入 1≤n≤2×1051\le n\le2\times10^5,随后输入 nn 个整数,∣ai∣≤109|a_i|\le10^9;输出任意一组满足条件的区间端点 l,rl,r,下标从 11 开始。

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

const int maxn = 200000 + 5;
int first[maxn];  // first[r]:余数 r 首次出现的前缀位置

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    fill(first, first + n, -1);
    first[0] = 0;  // 空前缀 P[0]=0 也必须参与分类

    int rem = 0;
    for (int i = 1; i <= n; ++i) {
        ll x;
        cin >> x;
        // 只维护前缀和的余数;统一到 0..n-1,兼容负数。
        rem = (rem + x % n + n) % n;
        if (first[rem] != -1) {
            cout << first[rem] + 1 << ' ' << i << '\n';
            return 0;  // 两个不同位置的同余前缀,给出非空区间
        }
        first[rem] = i;
    }
    return 0;
}

时间、空间均为 O(n)O(n)。代码只保存前缀和的余数,不需要保存全部前缀和或原数组。

两个边界影响正确性:

  • 必须加入空前缀 P0=0P_0=0,否则只剩 nn 个对象,不能直接保证它们在 nn 类中发生重复,也会漏掉从位置 11 开始的区间。
  • C++ 对负数取余可能得到负值,应统一到 0∼n−10\sim n-1,才能作为同一套类别与数组下标。

5 使用条件

鸽巢原理给出的是必然存在的关系。实现构造时,还需要保存同类对象的位置或代表,不能只统计每类的数量。

“每个盒子可以装多少个”必须与分类性质一致。例如上述连续段结论使用 n+1n+1 个前缀、模 nn 分类;若把模数改成 mm,只有在 n≥mn\ge m 时,才能用相同计数直接保证前缀余数重复。

这不表示 n<mn<m 时一定无解,只表示对象数量本身已经不足以保证有解。

6 相关题解

暂无相关题解