抽屉原理

🧠 逻辑推理与抽屉原理·
⭐⭐⭐

🎯 学习目标

  • 理解抽屉原理的基本思想和应用场景
  • 能用抽屉原理解释和解决简单的实际问题
  • 掌握将实际问题转化为‘物品’与‘抽屉’模型的方法

📚 核心概念

抽屉原理,也叫鸽巢原理,是一种非常直观但强大的逻辑推理工具。它的基本思想是:如果把多于 nn 个的物品放进 nn 个抽屉里,那么至少有一个抽屉里会放有至少两个物品

更一般地,抽屉原理可以表述为:

如果把 mm 个物品放入 nn 个抽屉中,且 m>nm > n,那么至少有一个抽屉中包含不少于 mn\left\lceil \frac{m}{n} \right\rceil 个物品。

其中,x\left\lceil x \right\rceil 表示不小于 xx 的最小整数(向上取整)。

举个例子:如果有5只鸽子飞进4个鸽笼,那么至少有一个鸽笼里有2只或更多的鸽子。因为 5>45 > 4,所以不能每个笼子最多只有1只。

抽屉原理的关键在于构造合适的“抽屉”。在解题时,我们要把问题中的对象看作“物品”,把分类标准或可能的情况看作“抽屉”。只要物品数量超过抽屉数量,就一定能得出某种“重复”或“集中”的结论。

📝 关键公式

  • 基本形式:若 m>nm > n,将 mm 个物品放入 nn 个抽屉,则至少有一个抽屉含 ≥2 个物品。
    示例:6本书放进5个书包,至少一个书包有2本以上。

  • 推广形式:将 mm 个物品放入 nn 个抽屉,则至少有一个抽屉含 ≥ mn\left\lceil \frac{m}{n} \right\rceil 个物品。
    示例:13个苹果分给4个小朋友,134=3.25=4\left\lceil \frac{13}{4} \right\rceil = \left\lceil 3.25 \right\rceil = 4,所以至少一人分到4个或更多苹果。

💡 经典例题

例题1(基础):一个袋子里有红、黄、蓝三种颜色的球各若干个。最少要摸出几个球,才能保证其中有2个球颜色相同?

解题过程

  1. 把颜色看作“抽屉”——共有3种颜色,即3个抽屉。
  2. 要保证“至少有两个球同色”,相当于让“物品数 > 抽屉数”。
  3. 最坏情况是每种颜色各摸1个(共3个),此时再摸1个,无论什么颜色,都会与已有某个颜色重复。
  4. 所以最少摸 3+1=43 + 1 = 4 个球。

答案:4个。


例题2(进阶):某班有50名学生,证明:至少有5名学生出生在同一月份。

解题过程

  1. 把12个月份看作12个“抽屉”,50名学生看作50个“物品”。
  2. 计算平均每个抽屉放多少人:50124.17\frac{50}{12} \approx 4.17
  3. 向上取整得 5012=5\left\lceil \frac{50}{12} \right\rceil = 5
  4. 根据抽屉原理推广形式,至少有一个月份(抽屉)中有不少于5名学生(物品)。

结论:一定存在至少一个月,有5人或以上出生。

⚠️ 易错点

  • 错误理解“至少”含义:认为“至少有一个抽屉有2个”等于“每个抽屉都有2个”。应强调这是存在性结论,不是普遍性。
  • 混淆物品与抽屉:例如把人数当抽屉、月份当物品。正确做法是:被分配的对象是物品,分类标准是抽屉。
  • 忽略最坏情况:在求“最少摸几个才能保证……”类问题时,必须考虑最不利情形(即尽量避免目标结果),再加1。
  • 忘记向上取整:使用推广公式时,mn\frac{m}{n} 不一定是整数,必须用 mn\left\lceil \frac{m}{n} \right\rceil 才能得到正确下界。

💡 例题

1

一个班级有20名学生要从语文、数学、英语、物理、化学五门竞赛中各选择若干门参加(每名学生至少参加一门,至多参加三门)。已知没有任何两名学生参加的竞赛组合相同。问:这个班级至少有多少名学生恰好参加了3门竞赛?

  1. 计算所有可能的参赛组合:
  • 参加1门竞赛的组合数:C(5,1) = 5种
  • 参加2门竞赛的组合数:C(5,2) = 10种
  • 参加3门竞赛的组合数:C(5,3) = 10种
  • 总共有5 + 10 + 10 = 25种不同的参赛组合。
  1. 我们需要找出"至少有多少名学生恰好参加了3门竞赛"。 考虑最不利的情况,即参加3门竞赛的学生尽可能少的情况。
  2. 假设有x名学生参加了3门竞赛,那么剩下的20-x名学生参加1门或2门竞赛。 参加1门和2门竞赛的组合共有5 + 10 = 15种。
  3. 为了使参加3门竞赛的学生尽可能少,我们需要尽可能多地使用参加1门和2门竞赛的组合。 在最不利的情况下,我们可以有15名学生分别参加1门或2门竞赛的15种不同组合,其余的20-15=5名学生必须参加3门竞赛。
  4. 所以,至少有5名学生恰好参加了3门竞赛。