数学课堂
挑战≈ 15 分钟未开始

抽屉原理

核心概念

抽屉原理(鸽笼原理)——基本形式:把 n+1n+1 个物体放进 nn 个抽屉,则至少有一个抽屉里有 22 个或更多物体。

加强形式:把 mm 个物体放进 nn 个抽屉,则至少有一个抽屉里的物体数不少于

⌈mn⌉(向上取整).\left\lceil \frac{m}{n} \right\rceil \quad(\text{向上取整}).

使用关键:解题的难点几乎总在"如何构造抽屉"。物体是什么、抽屉按什么标准分,需要根据问题巧妙设计——余数、区间、颜色、坐标奇偶都可以是抽屉。

直观理解 · 动手试试

抽屉原理朴素到近乎显然:东西比格子多,必有格子挤了不止一个。但它的威力在于存在性证明——它不告诉你"是哪一个"挤了,只断言"一定存在"这样一个。很多竞赛题要证"必然存在两个满足某关系的对象",抽屉原理就是首选。

真正的功夫在设计抽屉:把"满足某关系"翻译成"落进同一个抽屉"。一旦抽屉设计得当,使物体数超过抽屉数,结论立刻成立。所以解题时先问自己:物体是谁?抽屉怎么分?为什么同抽屉就意味着我要的结论?

抽屉原理

7 个物体放进 3 个抽屉

抽屉 1
抽屉 2
抽屉 3
即使尽量平均地放,也必有一个抽屉至少装 ⌈7/3⌉ = 3 个。
7
3

物体比抽屉多时,必有抽屉装了不止一个。解题难点常在「如何设计抽屉」——余数、区间、颜色都可以当抽屉。

例题 1基础应用

证明:任意 1313 个人中,必有两人出生在同一个月。

▸查看解答步骤

答: 必有两人生日同月

例题 2按余数构造抽屉

从任意 66 个整数中,证明必有两个数之差能被 55 整除。

▸查看解答步骤

答: 必有两数之差被 5 整除

即时练习

要保证至少有两人出生在同一个月,至少需要多少人?

1212 个月做抽屉,需 12+1=1312+1 = 13 人才能保证。

把 99 个苹果放进 22 个抽屉,必有一个抽屉至少有几个苹果?

⌈9/2⌉=5\lceil 9/2\rceil = 5,必有抽屉至少 55 个。

要保证至少有两人星期几出生相同(一周 77 天),至少需要多少人?

77 个抽屉,需 7+1=87+1 = 8 人。

任取 1111 个整数,必有两个数的个位数字相同。

个位数字只有 0∼90\sim9 共 1010 种(抽屉),1111 个数必有两个个位相同。

要保证至少两人星座相同(共 1212 个星座),至少需要多少人?

1212 个抽屉,需 12+1=1312+1 = 13 人。

把 1010 个球放进 33 个抽屉,必有一个抽屉至少有几个球?

⌈10/3⌉=4\lceil 10/3\rceil = 4。

易错点

  • 抽屉数算错。 余数类、月份、个位数字……要数清恰好有几个抽屉,差一个结论就不同。
  • 把"存在"误读成"具体是哪个"。 抽屉原理只保证存在,不指出是哪一个,别试图断定具体对象。
  • 物体数没真正超过抽屉数。 基本形式要 n+1n+1 个物体配 nn 个抽屉,恰好相等是不够的。

下一步

接下来学习