初级鸽巢原理

鸽巢原理，也叫狄利克雷抽屉原理，或者鸽笼原理——我认为前者读来拗口，后者有些残忍（咕咕咕这么可爱你竟然把它关起来！），于是就使用「鸽巢原理」这种更加贴近自然的叫法了。

定理内容

鸽巢原理指的是一个简单的事实：一大群鸽子飞进为数不多的巢中，至少有一个巢飞进了不止一只鸽子。我们可以把鸽巢原理的简单形式抽象成一个简洁但枯燥的数学模型：

把 $n+1$ 个物品放入 $n$ 个盒子中，那么至少有一个盒子中有两个或者更多的物品。

证明：如果每个盒子中至多有一个物品，那么 $n$ 个盒子中至多有 $n$ 个物品，与条件矛盾，固定理成立。

这个原理并无深奥之处，其正确性也是显而易见的，但利用它可以解决许多有趣的组合问题，得到一些很重要的结论，它在数学发展的历史上起了很重要的作用。——《组合数学引论》

我的高中数学老师曾在一节讲概率课上讲过这样一个题：证明在边长为 1 的正方形内任取 5 个点，则其中至少有两个点的距离不超过 $\frac{\sqrt 2}{2}$.

虽然表面上使用了概率知识，但是背后的原理其实就是鸽巢原理——把正方形切成一个「田」字，四个小正方形的对角线距离是 $\frac{\sqrt 2}{2}$。四个小正方形是「巢」，五个点是「鸽」。

例题：怠惰的 potatoler

potatoler 是一名 OIer，它有 11 周的时间准备 NOIP 比赛。potatoler 很菜，于是它决定每天至少做一道题；但是又因为 potatoler 很怠惰，所以它一周（连续的 7 天）内做的题不会多于 12 道。证明：在此期间一定有连续的一些日子，potatoler 共做了 21 道题。——改自《组合数学引论》P7 例4

这个问题的难点在于：我们知道要往鸽巢原理上想，但是不知如何下手。事实上，题目中的「21 道题」绝非是简单的三乘七，其中还包含着解锁鸽巢原理的钥匙。

用 $b_1,b_2,…,b_{77}$ 表示 potatoler 每一天做的题目数，并用 $a_1,a_2,…,a_{77}$ 表示到每一天为止一共做题的数目，即：

$a_1=b_1$,

$a_2=b_1+b_2$,

…,

$a_{77}=b_1+b_2+…+b_{77}$.

由于每周做题不超过 12 道，于是有 $1\le a_1< a_2<…<a_{77}\le 12\times11$

考虑这两个数列：$a_1,a_2,…a_{77}$ 和 $a_1+21,a_2+21,…a_{77}+21$

其中每一项都在 1 到 12x11+21=153 之间，而且根据上面得出的结论，每一个数列的各个项两两不同。现在两个数列一共有 154 项，但是取值范围只有 153 个整数——154只「鸽子」，153个「巢」，那么一定有第二个数列中的某一项等于第一个数列中的某一项，即一定有 $a_j=a_i+21(1\le i<j\le77)$。

所以从第 $i+1$ 到第 $j$ 这 $i-1$ 天中，potatoler 正好做了 21 道题。

中国剩余定理初见

中国剩余定理可以求解如下形式的一元线性同余方程组，其中 $n_1,n_2,…n_k$ 两两互素： $$ \left{ \begin{aligned} x≡a_1(\bmod n_1)\ x≡a_2(\bmod n_2)\ …\ x≡a_k(\bmod n_k) \end{aligned} \right. $$ 我们在这里证明弱化的定理。设 $m,n$ 为两个互素的正整数，$a,b$ 是满足 $0\le a\le m-1,0\le b\le n-1$ 的正整数。证明：存在正整数 $x$，使得 $x$ 除以 $m$ 的余数是 $a$，除以 $n$ 的余数是 $b$，即存在 $p,q$，使得$x=pm+a, x=qn+b$.

证明：考虑数列 $a,m+a,2m+a,…(n-1)m+a$，这 n 个数除以 $m$ 余数都是 $a$。假设其中有两个数除以 $n$ 同余，余数为 $r$ ，即有$(j>i)$： $$ \left{ \begin{aligned} im+a=q_in+r\ jm+a=q_jn+1\ \end{aligned} \right. $$ 则有 $(j-i)m=(q_j-q_i)n$。我们知道 $m$ 与 $n$ 互素而且一定有 $(j-i)\le n-1$，所以右边的 $n$ 既不是 $j-i$ 的因子也不是 $m$ 的因子，与假设得出的结论矛盾——所以不可能有两个数除以 $n$ 同余。

除以 $n$ 得到的余数有 n 个，从 0 到 n-1，而最开始的数列中没有除以 $n$ 同余的数，那么这个数列中的数除以 $n$ 就可以取遍余数，因此一定存在正整数 $x$，使得$x=pm+a, x=qn+b$。

当然我们这里证明的只是中国剩余定理的超级弱化版，主要目的是为了熟悉鸽巢原理，~~并开拓思维，~~完整的证明可以去看 OI wiki。