抽屉原理(鸽巢原理)!!


前言

已删除。


介绍:

抽屉原理用于证明存在性证明求最坏情况下的解。


哎呀直接看最核心的部分吧:

理论:将 n+1n+1 个物体,划分为 nn 组,那么有 至少一组两个(或以上) 的物体。

以下将44小拨鼠,让它们去宿舍共33组。

看完以上实例你会发现,你无论怎么分小拨鼠,只要把n+1n+1个小拨鼠分成nn组,那么有至少一组必然有两个及以上的小拨鼠。设若nn为3,也就是把44个小拨鼠分成33组,哪怕每组11个,最后一组必然只能分22个。


理论就这么简单,没了。(别忘了这只是初步)


以下是进阶_推广

被你发现了...

编者注:“\left \lceil \right \rceil ”是向上取整符号,如4.1=5\left \lceil 4.1 \right \rceil =5 ,114513.998=114514\left \lceil 114513.998 \right \rceil =114514

nn 个土豆,划分为 k k 组的马铃薯捆,那么至少存在一个组的马铃薯捆,含有大于或等于 nk\left \lceil \dfrac{n}{k} \right \rceil 个土豆。

推广的形式也可以使用 反证法 证明:若每个分组含有小于 nk\left \lceil \dfrac{n}{k} \right \rceil 个物体,则其总和 $S\leq (\left \lceil \dfrac{n}{k} \right \rceil -1 ) \times k=k\left\lceil \dfrac{n}{k} \right\rceil-k < k(\dfrac{n}{k}+1)-k=n$ 矛盾。

此外,划分还可以弱化为覆盖结论不变。

给定集合 SS, 一个 SS 的非空子集构成的簇 {A1,A2Ak}\{A_1,A_2\ldots A_k\}

  • 若满足 i=1kAi\bigcup_{i=1}^k A_i 则称为 SS 的一个覆盖(cover)
  • 若一个覆盖还满足 ijAiAj=i\neq j\to A_i\cap A_j=\varnothing 则称为 SS 的一个划分。

鸽巢原理可以有如下叙述: 对于 SS 的一个覆盖 {A1,A2Ak}\{A_1,A_2\ldots A_k\} 有至少一个集合 AiA_i 满足 $\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil$。