- gf24118 的博客
GF2025C2抽屉原理(鸽巢原理)
- 2025-8-8 20:03:55 @
抽屉原理(鸽巢原理)!!
前言
已删除。
介绍:
抽屉原理用于证明存在性证明和求最坏情况下的解。
哎呀直接看最核心的部分吧:
理论:将 个物体,划分为 组,那么有 至少一组 有 两个(或以上) 的物体。
以下将个小拨鼠,让它们去宿舍共组。
看完以上实例你会发现,你无论怎么分小拨鼠,只要把个小拨鼠分成组,那么有至少一组必然有两个及以上的小拨鼠。设若为3,也就是把个小拨鼠分成组,哪怕每组个,最后一组必然只能分个。
理论就这么简单,没了。(别忘了这只是初步)
以下是进阶_推广
被你发现了...
编者注:“”是向上取整符号,如,
将 个土豆,划分为 组的马铃薯捆,那么至少存在一个组的马铃薯捆,含有大于或等于 个土豆。
推广的形式也可以使用 反证法 证明:若每个分组含有小于 个物体,则其总和 $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$ 矛盾。
此外,划分还可以弱化为覆盖结论不变。
给定集合 , 一个 的非空子集构成的簇
- 若满足 则称为 的一个覆盖(cover)
- 若一个覆盖还满足 则称为 的一个划分。
鸽巢原理可以有如下叙述: 对于 的一个覆盖 有至少一个集合 满足 $\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil$。