针对抽屉原理的归纳、梳理和总结.

最简单的形式

如果把 $n+1$ 个物体放进 $n$ 个抽屉,那么至少有一个抽屉包含多于一个物体.

这是抽屉原理最简单、最原始的形式,其陈述的内容可以说是 trivial 的——本文并不打算对抽屉原理进行证明,因为其证明同样是显然的(反证法). 本文旨在梳理各种形式的抽屉原理,并尽可能细致地阐述抽屉原理值得注意、或者容易忽略的细节.

  1. “物体” 和 “抽屉” 当然不是仅指代具体的物体和抽屉,他们可以是各种形式的数学对象:

    • 集合
    • 函数
    • 点、线、面
    • ……
  2. 抽屉包含物体,指的是数学对象之间的对应关系,不一定须是集合包含元素,或者圆包含点这种狭义的 “包含”;

  3. 但要注意的是,抽屉原理本质上要求的是 物体的集合 到 抽屉的集合 的映射

    • 每一个物体都分配到唯一的抽屉中
    • 任何一个抽屉都可以不包含物体,也可以包含任意个物体

    因此,可以用较为现代的语言改写抽屉原理:

    若有映射 $f:A \rightarrow B$$\lvert A \rvert=n+1$, $\lvert B \rvert = n$,其中 $n$ 是正整数,那么 $f$ 不是单射.

  4. 存在性判定:抽屉原理(在没有其他条件、命题或定理的辅助下)只能用于存在性的判断.

    这一点从其命题叙述上就可见端倪:

    至少有一个抽屉包含多于一个物体

    抽屉原理只能断言某个抽屉具有不止一个物体,具体是哪个抽屉,以及这个抽屉具体有多少个物体,无法单凭抽屉原理确定;

抽屉原理有不止一种阐述与推广形式,许多教材与资料在最简单的基础上会列出额外的若干种阐述;

笔者经过梳理后认为,这些推广与变形形式应该归结到不同的 方面/维度 上

  1. 均分与加权
  2. 正向与反向
  3. 离散与连续
  4. 有限与无限

不同的维度是相互独立的,理论上它们可以自由地组合

均分与加权

均分形式

$m$$n$ 都是正整数,如果把 $m$ 个物体分配到 $n$ 个抽屉中,那么至少有一个抽屉包含不少于 $\lceil \frac mn \rceil$ 个物体

加权形式

$q_{1}^{}$, $q_{2}^{}$, $q_{3}^{}$, $\ldots$, $q_{n}^{}$ 是正整数,如果将多于 $q_{1}^{}+q_{2}^{}+q_{3}^{}+\cdots+q_{n}^{}$ 个物体放进这 $n$ 个抽屉,那么:

以上 $n$ 个陈述至少有一个成立

注解

  1. 可以认为均分形式是最简单形式的推广,而加权形式又是均分形式的推广

  2. 加权形式的抽屉原理乍看上去不如简单形式那样显然;理解的时候要注意的是:

    第一个抽屉对应的正整数 $q_{1}^{}$,第二个抽屉对应的正整数 $q_{2}^{}$,……,直至第 $n$ 个抽屉对应的 $q_{n}^{}$,这些数并不是恒定不变的,只要满足 $q_{1}^{}+q_{2}^{}+\ldots+q_{n}^{}$ 小于物体的数目,那么就可以任意地分划,并可放心地应用抽屉原理的加权形式

正向与反向

$m$$n$ 都是正整数,如果把 $m$ 个物体分配到 $n$ 个抽屉中,那么至少有一个抽屉包含不少于 $\lceil \frac mn \rceil$ 个物体,同时也至少存在一个抽屉包含不多于 $\lfloor \frac mn \rfloor$ 个物体;

加权形式也同时存在正反向表述.

$q_{1}^{}$, $q_{2}^{}$, $q_{3}^{}$, $\ldots$, $q_{n}^{}$ 是实数,如果将实数值 $q_{1}^{}+q_{2}^{}+q_{3}^{}+\cdots+q_{n}^{}$ 个分配给这 $n$ 个抽屉,那么:

