抽屉原理
XyzL
·
·
个人记录
抽屉原理
敬请往下浏览！
原理：
第一抽屉原理：
原理1: 把多于 n+1 个的物体放到 n 个抽屉里，则至少有一个抽屉里的东西不少于两件。
证明(反证法):如果每个抽屉至多只能放进一个物体，那么物体的总数至多是 n×1，而不是题设的 n+k(k≥1) ，故不可能。
原理2 : 把多于mn(m \times n)+1 (n!=0) 个的物体放到 n 个抽屉里，则至少有一个抽屉里有不少于 (m+1) 的物体。
证明(反证法):若每个抽屉至多放进 m 个物体,那么 n 个抽屉至多放进 mn 个物体,与题设不符，故不可能。
原理3 : 把无穷多件物体放入 n 个抽屉，则至少有一个抽屉里 有无穷个物体。
原理1 、2 、3都是第一抽屉原理的表述。
第二抽屉原理：
把 (mn-1) 个物体放入 n 个抽屉中，其中必有一个抽屉中至多有 (m-1) 个物体
运用：
构造抽屉的方法：
运用抽屉原理的核心是分析清楚问题中，哪个是物件（元素），哪个是抽屉。
形如：任意写一个数字 1,2,3 组成的 30 位数，从这 30 位数中任意截取相邻的三位，求证在各个不同的位置上所截得的三位数至少有两个相等。
证明：由题可知，共截取 28 个三位数=> 28 个元素，而三位数所构成的情况为 3^3=27 ，视为 27 个抽屉。根据抽屉原理必有两数相同。
最差原则：
什么是最差原则？
所谓最差原则（又称“最不利原则”），就是考虑问题发生的最差情况，然后就最差情况进行分析。最差原则是极端法的一种应用，一般情况下，我们优先考虑用最差原则来解决抽屉问题。
形如1：有 300 人去雅礼中学考试，AKIOI 的有 150 人，AKIMO 的有 80 人，AKIPhO 的 70 人，吊打集训队的有 50 人。求至少录取多少学生才能保证特长 70 人的特长相同。
解析1：此时我们考虑的最差情况为:AKIOI、AKIMO 和 AKIPhO 各录取 69 人，吊打集训队的 50 人全部录取，则此时再录取 1 人就能保证有 70 人找到的特长生相同。
推导1： 根据第二抽屉原理， mn+1 个人的时候必有 m+1 个人找到的特长相同，所以是要求出 mn+1 的人数，现在已知n=4,m+1=70。考虑到吊打集训队只有50人，得出 mn+1=(69*3+50)+1=258人。
形如2： lrj124 去参加IOI考试，出发的时候，发现自己价值 10 亿 美元的自行车，被人多上了10 把锁（他自己本来车子上就有一把），地上有 10 把与锁配对的钥匙。请问，可怜的 lrj124 最多要试才能将车子解开去AKIOI？
解析2：此时我们考虑的最差情况为:在 10 把锁中，第n把锁最差的情况要试（11 - n）次，还有第 11 把锁则是 lrj124 自己的，要试一次。所以一共要试1->10锁最多次数的总和 +1。所以 lrj124 要用 10+9+8+7+6+5+4+3+2+1+1=56次 才能将车子解开去AKIOI。
推导2： 条件十分清晰，这是一道经典的小奥题。我们只要根据最差原则来推出次数，再依次相加即可得出。
表现形式：
把它推广到一般情形有以下几种表现形式。
形式1: 设把 n+1 个元素划分至 n 个集合中 (A1，A2，…，An) ，用 a1，a2，…，an 分别表示这 n 个集合对应包含的元素个数，则:至少存在某个集合 Ai ，其包含元素个数值 ai≥2 。
证明1:(反证法)假设结论不成立，即对每一个 ai 都有 ai<2 ，则因为 ai 是整数，应有 ai≤1 ，于是有: a1+a2+…+an≤1+1+…+1=n<n+1，这与题设矛盾。
所以，至少有一个 ai≥2 ，即必有一个集合中含有两个或两个以上的元素。
形式2: 设把 nm+1 个元素划分至 n 个集合中 (A1，A2，…，An) ，用 a1，a2，…，an 表示这n个集合对应包含的元素个数，则:至少存在某个集合 Ai ，其包含元素个数值 ai 大于或等于 m+1 。
证明2:(反证法)假设结论不成立，即对每一个 ai 都有 ai<m+1 ，则因为 ai 是整数，应有 ai≤m ，于是有: a1+a2+…+an≤m+m+…+m=nm<nm+1 ，这与题设相矛盾。
所以，至少有存在一个 ai≥m+1 。
知识扩展--高斯函数 [x] 定义:对任意的实数 x ，[x]表示"不大于 x 的最大整数"。例如: [3.5]=3 ，[2.9]=2，[-2.5]=-3，[7]=7，……一般地，我们有:[x]≤x<[x]+1 。
形式3: 设把 n 个元素分为k个集合 A_1，A_2，…，A_k ，用 a_1,a_2…，a_k 表示这k个集合里相应的元素个数，需要证明至少存在某个 a_i 大于或等于 [n/k] 。
证明3:(用反证法)假设结论不成立，即对每一个 a_i 都有 a_i<[n/k] ，于是有: a_1+a_2+…+a_k<[n/k]+[n/k]+…+[n/k] =k?[n/k]≤k?(n/k)=n
**形式4:** 设把 $q_1+q_2+…+q_n-n+1$ 个元素分为 $n$ 个集合 $A_1$，$A_2$，…，$A_n$，用 $a_1$，$a_2$，…，$a_n$表示这n个集合里相应的元素个数，需要证明至少存在某个 $i$ ，使得 $a_i$ 大于或等于 $q_i$ 。
**证明4:**(用反证法)假设结论不成立，即对每一个 $a_i$ 都有 $a_i<q_i$ ，因为 $a_i$ 为整数，应有 $a_i≤q_i-1$ ，于是有: $a_1+a_2+…+a_n≤q_1+q_2+…+q_n-n <q_1+_q2+…+q_n-n+1$ 这与题设矛盾。
所以，假设不成立，故必有一个i,在第i个集合中元素个数 $a_i≥q_i$ 。
**形式5:** 证明:(用反证法)将无穷多个元素分为有限个集合，假设这有限个集合中的元素的个数都是有限个，则有限个有限数相加，所得的数必是有限数，这就与题设产生矛盾，所以，假设不成立，故必有一个集合含有无穷多个元素。(借由康托的无穷基数可将鸽巢原理推广到无穷集中。)
------------
## 例题1：
**已知 $n + 1$ 个正整数，它们全都小于或等于 $2n$ ，证明当中一定有两个数是互质的。**
匈牙利大数学家厄杜斯(PaulErdous,1913 - 1996) 向当年年仅 $11$ 岁的波萨 (LouisPósa) （年少有为...）提出这个问题，而小波萨思考了不足半分钟便能给出正确的答案。
波萨是这样考虑问题:取 $n$ 个盒子，在第一个盒子我们放 $1$ 和 $2$ ，在第二个盒子我们放 $3$ 和 $4$ ，第三个盒子是放 $5$ 和 $6$ ，依此类推直到第 $n$ 个盒子放 $2n-1$ 和 $2n$ 这两个数。
如果我们在 $n$ 个盒子里随意抽出 $n+1$ 个数。我们马上看到一定有一个盒子是被抽空的。因此在这 $n+1$ 个数中必有两个数是连续数，很明显的连续数是互质的。因此这问题就解决了! 这就是利用了抽屉原理的核心思想。
------------
## 例题2：
** Ramsey定理 （又称广义抽屉原理） **
狭义解释1：任意六个人中要么至少三个人认识，要么至少三个不认识。
狭义解释2：设空间内任意三个点不共面，若将其中的任意两个点的连线染成红色或蓝色，则必存在三边颜色相同的三角形。
狭义证明1：如狭义解释1，首先，把这 $6$ 个人设为 $A$、$B$、$C$、$D$、$E$、$F$ 六个点。由 $A$ 点可以引出$AB$、$AC$、$AD$、$AE$、$AF$五条线段。设:如果两个人认识，则设这两个人组成的线段为红色;如果两个人不认识，则设这两个人组成的线段为蓝色。由抽屉原则可知:这五条线段中至少有三条是同色的。不妨设$AB$、$AC$、$AD$为红色。若$BC$或$CD$为红色，则结论显然成立。若$BC$和$CD$均为蓝色，则若$BD$为红色，则一定有三个人相互认识;若$BD$为蓝色，则一定有三个人互相不认识。
------------
## 例题3：
**$17$个科学家中,每个科学家都和其他科学家通信，他们之间讨论$3$个题目，且任意两个科学家之间只讨论$1$个题目，证明其中至少有$3$名科学家，他们互相通信中讨论的是同一题目。**
**思路：**视$17$个科学家为$17$个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第$2$个问题则在相应两点连条黄线，若讨论第$3$个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。
**证明：** 考虑科学家$A$，他要与另外的$16$位科学家每人通信讨论一个问题，相应于从$A$出发引出$16$条线段，将它们染成$3$种颜色，而$16=3×5+1$，因而必有$6=5+1$条同色，不妨记为$AB1，AB2，AB3，AB4，AB5，AB6$同红色，若$Bi$($i=1$，$2$，…，$6$)之间有红线，则出现红色三角线，命题已成立；否则$B1$，$B2$，$B3$，$B4$，$B5$，$B6$之间的连线只染有黄蓝两色。考虑从$B1$引出的$5$条线，$B1B2$，$B1B3$，$B1B4$，$B1B5$，$B1B6$，用两种颜色染色，因为$5=2×2+1$，故必有$3=2+1$条线段同色，假设为黄色，并记它们为$B1B2$，$B1B3$，$B1B4$。这时若$B2$，$B3$，$B4$之间有黄线，则有黄色三角形，命题也成立，若$B2$，$B3$，$B4$，之间无黄线，则 $△B2，B3，B4$，必为蓝色三角形，命题仍然成立。
------------
## 例题4：
**以（$x,y,z$）表示有序三元数组，其中$x,y,z$为整数，试证：在任意七个三元整数组中，至少有两个三元数组，它们的$x,y,z$元中都是奇数或都是偶数。**（
**思路1：** 此类题我们可以“逐个击破”，一步步的证明。如先考虑$x$的情况，再考虑$y$，最后是$z$。（注意$x,y,z$顺序）
**证明1：**（$0$为偶数，$1$为奇数）
如($x1,y1,z1$)$010$ ——同奇偶
和($x2,y2,z2$)$101$ ——不符合
故我们先考虑x，根据第二抽屉原理，至少有$4$个$x$同奇偶，在这里我们就设为偶（$0$）。如：
$A1$（$0,y1,z1$）
$A2$（$0,y2,z2$）
$A3$（$0,y3,z3$）
$A4$（$0,y4,z4$）
我们再来考虑y，根据第二抽屉原理，至少有$2$个$y$同奇偶，若为偶，则满足条件，则我们让$y$为奇。（至少有$3$个奇数）则：
$A1$（$0,1,z1$）
$A2$（$0,1,z2$）
$A3$（$0,1,z3$）
最后来考虑$z$，根据第二抽屉原理，至少有$2$个$z$同奇偶，此时若为奇或偶都成立。
$A1$（$0,1,0$）或（$0,1,1$）
$A2$（$0,1,0$）或（$0,1,1$）
$A3$（$0,1,1$）或（$0,1,0$）都成立
**思路2：** 此类题我们还可以“整体考虑”，将所有的可能性算出来，再去证明。
**证明2：**我们可以显而易见地想出($x,y,z$)共有$8$种奇偶排列方式。
$A1$（$1,1,1$） $A2$（$1,1,0$）
$A3$（$1,0,0$） $A4$（$0,0,0$）
$A5$（$1,0,1$） $A6$（$0,1,0$）
$A7$（$0,0,1$） $A8$（$0,1,1$）
若同时选择了两次相同的奇偶形式，命题成立。（如$A1，A1$成立）
同理，得证！
------------
## 小试牛刀：
### CF1305C Kuroni and Impossible Calculation
#### 题意：
给定 $a1,a2,...,an$ 和 $m$（$1≤m≤1000$）,求
$\prod_{1\le i<j\le n}\left|a_i-a_j\right|\%m$。
#### 思路：
读题可知，当 $n<m$ 时，必有两项 $ai,aj$ 模 $m$ 同余，由此可知，$Ans=0$，否则暴力跑一遍 $O(nm)$ .
#### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline long long read() {
long long x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while (c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 2e5 + 5;
int n, m;
long long ans = 1, a[Maxn];
int main() {
n = read(), m = read();
if(n > m) {
puts("0");
return 0;
}
for(register int i = 1; i <= n; ++i) {
a[i] = read();
}
for(register int i = 1; i <= n; ++i) {
for(register int j = i + 1; j <= n; ++j) {
ans = ans * abs(a[i] - a[j]) % m;
}
}
printf("%lld\n", ans);
return 0;
}
```
------------
### POJ2356 Find a multiple
#### 题意：
给你长为 $n$ 的一个序列，要求在序列中找到连续的一些数，使他们的和是 $n$ 的倍数，输出抽多少个，并分别输出他们。
#### 思路：
若使用前缀和暴力枚举子串，时间复杂度为 $O(n ^ 2)$ ，会超时。
令每一个前缀和对 $n$ 的模数设为 $x$ ，若 $i = k$ 的时候 $x = 0$ 那意味着 $1$ 到 $i$ 是一个符合的序列。
若 $n$ 个前缀和的模数都在 $1$ 和 $n - 1$ 之间，根据抽屉原理，定有两个模数相同，设其下标分别为 $l$ 和 $r$， $sum[l]$ 或 $sum[r]$ $% n = x$, 那么 $sum[l] - sum[r]$ 这一部分的和 $% n$ 等于零,故我们只要找到 $l$ 和 $r$ 并输出 $l + 1$ 到 $r$ 序列即可。
#### 代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline long long read() {
long long x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if(c == '-') {
f = -1;
}
c = getchar();
}
while (c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
}
return x * f;
}
const int Maxn = 2e4 + 4;
int n, vis[Maxn];
long long a[Maxn], sum[Maxn], num[Maxn];
int main() {
while(cin >> n) {
Mem(vis, 0);
for(register int i = 1; i <= n; ++i) {
a[i] = read();
sum[i] = sum[i - 1] + a[i];
num[i] = sum[i] % n;
}
int l = 1, r = 0;
for(register int i = 1; i <= n; ++i) {
if(num[i] == 0) {
l = 1, r = i;
break;
}
if(vis[num[i]] == 0){
vis[num[i]] = i;
} else {
l = vis[num[i]] + 1, r = i;
break;
}
}
printf("%d\n", r - l + 1);
for(register int i = l; i <= r; ++i) {
printf("%lld\n", a[i]);
}
}
return 0;
}
```
------------