抽屉原理

一、定义

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

二、抽屉原理

第一抽屉原理

如果将m个物件放入n个抽屉内，那么必有一个抽屉内至少有 [(m−1)/n]+1 个物件。

具体表现形式如下：

形式1： 把多于n个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。

证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n×1，而不是题设的n+k(k≥1)，故不可能。

形式2：把多于mn+1（n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。

证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。

形式3：把n个元素分成k的集合，那么必有一个集合含有至少[n/k]个元素，也必有一个集合至多含有[n/k]个元素。

形式4：把无数个元素分为有限个集合，必有一个集合含有无数个元素。

第二抽屉原理

把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m-1）个物体。

三、常见运用

构造抽屉的方法：运用抽屉原理的核心是分析清楚问题中，哪个是物件，哪个是抽屉。

【例1】属相是有12个，那么任意37个人中，至少有一个属相是不少于4个人。这时将属相看成12个抽屉，则一个抽屉中有 37/12，即3余1，余数不考虑，而向上考虑取整数，所以这里是3+1=4个人。

最不利原则是抽屉原理的一种应用策略，它假设每次选择都是最不利的情况，以此来保证一定会出现某种结果。例如，为了确保取出的球中有两个颜色相同的球，需要取出最多的不同颜色的球，然后再取一个，以确保有两个相同颜色的球。

最不利原则在抽屉原理中的应用实例

【例2】假设有一个箱子中有红色、蓝色和绿色三种颜色的球，每种颜色各有10个。为了确保取出的球中有两个颜色相同的球，最不利的情况是先取出9个不同颜色的球（每种颜色各3个），然后再取一个球，这个球必然与之前取出的某个球颜色相同。因此，至少需要取出10个球才能保证有两个颜色相同的球。

【例3】有300人到招聘会求职，其中软件设计有100人，市场营销有80人，财务管理有70人，人力资源管理有50人。那么至少有多少人找到工作才能保证一定有70人找的工作专业相同呢？

此时我们考虑的最差情况为：软件设计、市场营销和财务管理各录取69人，人力资源管理的50人全部录取，则此时再录取1人就能保证有70人找到的工作专业相同。因此至少需要69*3+50+1=258人。

根据第一抽屉原理之原理2推导：mn+1个人的时候必有m+1个人找到的工作专业相同，所以是要求出mn+1的人数，已知n=3，m+1=70。考虑到人力资源专业只有50人，得出mn+1=(69*3+50)+1=258人。