18 KiB
抽屉原理,鸽巢原理
一、鸽巢原理
别名：鸽笼原理。狄利克雷抽屉原理。
最简单的一种形式：有m + 1只鸽子，m个笼子，那么至少有一个笼子有至少两只鸽子。当然，换个角度来说：有m − 1只鸽子，m个笼子，那么至少有一个笼子是空的。
初级加强：有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<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.
我们先画出一个边长为2的等边三角形。
然后把三条边中点两两相连。就形成了这张图。
那么根据鸽巢原理，必然有两个点在一个边长为1的小三角形里。
而我们知道，边长为1的等边三角形里处处距离都小于等于1,于是问题就解决了
5个鸽子，4个笼子。
3、练习题
已知n+1个正整数，它们全都小于或等于2n，证明当中一定有两个数是互质的。
要证明这个问题，我们就要利用一个互质的特性：两个相邻整数互质。
有了这个突破口，于是我们可以构造n个鸽巢，每一个里依次放入
1,2,3,4,...,2n
这2n个数中的两个数。
也就是说，我们要在这其中取出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<s,那么第二个数就能被第一个数整除。反之亦然。
注意，从1,2，...，200中可以选择100个数，使得其中没有一个能被另一个数整除（比如，这100个整数是101,102，...，119,200）
五、Ramsey定理
扒栗史：此定理由
FrankPlumptonRamsey（弗兰克·普伦普顿·拉姆齐，1903−1930）提出.
此定理有一个广为流传的例子：6 个人中至少存在3人相互认识或者相互不认识。
转换：该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形
六、与编程结合的题目
题目大意：
给你两个整数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<i。则第 j +1项到第 i 项数的和即为 C 的倍数。
这题说，要是没答案就输出 no sweets ，想想，这有可能吗？
#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");
}
}
方法：隔板法求解
找出数量最多的一种糖果，把数量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）。
#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");
}
}
题意：给出一个图，求稳定子图的个数。稳定子图定义为包含三元环子图或者三个点独立集子图的图。
题解：
Ramsey定理的通俗表述： 6 个人中至少存在3人相互认识或者相互不认识。所以对于大于6的子集都是满足条件的，组合数算一下就好，对于小于6的子集，最多是n的5次方，直接暴力。
#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^(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