You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

463 lines
18 KiB

This file contains invisible Unicode characters!

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

## 抽屉原理,鸽巢原理
### 一、鸽巢原理
别名:鸽笼原理。狄利克雷抽屉原理。
最简单的一种形式:有$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_i1$ 只鸽子,那么总共最多有:
$$S_1=(q_11)+(q_21)+⋯+(q_n1)=q_1+q_2+⋯+q_nn$$
此时发现$S_2=S_1+1$,也就是还有一只鸽子没有笼子,因此矛盾,所以假设错误,至少有一个笼子$i$,满足有$q_i$只鸽子。
### 二、 简单应用
1从一副纸牌排除大小王中随机抽取 $5$ 张纸牌,则至少存在两张牌的花色一致。
>**注意**:此时的 **鸽** 与 **笼** 分别指什么?
**鸽**$5$ 张纸牌的各自花色,**笼**$4$种花色;
2三个人分四块蛋糕本着公平的原则一定有一个人会分得 $2$ 块蛋糕;
3五个蛋糕要放在两个盒子里则存在一个盒子存放的蛋糕数量至少为$3$.
$(51)2+1$$5-1$:表示减去余出来的一个鸽子)
### 三、高级加强
任意给 $m$ 个整数$a_1,a_2,a_3,...,a_m$。
**求证**:必存在整数 $s,t(0≤st≤m)$,使得 $m$ 整除 $a_{s+1}+a_{s+2}+…+a_t$。
> **解释**:就是在序列$a_1a_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<t$,使得$a_1+a_2+...+a_s$ $a_1+a_2+...+a_t$除以$m$有相同的余数$r$
$$
\large \left\{\begin{matrix}
a_1+a_2+...+a_s=b*m+r & \\
a_1+a_2+...+a_t=c*m+r &
\end{matrix}\right.
$$
二式相减,发现$a_{s+1}+a_{s+2}+……+a_t=(c-b)*m$,从而 $a_{s+1}+a_{s+2}+……+a_t$ 能够被$m$整除,证毕。
> **举栗子**:设$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<a_2<a_3<...<a_{84}$$
另有$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$万人。而人的头发大约有$812$万根。那么必然有两人的头发数量相同。
#### 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<s$,那么第二个数就能被第一个数整除。反之亦然。
注意,从$1,2...200$中可以选择$100$个数,使得其中没有一个能被另一个数整除(比如,这$100$个整数是$101,102...119,200$
### 五、$Ramsey$定理
> **扒栗史**:此定理由$Frank$ $Plumpton$ $Ramsey$(弗兰克·普伦普顿·拉姆齐,$19031930$)提出.
此定理有一个广为流传的例子:$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] \% Cj<i$。则第 $j +1$项到第 $i$ 项数的和即为 $C$ 的倍数。
这题说,要是没答案就输出 `no sweets` ,想想,这有可能吗?
```cpp {.line-numbers}
#include <bits/stdc++.h>
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$,把$s$个糖果放到隔板之间,$n$个隔板不够放,至少一个空间内没有糖果,因为两个隔板为同一种糖果,不符合题意,无解。
2若$s>=n-1$,有解。
推导之后发现:当总数-最大值>=最大值-1时就满足有解条件。
**注意事项**
1用数组存放时数组要开大$n<=1000000$,数组要$a[1000000]$
2把$t,n$等变量定义成`long long`类型($int$类型的话为$WA$)。
```cpp {.line-numbers}
#include <bits/stdc++.h>
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 <bits/stdc++.h>
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^(p2) ≡ 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