跳转至

抽屜原理

定義

抽屜原理，亦稱鴿巢原理（the pigeonhole principle）。

它常被用於證明存在性證明和求最壞情況下的解。

簡單情況

將 \(n+1\) 個物體，劃分為 \(n\) 組，那麼有至少一組有兩個（或以上）的物體。

這個定理看起來比較顯然，證明方法考慮反證法：假如每個分組有至多 \(1\) 個物體，那麼最多有 \(1\times n\) 個物體，而實際上有 \(n+1\) 個物體，矛盾。

推廣

將 \(n\) 個物體，劃分為 \(k\) 組，那麼至少存在一個分組，含有大於或等於 \(\left \lceil \dfrac{n}{k} \right \rceil\) 個物品。

推廣的形式也可以使用反證法證明：若每個分組含有小於 \(\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\) 矛盾。

此外，劃分還可以弱化為覆蓋結論不變。
給定集合 \(S\), 一個 \(S\) 的非空子集構成的簇 \(\{A_1,A_2\ldots A_k\}\)

  • 若滿足 \(\bigcup_{i=1}^k A_i\) 則稱為 \(S\) 的一個覆蓋（cover）
  • 若一個覆蓋還滿足 \(i\neq j\to A_i\cap A_j=\varnothing\) 則稱為 \(S\) 的一個劃分。

鴿巢原理可以有如下敍述：對於 \(S\) 的一個覆蓋 \(\{A_1,A_2\ldots A_k\}\) 有至少一個集合 \(A_i\) 滿足 \(\left\vert A_i \right\vert \geq \left\lceil \dfrac{\left\vert S \right\vert}{k} \right\rceil\)。

參考文獻

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用