鸽巢原理及应用

鸽巢原理及应用

​ 就简单的概述一下了

简单形式

​ 现有 $n+1$ 个物品，要将他们放入 $n$ 个盒子里，那么必定有 $1$ 个盒子内至少有 $2$ 个物品。

​ 显然，我们考虑每个盒子里都只能放置 $1$ 个物品，那么会有 $1$ 个物品剩余，所以易证。

应用：中国剩余定理

​ 现有两个正整数 $n,m$ 使得 $\gcd(n,m)=1$，即两数互质。那么试证明：存在正整数 $x$ 使得 $x$ 除以 $n$ 的余数为 $a$，且 $x$ 除以 $m$ 的余数为 $b$，其中 $a\in[0,n-1]$ 且 $b\in[0,m-1]$。

​ 那么易知，现有 $m$ 个数满足性质使得 $x$ 除以 $n$ 的余数为 $a$：$a,n+a,\cdots,(m-1)n+a$。

​ 此时我们观察这 $m$ 个数是否满足性质使得 $x$ 除以 $m$ 的余数为 $b$，显然发现对于除以 $m$ 后的余数仅属于 $[0,m-1]$ 中，如果每个余数都出现过恰好一次，则结论显然成立。

​ 那么我们假设存在两个数除以 $m$ 的余数相同为 $r$：$i\cdot n+a=p\cdot m+r,j\cdot n+a=q\cdot m+r$，其中 $0\le i<j\le m-1$，将两式联立相减则得：

$(j-i)\cdot n=(q-p)\cdot m$

​ 由于 $\gcd(n,m)=1$，所以 $m$ 为 $j-i$ 的因子，且 $0<j-i\le m-1$，显然不成立，易证。

加强形式

​ 令 $q_1,q_2,\cdots,q_n$ 均为正整数，则将 $(\sum_{k=1}^{n}q_k)-n+1$ 个物品放入 $n$ 个盒子中，那么对于编号为 $i$ 的盒子至少存在一个满足其中的物品数大于 $q_i$。

​ 显然，我们考虑将编号为 $i$ 的盒子里放入 $q_i-1$ 个数，那么会有 $1$ 个物品剩余，所以易证。

应用：一个稍难例子

​ 现有一个长度为 ${n}^{2}+1$ 的序列，试证明其中含有长度为 $n+1$ 的不上升子序列或者不下降子序列。

​ 对于序列 $a_1,a_2,\cdots,a_{n^2+1}$，我们现定义 $f_i$ 为以 $a_i$ 为起点的最长不下降子序列的长度。那么对于 $f_1,f_2,\cdots,f_{n^2+1}$ 的值都必然在 $[1,n]$ 的范围中，带入加强形式的鸽巢原理，显然至少存在 $n+1$ 个数值相等。

​ 故令 $f_{k_1}=f_{k_2}=\cdots=f_{k_n+1}$，此时假若对于任意的 $i\in[1,n]$，如果满足存在一对 $a_{k_i}\le a_{k_{i+1} }$，那么我们可以由 $a_{k_i}$ 和构成 $f_{ k_{i+1} }$ 本身的长度为 $n$ 的序列一起构成长度为 $n+1$ 的不下降子序列。如果不存在任意一对满足，那么意味着对于所有的 $i\in[1,n]$，都有 $a_{k_i}>a_{ {k_i+1} }$。那么 $a_{k_1},a_{k_2},\cdots,a_{k_{n+1} }$ 本身求能够构成一个长度为 $n+1$ 的不上升子序列，所以易证。