定理已证明

基本抽屉原理

命题陈述

如果把 $n$ 件物品分配到 $k$ 个盒子中,且 $n>k$ ,那么至少有一个盒子装有至少 $2$ 件物品。

为什么成立?

这本质上是一个计数命题,通过反证法证明:如果每个盒子至多装 $1$ 件物品,那么所有盒子总共容纳的物品数不可能超过 $k$ 。

证明思路

为反证,假设结论不成立: $k$ 个盒子中的每一个都至多装有 $1$ 件物品。

那么分配出去的物品总数至多为 $k\times1=k$ 。

但我们分配的是 $n$ 件物品,且由假设 $n>k$ ,所以分配出去的物品总数是 $n>k$ 。

对同一批物品的这两种计数相互矛盾( $n>k$ ,但总数又 $\le k$ ),所以反证假设不成立:必有一个盒子装有至少 $2$ 件物品。

用到此定理的主题

分步证明

该定理暂无分步证明。