针对抽屉原理的归纳、梳理和总结.
如果把 $n+1$ 个物体放进 $n$ 个抽屉,那么至少有一个抽屉包含多于一个物体.
这是抽屉原理最简单、最原始的形式,其陈述的内容可以说是 trivial 的——本文并不打算对抽屉原理进行证明,因为其证明同样是显然的(反证法). 本文旨在梳理各种形式的抽屉原理,并尽可能细致地阐述抽屉原理值得注意、或者容易忽略的细节.
“物体” 和 “抽屉” 当然不是仅指代具体的物体和抽屉,他们可以是各种形式的数学对象:
抽屉包含物体,指的是数学对象之间的对应关系,不一定须是集合包含元素,或者圆包含点这种狭义的 “包含”;
但要注意的是,抽屉原理本质上要求的是 物体的集合 到 抽屉的集合 的映射:
因此,可以用较为现代的语言改写抽屉原理:
若有映射 $f:A \rightarrow B$, $\lvert A \rvert=n+1$, $\lvert B \rvert = n$,其中 $n$ 是正整数,那么 $f$ 不是单射.
存在性判定:抽屉原理(在没有其他条件、命题或定理的辅助下)只能用于存在性的判断.
这一点从其命题叙述上就可见端倪:
至少有一个抽屉包含多于一个物体
抽屉原理只能断言某个抽屉具有不止一个物体,具体是哪个抽屉,以及这个抽屉具体有多少个物体,无法单凭抽屉原理确定;
抽屉原理有不止一种阐述与推广形式,许多教材与资料在最简单的基础上会列出额外的若干种阐述;
笔者经过梳理后认为,这些推广与变形形式应该归结到不同的 方面/维度 上
不同的维度是相互独立的,理论上它们可以自由地组合
设 $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$ 个抽屉,那么:
第 $1$ 个抽屉里至少有 $q_{1}^{}+1$ 个物体
第 $2$ 个抽屉里至少有 $q_{2}^{}+1$ 个物体
……
第 $n$ 个抽屉里至少有 $q_{n}^{}+1$ 个物体
以上 $n$ 个陈述至少有一个成立
可以认为均分形式是最简单形式的推广,而加权形式又是均分形式的推广
加权形式的抽屉原理乍看上去不如简单形式那样显然;理解的时候要注意的是:
第一个抽屉对应的正整数 $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$ 个陈述至少有一个成立
这两个命题都同时成立.
笔者曾经在做某些问题的时候,也曾稍微感到迷糊;然而它们都的确同时真实地成立;
注意:某个抽屉 $i$,使得 1. 和 2. 同时成立,当且仅当这个抽屉对应的值恰好等于 $q_{i}^{}$
我们还注意到,抽屉的数目是固定的,所分配的值也是确定的——这才使得我们可以同时从正、反两个方向对抽屉的值作断言;
如果我们把条件中的 ”实数值 $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$ 个抽屉,那么:
第 $1$ 个抽屉的值不小于 $q_{1}^{}$
第 $2$ 个抽屉的值不小于 $q_{2}^{}$
……
第 $n$ 个抽屉的值不小于 $q_{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$ 个抽屉中,则必有至少两个抽屉包含相等数目的元素