抽屉原理,也叫鸽巢原理,是组合数学中一个非常基础但重要的原理。它的基本表述是:如果有 n 个物体要放进 m 个抽屉里,且物体数量大于抽屉数量,那么至少有一个抽屉里会包含不止一个物体。比如这里有4个球要放进3个抽屉,根据抽屉原理,至少有一个抽屉里会有2个或更多的球。
抽屉原理有一个更一般的表述:如果有 n 个物体要放进 m 个抽屉里,那么至少有一个抽屉里会包含至少 n 除以 m 向上取整个物体。这里的向上取整符号表示不小于这个数的最小整数。比如7个球放进3个抽屉,7除以3等于2点33,向上取整得到3,所以至少有一个抽屉包含3个球。
让我们看一个抽屉原理的经典应用。问题是:在任意13个人中,至少有两个人的生日在同一个月。这个问题可以用抽屉原理来解决。我们有13个人作为物体,12个月作为抽屉。因为13大于12,根据抽屉原理,至少有一个月会包含两个或更多人的生日。这就证明了我们的结论。
现在让我们用反证法来证明抽屉原理。假设每个抽屉最多包含1个物体,那么m个抽屉最多能容纳m个物体。但我们已知有n个物体,且n大于m,这就产生了矛盾。因此我们的假设是错误的,至少有一个抽屉必须包含超过1个物体。这就完成了抽屉原理的证明。
总结一下我们学到的内容:抽屉原理是组合数学中一个非常基本但重要的原理。它告诉我们,当物体数量大于抽屉数量时,必然会有重复的分配情况出现。这个原理广泛应用于各种存在性证明和计数问题中,是一个简单却非常强大的数学工具。