有些证明能保证某个对象存在，却不告诉我们具体是哪一个。Pigeonhole principle 通过计数做到这一点：如果对象太多，不可能每个盒子只放一个，就一定有盒子放了不止一个对象。它的证明也能帮助我们区分 contraposition 与 contradiction。

Pigeonhole principle

把五个对象放进四个盒子，每个对象恰好分配到一个盒子。五个对象不可能全部分开，因此至少有一个盒子包含至少两个对象。这不表示每个盒子都有两个对象，也不表示那个共用的盒子里恰好有两个。

Pigeonhole principle，通常简称 PHP，把这个结论推广到任意正整数 $n$ 和 $m$：

把 $n$ 个对象分配到 $m$ 个盒子中，如果 $n>m$，那么至少有一个盒子包含至少两个对象。

这些对象称为 “pigeons”，盒子或类别称为 “holes”。每个对象必须恰好分配到一个 hole。应用时，难点往往是怎样选择 holes，使两个对象落入同一个 hole 就能得到我们要的结论。

Proof by contrapositive

不从“对象比 holes 多”出发，而是假设每个 hole 都少于两个对象。我们要证明，对象总数至多等于 holes 的数量。

设 $x_i$ 是第 $i$ 个 hole 中的对象数，其中 $i=1,2,\ldots,m$。每个 $x_i$ 都是非负整数，因此“少于两个”就意味着 $x_i\le1$。每个对象恰好计数一次，得到

$$n=x_1+x_2+\cdots+x_m \le\underbrace{1+1+\cdots+1}_{m\text{ terms}} =m.$$

我们已经证明：如果每个 hole 至多有一个对象，那么 $n\le m$。这正是 pigeonhole principle 的 contrapositive，所以原 statement 成立。

正六边形中的七个点

在边长为 $1$ 的正六边形内任意放置七个点。证明其中至少有两个点之间的距离不超过 $1$。

七个点就是 pigeons。为了选出有用的 holes，将六边形的中心与各顶点相连，把它分成六个 equilateral triangles。每个三角形的边长也为 $1$，同一个三角形内任意两点的距离都不超过 $1$。

把每个点分配给一个包含它的三角形。如果点位于共用边或中心，只能分配给其中一个包含它的三角形；按任意固定规则选一个即可。这样就不会重复计数。

共有七个点，却只有六个三角形。由 PHP，至少一个三角形分配到了至少两个点。这两点的距离不超过 $1$，结论成立。

这是对每一种放置方式的保证，不是概率 statement。距离上界允许取等号，因此也包含点位于六边形边界上的情况。

Generalized pigeonhole principle

如果对象数比 holes 的数量多得更多，就能保证某个 hole 不止有两个对象。至少有一个 hole 的对象数不小于平均数；由于对象数是整数，需要把平均数向上取整。

对于实数 $t$，ceiling $\lceil t\rceil$ 是大于或等于 $t$ 的最小整数。例如，

$$\left\lceil\frac76\right\rceil=2.$$

Generalized pigeonhole principle 说：把 $n$ 个对象分配到 $m$ 个 holes 中，其中 $n$ 和 $m$ 是正整数，那么至少有一个 hole 包含至少

$$\left\lceil\frac nm\right\rceil$$

个对象。这是对象数的 lower bound，不是说恰好有这么多。当 $n>m$ 时，$n/m>1$，所以 ceiling 至少为 $2$，普通 PHP 就是这个结论的特例。

抽多少张牌能保证三张同 suit？

从一副不含 jokers 的标准扑克牌中抽牌。至少抽多少张，才能保证其中至少三张属于同一个 suit？

牌是对象，四种 suits 是 holes。如果抽 $n$ 张牌，至少一种 suit 出现不少于 $\lceil n/4\rceil$ 次。我们需要

$$\left\lceil\frac n4\right\rceil\ge3.$$

只要 ceiling 内部的数超过 $2$，ceiling 就至少为 $3$；内部的数本身不需要达到 $3$。因此

$$\left\lceil\frac n4\right\rceil\ge3 \quad\Longleftrightarrow\quad \frac n4>2 \quad\Longleftrightarrow\quad n>8.$$

由于 $n$ 是整数，抽九张就足够。要得到保证，九张也是必要的：八张可能恰好每种 suit 各两张，没有任何 suit 出现三次。所以最小值是 $9$。

Proof by contradiction

用 contradiction 证明 statement $P$ 时，先假设它的 negation $\neg P$ 成立，再推出不可能的结果。于是这个假设必须为假，$P$ 为真。在 classical logic 中，

$$P\equiv(\neg P\Rightarrow\mathrm{False}).$$

这个不可能的结果不一定要直接反驳某个已经写出的 hypothesis。例如，推出 $n<n$ 就足够了，因为没有哪个数严格小于它自己。

证明 generalized pigeonhole principle

结论要求至少有一个 hole 达到指定数量。否定它，就得到每个 hole 的对象数都低于这个数量，因此可以把各个上界相加，检查是否还能容纳全部对象。

令 $x_i$ 为第 $i$ 个 hole 中的对象数，其中 $i=1,2,\ldots,m$。每个对象恰好分配到一个 hole，所以