- 第 $1$ 个抽屉的值不小于 $q_{1}^{}$

- 第 $2$ 个抽屉的值不小于 $q_{2}^{}$

- ……

- 第 $n$ 个抽屉的值不小于 $q_{n}^{}$

以上 $n$ 个陈述至少有一个成立. 
- 第 $1$ 个抽屉的值不大于 $q_{1}^{}$

- 第 $2$ 个抽屉的值不大于 $q_{2}^{}$

- ……

- 第 $n$ 个抽屉的值不大于 $q_{n}^{}$

以上 $n$ 个陈述至少有一个成立

这两个命题都同时成立.

笔者曾经在做某些问题的时候,也曾稍微感到迷糊;然而它们都的确同时真实地成立;

  1. 注意:某个抽屉 $i$,使得 1. 和 2. 同时成立,当且仅当这个抽屉对应的值恰好等于 $q_{i}^{}$

  2. 我们还注意到,抽屉的数目是固定的,所分配的值也是确定的——这才使得我们可以同时从正、反两个方向对抽屉的值作断言;

    如果我们把条件中的 ”实数值 $q_{1}^{}+q_{2}^{}+q_{3}^{}+\cdots+q_{n}^{}$” 改为 “某个不小于 $q_{1}^{}+q_{2}^{}+q_{3}^{}+\cdots+q_{n}^{}$ 的值”,那么原来的 2. 就不再成立了

离散与连续

上述的所有表述,针对的都是离散的数值;而我们可以对 物体的数目 做进一步的推广(由离散到连续),得到如下的形式.

$q_{1}^{}$, $q_{2}^{}$, $q_{3}^{}$, $\ldots$, $q_{n}^{}$ 是实数,如果将实数值 $q_{1}^{}+q_{2}^{}+q_{3}^{}+\cdots+q_{n}^{}$ 个分配给这 $n$ 个抽屉,那么:

以上 $n$ 个陈述至少有一个成立

不难看出,连续形式是离散形式的进一步推广,后者与前者不同的地方主要在于,离散形式需要考虑取整的问题;

无限与有限

把无穷多个物体分配个 $n$ 个抽屉,那么至少有一个抽屉包含无穷多个物体

在笔者接触过的组合问题当中,物体数量为无穷大的情形并不常见

其他约束

(广义)单射约束

如果把 $n$ 个物体放入 $n$ 个抽屉,并且使得没有任何一个抽屉中有多于一个物体,那么每个抽屉恰好有一个物体.

我们可以继续推广一下,得到如下的结论:

如果把 $q_{1}^{}+q_{2}^{}+q_{3}^{}+\cdots+q_{n}^{}$ 个物体放入 $n$ 个抽屉,并且使得第 $i$ 个抽屉中的物体不多于 $q_{i}^{}$ 个,那么每个抽屉恰好$q_{i}^{}$ 个物体.

(广义)满射约束

如果把 $n$ 个物体放入 $n$ 个抽屉,并且使得没有一个抽屉是空的,那么每个抽屉恰好有一个物体.

同样地,我们可以继续推广一下,得到如下的结论:

如果把 $q_{1}^{}+q_{2}^{}+q_{3}^{}+\cdots+q_{n}^{}$ 个物体放入 $n$ 个抽屉,并且使得第 $i$ 个抽屉中的物体不少于 $q_{i}^{}$ 个,那么每个抽屉恰好$q_{i}^{}$ 个物体.

不等容约束

不等容下界

少于 $\binom{n}{2}$ 个元素分到 $n$ 个抽屉中,那么必然至少有 $2$ 个抽屉包含的元素数目相等

不等容上界

$k \geq n-1$(必要条件), 若每个抽屉最大的容纳量为 $k$,将多于 $k+(k-1)+\cdots + (k-n+1)=nk-\binom{n}{2}$ 个元素分到 $n$ 个抽屉中,则必有至少两个抽屉包含相等数目的元素