最后更新: 2025-01-10 07:43 查看: 71 次反馈刷题

古典模型5：抽屉原理

## 抽屉原理
桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

## 推广

将 $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$。

#### 典型例题
问：一副扑克牌有54张，至少抽取张扑克牌，方能使其中至少有两张牌有相同的点数。（大小鬼不相同)
解：建立抽屉：54张牌，根据点数特点可以分别看做15个抽屉，考虑最差情况：每个抽居都摸出了1张牌，共摸出15张牌，此时再任意摸出一张，无论放到哪个抽居，都会出现有两张牌在同一个抽居，即两张牌点数相同，$15+1=16 \text { (张) , }$ 答: 至少抽取16张扑克牌，方能使其中至少有两张牌有相同的点数。

其他版本
【高中数学】古典概率

开VIP会员

非会员每天6篇，会员每天16篇，VIP会员无限制访问

题库训练自我测评投稿

上一篇：古典模型4：生日问题

下一篇：古典模型6：错位排列

本文对您是否有用？有用 (0) 无用 (0)