前言^[1]

由于今天上课大部分是讲题，所以讲课的部分就少了。而抽屉原理本身也没什么好讲的。

目录：

• 前言
• 抽屉原理
• 例题

---

抽屉原理^[2]

抽屉原理（鸽巢原理）是指：有 $n+1$ 个物品，要放进 $n$ 个容器里，则至少有一个容器里有 $2$ 个物品。

证明： 可以使用反证法。假设每个容器只有 $1$ 个物品，则物品数只有 $n$ 个，与有 $n + 1$ 个物品矛盾。

推广

• 有 $n$ 个物品，要放进 $m$ 个容器里，则至少有一个容器里有 $\lceil \frac{n}{m} \rceil$ 个物品 。
• 将 $mn-1$ 个物品放入 $n$ 个容器中，则至少有一个物品不少于 $m-1$ 个。

---

例题^[3]

参考 BCOI 例题：https://www.bcoi.cn/p/CS305 。

第一题

题目描述

1.【CSP-J/2019】一副纸牌除掉大小王有 $52$ 张牌，四种花色，每种花色 $13$ 张。假设从这 $52$ 张牌中随机抽取 $13$ 张纸牌，则至少( )张牌的花色一致。

A. 4
B. 2
C. 3
D. 5

题目解析

可以先找到鸽子和笼子，就能转化为一半鸽巢问题，带入公式求解。

可以这样看：一副纸牌除掉大小王有 $52$ 张牌，四种花色，每种花色 $13$ 张。抽出了 $13$ 张牌要分配到 $4$ 中花色中，则至少( )张牌的花色一致。

这样就能找到鸽子数 $13$ 笼子数 $4$ 。带入公式：

$$\lceil\frac{n}{m}\rceil=\lceil\frac{13}{4}\rceil=5 $$

因此，答案为 $5$ 。

剩下不会了，太难了。。。

---

1. 前言 ↩︎

2. 抽屉原理 ↩︎

3. 例题 ↩︎