$$n=x_1+x_2+\cdots+x_m.$$

目标是证明某个 hole 至少有 $\lceil n/m\rceil$ 个对象。为了用 contradiction 证明，假设每个 hole 的对象数都低于这个 bound：

$$x_i<\left\lceil\frac nm\right\rceil \qquad\text{for every }i=1,2,\ldots,m.$$

要将这些数量与平均数 $n/m$ 比较，先用 ceiling 的定义性质：

$$\lceil t\rceil-1<t\le\lceil t\rceil.$$

如果 $t$ 是整数，右侧 inequality 取等号，但左侧仍然是 strict inequality。

每个 $x_i$ 都是整数。因此，它小于整数 $\lceil n/m\rceil$ 时，至少比它小一个整数单位：

$$x_i\le\left\lceil\frac nm\right\rceil-1<\frac nm.$$

将全部 $m$ 个 holes 对应的 strict inequalities 相加，得到

$$n=x_1+x_2+\cdots+x_m <\underbrace{\frac nm+\frac nm+\cdots+\frac nm}_{m\text{ terms}} =m\frac nm=n.$$

这就得到了 $n<n$，产生 contradiction。因此，“每个 hole 的对象数都低于这个 bound”的假设为假，于是

$$\exists i\in\{1,2,\ldots,m\}\quad x_i\ge\left\lceil\frac nm\right\rceil.$$

注意 assumption 中的“每个”变成了 conclusion 中的“某个”。否定“每个 hole 都低于 bound”，并不意味着每个 hole 都达到了 bound。

例：根号二是 irrational

用 $\mathbb Z$ 表示整数集。Rational number 可以写成 $a/b$，其中 $a$、$b$ 都是整数，且 $b\ne0$。Rational numbers 组成的 set 记作 $\mathbb Q$。Irrational number 是不属于 rational numbers 的实数。我们要证明

$$\sqrt2\notin\mathbb Q.$$

每个 rational number 都能写成分母为正的 lowest terms 形式：取 $b>0$，且 $\gcd(a,b)=1$。这里，$\gcd(a,b)$ 表示 $a$ 和 $b$ 的 greatest common divisor；这个条件说明它们没有除 $1$ 以外的正公因子。

假设 $\sqrt2$ 是 rational，以求推出 contradiction。选择这样的 reduced representation：

$$\sqrt2=\frac ab, \qquad a,b\in\mathbb Z,\quad b>0,\quad\gcd(a,b)=1.$$

两边平方，再乘以 $b^2$，得到

$$2=\frac{a^2}{b^2} \quad\Longrightarrow\quad a^2=2b^2.$$

因此 $a^2$ 是 even。整数平方的 parity 结论 说明，一个整数是 even，当且仅当它的平方是 even。所以 $a$ 是 even，存在整数 $k$，使 $a=2k$。

把它代回 $a^2=2b^2$：

$$(2k)^2=2b^2 \quad\Longrightarrow\quad 4k^2=2b^2 \quad\Longrightarrow\quad b^2=2k^2.$$

现在 $b^2$ 是 even，由同一个 parity 结论，$b$ 也是 even。于是可以写成 $b=2\ell$，其中 $\ell$ 是整数。

这样，$a$ 和 $b$ 都有公因子 $2$，与 $\gcd(a,b)=1$ 矛盾。原假设为假，因此 $\sqrt2$ 是 irrational。

一开始选择 lowest terms 对这个证明不可缺少。发现任意一个分式的分子、分母有公因子，不会产生 contradiction；只有在已经假设分式约分到最低项之后，发现公因子才构成 contradiction。

Proof by cases

不同输入有时需要不同论证。Proof by cases 把所有可能输入分成若干种情况，再在每一种情况下证明所需 conclusion。

对于 $k$ 种情况，令 $A_1,\ldots,A_k$ 表示各情况的条件，$C$ 表示 conclusion。相应的 logical equivalence 是

$$\bigl((A_1\lor\cdots\lor A_k)\Rightarrow C\bigr) \equiv \bigl((A_1\Rightarrow C)\land\cdots\land(A_k\Rightarrow C)\bigr).$$

要得到 $C$，还必须知道至少一种情况成立，即 $A_1\lor\cdots\lor A_k$。这些 cases 必须 exhaustive，也就是覆盖全部可能性。Cases 可以重叠，不要求 mutually exclusive。即使题目没有提示如何分类，选择有用的 cases 也是证明的一部分。

例：整数不大于它的平方

我们要证明

$$n\le n^2\qquad\text{for every }n\in\mathbb Z.$$

任取整数 $n$，根据它的正负分情况。

Case 1：$n\le0$。 平方非负，因此

$$n\le0\le n^2.$$

Case 2：$n>0$。 由于 $n$ 是整数，所以 $n\ge1$。将 $1\le n$ 两边乘以正数 $n$，不等号方向不变：

$$n\cdot1\le n\cdot n, \qquad\text{so }n\le n^2.$$

每个整数都满足 $n\le0$ 或 $n>0$，而两种情况都得到了所需结论，因此 claim 成立。

整数假设恰好用在从 $n>0$ 推出 $n\ge1$ 的那一步。对于任意正实数，这一步并不成立。