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

2 years ago
## 抽屉原理,鸽巢原理
### 一、鸽巢原理
别名:鸽笼原理。狄利克雷抽屉原理。
最简单的一种形式:有$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