## 抽屉原理,鸽巢原理 ### 一、鸽巢原理 别名：鸽笼原理。狄利克雷抽屉原理。 最简单的一种形式：有$m + 1$只鸽子，$m$个笼子，那么至少有一个笼子有至少两只鸽子。当然，换个角度来说：有$m − 1$只鸽子，$m$个笼子，那么至少有一个笼子是空的。 ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202311240947996.png) **初级加强**：有$m$个笼子，$k ∗ m + 1$只鸽子，那么至少有一个笼子有至少$k+1$只鸽子。 **高级加强**： 设$q_1,q_2,...,q_n$是正整数，如果有： $$S_2=q_1+q_2+...+q_n-n+1$$ 只鸽子需要放进$n$个笼子，那么或者第一个笼子至少有$q_1$只鸽子，或者第二个笼子至少有$q_2$只鸽子，...,或者第$q_n$个鸽笼至少有$q_n$只鸽子。 **反证法** 假设每个笼子里的鸽子数量都比题目要求的目标结果少一只： 即第 $i$ 个笼中最多有 $q_i−1$ 只鸽子，那么总共最多有： $$S_1=(q_1−1)+(q_2−1)+⋯+(q_n−1)=q_1+q_2+⋯+q_n−n$$ 此时发现$S_2=S_1+1$,也就是还有一只鸽子没有笼子，因此矛盾，所以假设错误，至少有一个笼子$i$,满足有$q_i$只鸽子。 ### 二、 简单应用 （1）从一副纸牌（排除大小王）中随机抽取 $5$ 张纸牌，则至少存在两张牌的花色一致。 >**注意**:此时的 **鸽** 与 **笼** 分别指什么？ **鸽**：$5$ 张纸牌的各自花色，**笼**：$4$种花色； （2）三个人分四块蛋糕，本着公平的原则，一定有一个人会分得 $2$ 块蛋糕； （3）五个蛋糕要放在两个盒子里，则存在一个盒子存放的蛋糕数量至少为$3$. $(5−1)2+1$（$5-1$：表示减去余出来的一个鸽子） ### 三、高级加强 任意给 $m$ 个整数$a_1,a_2,a_3,...,a_m$。 **求证**：必存在整数 $s,t(0≤s＜t≤m)$,使得 $m$ 整除 $a_{s+1}+a_{s+2}+…+a_t$。 > **解释**:就是在序列$a_1，a_2，……，a_m$中存在连续的$a_x$，使得这些$a$的和能够被$m$整除。 **证明**： 考虑$m$个和 $$\large a_1,a_1+a_2,a_1+a_2+a_3,……,a_1+a_2+a_3+...+a_m$$ 如果这些和当中的 **任意一个可被$m$整除**，那么结论就成立。 那如果没有任意一个可以被$m$整除呢？ 假设这些和中的每一个除以$m$都有一个非零余数，余数等于$1,2，……，m-1$ 中的一个数。因为有$m$个和，而只有$m-1$个余数，所以必然有两个和除以$m$有相同的余数。因此，存在整数 $s$和 $t$，$s **举栗子**：设$m=7$，且 > 整数为: $a[]=\{2,4,6,3,5,5,6\}$ > 前缀和: $s[]=\{2,6,12,15,20,25,31\}$ > 这些整数被$7$除时余数分别为 > $r[]=\{2,6,5,1,6,4,3\}$。有两个等于$6$的余数(位置是$2$和$5$)，这意味着结论： > 从$2+1=3$开始，到$5$结束，有$a[3]+a[4]+a[5]=6+3+5=14$ 可被$7$整除。 ### 四、鸽巢原理的应用 #### 1、练习题 一位洛谷$oier$要用$12$周的时间准备 $CTSC$,为了练习，他每天至少要刷一题，因为题目有难度，他每星期刷题无法超过$13$题。请你证明：存在连续的若干天期间，这位$oier$恰好刷了$11$题。 **证明**： 1.我们可以令$a_1$ 表示第一天所刷的题数，$a_2$ 表示前两天所刷的题数，$a_3$表示前三天所刷的题数.之后以此类推 2.而题目说，由于每天都要 **至少** 刷$1$题，所以数列 $$a_1=1$.又每周最多刷$13$题，故$a_{84}< = 13 ∗ 12 = 156$。 因此又有： $1 < = a_1 < a_2 < a_3 < . . . < a_{84} < = 156$ 同理， $a_1+11,a_2+11,a_3+11,...,a_{84} +11$同样是一个严格递增序列。范围： $1+11 < = a_1+11 < a_2+11 < a_3+11 < . . . < a_{84}+11 < = 156+11$ $12<=a_1+11 < a_2+11 < a_3+11 < . . . < a_{84}+11<=167$ 我们把两个序列合起来看： $a_1 ,a_2,a_3,...,a_{84},a_1+11,a_2+11,a_3+11,...,a_{84} +11$ 一共$168$个数。其中每一个数都是$1$到$167$之间的一个整数。 根据鸽巢原理可得，其中必有两个数相等！！！ 同时$a_1,a_2,a_3,...,,a_{84}$中必然无相等的两个数， 而$a_1+11,a_2+11,a_3+11,...,a_{84} +11$中也是一样没有相等的两个数，那么，必然存在一个$x$和$y$,使得 $$\large a_x=a_y+11$$ 从而得出结论：这个$oier$在第$y+1,y+2,y+3,...,x$天内一共刷了$11$道题。 #### 2、练习题 证明：在边长为$2$的等边三角形 **内部** 放上$5$个点。则至少存在两个点，他们之间的距离小于等于$1$. ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202311241310117.png) 我们先画出一个边长为$2$的等边三角形。 然后把三条边中点两两相连。就形成了这张图。 那么根据鸽巢原理，必然有两个点在一个边长为$1$的小三角形里。 而我们知道，边长为$1$的等边三角形里处处距离都小于等于$1$,于是问题就解决了 > $5$个鸽子，$4$个笼子。 #### 3、练习题 已知$n+1$个正整数，它们全都小于或等于$2n$，**证明当中一定有两个数是互质的**。 要证明这个问题，我们就要利用一个互质的特性：**两个相邻整数互质**。 有了这个突破口，于是我们可以构造$n$个鸽巢，每一个里依次放入 $1,2,3,4,...,2n$ 这$2n$个数中的两个数。 ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202311241316080.png) 也就是说，我们要在这其中取出$n + 1$个数。 根据鸽巢原理，无论如何，我们都会抽空一个鸽巢。 一个鸽巢中的两个数肯定互质，所以问题就解决了。 > **扒栗史**：匈牙利大数学家厄杜斯($PaulErdous$,$1913 - 1996$) 向当年年仅$11$岁的波萨($LouisPósa$)提出这个问题，而小波萨思考了不足半分钟便能给出正确的答案。 > **冷笑话**： > 山东高考$2017$年有$54$万人。而人的头发大约有$8−12$万根。那么必然有两人的头发数量相同。 #### 4、练习题 $NOIP$ 提高组 初赛 问题求解 习题集 $2010$ 第$3$题 记$T$为一队列，初始时为空，现有$n$个 **总和** 不超过$32$的正整数依次入列。如果无论这些数具体为何值，**都能找到一种出队的方式** ，使得存在某个时刻队列$T$中的数之和恰好为$9$，那么$n$的最小值是___________。 答案： $18$ **题解**： 题意有些难懂：是指在数字尽可能取小，$n$尽可能长的情况下，符合题意的最大$n$值。 位置 `1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17` 数值 `1 1 1 1 1 1 1 1 (10) 1 1 1 1 1 1 1 1` 前缀和`1 2 3 4 5 6 7 8 18 19 20 21 22 23 24 25 26` 位置$9$取值是$10$的原因是，**起刁难作用**，让数组元素前缀和尽量的达不到$9$. 又因为，总的前缀和是$32$,故位置$9$的 **最小取值** 是$10$. 位置$10$开始，都用尽可能小的正数，故$1$最理想。 可以设置数据到数组的第$17$位元素，此时还是无法打成某段前缀和是$9$. 和是$32$,前$17$位已经用去了$26$，还剩下$6$,故第$18$位可以获得的数据是$1,2,3,4,5,6$ 若第$18$位数值是$1$, 位置`10 11 12 13 14 15 16 17 18` 数值`1 1 1 1 1 1 1 1 1` 位置$10$到位置$18$可以构成和值为`1+1+1+1+1+1+1+1+1=9`. 若第$18$位数值是$2$, 位置`11 12 13 14 15 16 17 18` 数值`1 1 1 1 1 1 1 2` 位置$11$到位置$18$可以构成和值为`1+1+1+1+1+1+1+2=9`. 若第$18$位数值是$3$, 位置`12 13 14 15 16 17 18` 数值`1 1 1 1 1 1 3` 位置$11$到位置$18$可以构成和值为`1+1+1+1+1+1+3=9`. 若第$18$位数值是$4$, 位置`13 14 15 16 17 18` 数值`1 1 1 1 1 4` 位置$11$到位置$18$可以构成和值为`1+1+1+1+1+4=9`. 若第$18$位数值是$5$, 位置`14 15 16 17 18` 数值`1 1 1 1 5` 位置$11$到位置$18$可以构成和值为`1+1+1+1+5=9`. 若第$18$位数值是$6$, 位置`15 16 17 18` 数值`1 1 1 6` 位置$11$到位置$18$可以构成和值为`1+1+1+6=9`. 很明显，在极端条件下，符合题意的$n$值，是$18$. #### 5、练习题 从整数$1,2,...,200$中选出$101$个整数。 **求证**：在所选的这些整数之间存在两个这样的整数，其中的一个可被另一个整除。 首先要先知道这点：任一整数都可以写成的$2^k*a$形式，其中$k>=0\&\&a$是奇数。 对于$1$到$200$之间的一个整数，$a$是$100$个数$1,3,5，...，199$中的一个。因此，在所选的$101$个整数中存在两个整数，当写成上述形式时这两个数具有相同的$a$值。令这两个数是$2^r*a$和$2^s*a$，如果$r **扒栗史**：此定理由$Frank$ $Plumpton$ $Ramsey$（弗兰克·普伦普顿·拉姆齐，$1903−1930$）提出. 此定理有一个广为流传的例子：$6$ 个人中至少存在$3$人相互认识或者相互不认识。 **转换**：该定理等价于证明这$6$个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形 ![](https://dsideal.obs.cn-north-1.myhuaweicloud.com/HuangHai/BlogImages/202311241334465.png) ### 六、与编程结合的题目 **[$HDU$ $1808$ $Halloween$ $treats$](https://acm.hdu.edu.cn/showproblem.php?pid=1808)** **题目大意**： 给你两个整数$C$和$N$，再给你$N$个正数的序列，从中找到若干数，使得其和刚好是 $C$ 的倍数。输出这些数的序号。 我们知道$C<=N$的，故我们可以用鸽巢原理去做， **思路**： $Sum[i]$为序列中前 $i$ 项的和。则有两种可能： 1.若有 $Sum[i]$ 是 $C$ 的倍数，则直接输出前 $i$ 项。 2.如果没有任何的 $Sum[i]$ 是 $C$ 的倍数，则计算 $ri = Sum[i] \% C$。根据鸽巢原理，肯定有 $Sum[i] \% C == Sum[j] \% C，j using namespace std; const int N = 1e5 + 100; int sum[N], mod[N]; int main() { ios::sync_with_stdio(false); int c, n; while (cin >> c >> n, c + n) { memset(mod, -1, sizeof mod); memset(sum, 0, sizeof sum); mod[0] = 0; int s = 0, t = 0; for (int i = 1; i <= n; i++) { int x; cin >> x; sum[i] = (sum[i - 1] + x) % c; // 前缀和 %c if (sum[i] == 0) { t = i; continue; } if (mod[sum[i]] == -1) mod[sum[i]] = i; // 首次出现这个余数 else { // 多次出现此余数 s = mod[sum[i]]; // 开始位置 t = i; // 结束位置 } } for (int i = s + 1; i <= t; i++) cout << i << (i != t ? " " : "\n"); } } ``` **[$HDU$ $1205$ 吃糖果](http://acm.hdu.edu.cn/showproblem.php?pid=1205)** **方法**：隔板法求解 找出数量最多的一种糖果，把数量$n$看成$n$个隔板，隔成$n$个空间（隔板以右为一空间），其他糖果数量总和记为数值$s$。 （1）若$s=n-1​$，有解。 推导之后发现：当总数-最大值>=最大值-1时，就满足有解条件。 **注意事项**： （1）用数组存放时，数组要开大，$n<=1000000$，数组要$a[1000000]$； （2）把$t,n$等变量定义成`long long`类型（$int$类型的话为$WA$）。 ```cpp {.line-numbers} #include using namespace std; #define int long long const int N = 1000010; int a[N]; signed main() { int T; cin >> T; while (T--) { int n, sum, mx; cin >> n; sum = 0, mx = 0; for (int j = 0; j < n; j++) { cin >> a[j]; sum += a[j]; mx = mx < a[j] ? a[j] : mx; } if ((sum - mx) >= (mx - 1)) puts("Yes"); else puts("No"); } } ``` **[$HDU$ $5917$ $Instability$](http://acm.hdu.edu.cn/showproblem.php?pid=5917)** > 前导知识： > **[离散数学 --- 图论基础 --- 子图和补图，握手定理](https://blog.csdn.net/qq_51947882/article/details/126751352)** > **题意**：给出一个图，求稳定子图的个数。稳定子图定义为包含三元环子图或者三个点独立集子图的图。 **题解**： $Ramsey$定理的通俗表述： $6$ 个人中至少存在$3$人相互认识或者相互不认识。所以对于大于$6$的子集都是满足条件的，组合数算一下就好，对于小于$6$的子集，最多是$n$的5次方，直接暴力。 ```cpp {.line-numbers} #include using namespace std; #define int long long #define endl "\n" const int M = 1e2 + 7; const int P = 1e9 + 7; int T, n, m, cas = 1; int g[M][M]; int fac[M]; // 快速幂 int qmi(int a, int b) { int res = 1; a %= P; while (b) { if (b & 1) res = res * a % P; b >>= 1; a = a * a % P; } return res; } /* Q:什么是费马小定理? 答：费马小定理是一个关于模运算的定理，它陈述了如果p是一个质数，而a是任意整数且不是p的倍数， 那么a^(p-1) 与 1 (mod p) 同余。 Q:费马小定理是怎么求逆元的？ 答：当p是质数时，我们分离一项出来 a * a^(p−2) ≡ 1 (mod p) 对比逆元的方程式，可以很容易得到，a关于p的逆元就是 a^(p −2),而a^(p-2)可以用快速幂求得 Q:组合数公式C(n,m)=n!/(m!*(n-m)!) ，由于需要取模，同时存在除法，所以可以考虑是否可以用费马小定理求除法逆元？ 答：是可以的，原因：因为模mod=1e9+7是质数，并且，题目中的数据范围n<=50,是不可能是mod的倍数的，所以符合费马小定理 的要求，可以用费马小定理来求除法逆元。 */ int C(int n, int m) { /* fac[n]: n! qmi(fac[m], P - 2) : 费马小定理的结果 (m!)^(p-2),这样，把除m!取模 转化为乘 (m!)^(p-2)后取模 qmi(fac[n - m], P - 2) :同上 */ return fac[n] * qmi(fac[m], P - 2) % P * qmi(fac[n - m], P - 2) % P; } int judge3(int i, int j, int k) { // 判断三点之间满不满足不稳定点集 if (g[i][j] && g[i][k] && g[j][k]) return 1; // 三点之间相连 if (!g[i][j] && !g[i][k] && !g[j][k]) return 1; // 三点之间不互连 return 0; } int judge4(int i, int j, int k, int l) { if (judge3(i, j, k) || judge3(i, j, l) || judge3(j, k, l) || judge3(i, k, l)) return 1; // 表示4个点中有三个点为不稳定点集就行,为什么呢？ // 因为时题目要求的，不稳定点集为3个点。 return 0; } int judge5(int i, int j, int k, int l, int o) { // 表示5个点中有4个点满足就行 if (judge4(i, j, k, l) || judge4(i, j, k, o) || judge4(i, j, l, o) || judge4(j, k, l, o) || judge4(i, k, l, o)) return 1; return 0; } void solve() { cin >> n >> m; // n个顶点,m条边 memset(g, 0, sizeof g); // 初始化地图 while (m--) { int a, b; cin >> a >> b; g[a][b] = g[b][a] = 1; // 无向图 } int ans = 0; if (n >= 6) { ans = qmi(2, n); // ① 多项式定理C(n,0)+C(n,1)+...+C(n,n)=2^n // ② 也可以这样来思考，一个也不要，要1个，要2个，要3个，...,要n个 // C(n,k)(k>=6)表示，从n个中取k个出来，总存在一个不稳定点集的个数（三点之间互联或三点之间不连） for (int i = 0; i < 6; i++) /// 减去前5个 ans = (ans - C(n, i) + P) % P; } if (n >= 3) { // 枚举任意3个 for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) for (int k = j + 1; k <= n; k++) if (judge3(i, j, k)) ans = (ans + 1) % P; } if (n >= 4) { // 暴力取4个 for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) for (int k = j + 1; k <= n; k++) for (int l = k + 1; l <= n; l++) if (judge4(i, j, k, l)) ans = (ans + 1) % P; } if (n >= 5) { // 暴力取5个 for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++) for (int k = j + 1; k <= n; k++) for (int l = k + 1; l <= n; l++) for (int o = l + 1; o <= n; o++) if (judge5(i, j, k, l, o)) ans = (ans + 1) % P; } printf("Case #%lld: %lld\n", cas++, ans); } signed main() { // 加快读入 ios::sync_with_stdio(false), cin.tie(0); // 预处理阶乘数组（同步取模） fac[0] = 1, fac[1] = 1; for (int i = 2; i < M; i++) fac[i] = fac[i - 1] * i % P; cin >> T; while (T--) solve(); } ``` https://blog.csdn.net/LJD201724114126/article/details/84547302