第1章 鸽巢原理及其应用
　　鸽巢原理， 亦称抽屉原理， 是组合数学中一个*基本的存在性原理. 应用鸽巢原理可以解决许多涉及存在性的组合问题. 本章主要介绍鸽巢原理以及在解决存在性问题上的应用.
　　1.1 鸽巢原理的简单形式
　　定理 1.1.1 (鸽巢原理) 把 n + 1 个物体放入 n 个盒子里， 则一定存在至少有一个盒子里含有两个或两个以上的物体.
　　证明 (反证法) 若没有一个盒子里含有两个或两个以上的物体， 则所有盒子里至多含有 n 个物体， 这与要放 n + 1 个物体矛盾， 故此原理成立.
　　例 1.1.1 在边长为 1 的正方形内任意放 n2 + 1 个点， 证明存在至少有两个点之间的距离不大于√2 n .
　　证明 将此正方形每边 n 等分， 过这些 n 等分点， 用平行于边的直线将正方形划分为总共 n2 个边长为的小正方形， 而正方形中任意两点之间的距离小于等于 √2， 将 n2 + 1 个点放入正方形内， 必定存在两个点放入同一个小正方形内，而小正方形内两点之间距离不大于√2n . 命题得证.
　　例 1.1.2 证明任何一组人中都存在两个人， 他们在组内认识的人数恰好相等.
　　证明 *先一组人至少有 2 人， 因此假设有 n 个人 (n . 2)， 若这 n 个人中有 1 人不认识其他任何人， 那么可只考虑余下的 n . 1 人 (n . 1 . 2， 若不然， 则余下 1 人， 这两人互不认识， 命题得证). 若这剩余的 n . 1 个人中有人不认识其他任何人， 那么命题得证 (此时已有两人认识的人数为零). 因此， 不失一般性， 可设剩下的 n . 1 人中每人至少认识一个人， 可是每个人又至多认识其他 n . 2 人，因此， 由鸽笼原理可知， 这 n . 1 个人至少有两人认识的人数相等.
　　例 1.1.3 一个棋手为参加一次锦标赛将进行 77 天的练习， 如果他每天至少下一盘棋， 而每周至多下 12 盘棋， 证明存在一个正整数 n 使得他在这 77 天里有连续的 n 天共下了 21 盘棋.
　　证明 设 ai 是从**天到第 i 天下棋的总盘数， i = 1， 2， ， 77. 因为他每天至少下一盘棋， 所以1 . a1 < a2 < < a77.
　　又因为每周至多下 12 盘棋， 77 天中下棋的总数 a77 不超过12 &times;777= 132.作序列a1 + 21， a2 + 21， ， a77 + 21，这个序列是严格单调递增的， 且有 a77 + 21 . 153. 考察下面的序列:
　　该序列有 154 个数， 每个数都是小于等于 153 的正整数， 由鸽巢原理知， 必存在 i和 j 使得 ai = dj + 21(j < i). 令 n = i . j， 则该棋手在第 j + 1， j + 2， ， j + n的连续 n 天中下了 21 盘棋.
　　例 1.1.4 证明: 在非闰年年份中， 每年中一定至少有一个 13 日是星期五， 至多有三个 13 日是星期五.
　　证明 每年中共有 12 个 13 日， 将它们表示为 1.13， 2.13， ， 12.13. 如果它们都非星期五， 那么它们是 (以下为方便叙述作简单标记)*1， *2， *3， *4， *6， *7(星期日) 之一. 我们知道 2.13， 3.13， 11.13 必是同一个 *n (比如 *6， 因为它们之间分别相隔 28 天和 245 天)， 于是余下的 9 个 13 日是 *1， *2， *3， *4， *7 之一. 又知1.13 与 10.13 是同一个 *n(它不可能与 2.13 是同一个 *n， 比如为 *7)， 因为它们之间相隔 273 天. 又由于 4.13 与 7.13 以及 9.13 与 12.13 分别具有相同的 *n， 例如 *3， *4， 因为它们分别相隔 91 天 (同样它们不可能是 *6， *7， 因为 4.13 及 9.13与 1.13， 2.13 相隔的天数均不是 7 的整数倍). 这样剩下的 3 个 13 日 (5.13， 6.13，8.13) 是 *1 和 *2 之一 (它们不可能是 *3， *4， *6， *7， 因为它们与 1.13， 2.13， 4.13，9.13 相隔的天数均不是 7 的整数倍). 根据鸽巢原理， 这 3 个 13 日中至少要有两个是同一个 *n， 但这是不可能的， 因为这 3 个 13 日之间相隔的天数都不是 7 的倍数， 故矛盾， 说明至少有一个 13 日是星期五.
　　由前面的讨论可知， 至多只有三个月， 它们两两之间的间隔天数都是 7 的倍数， 为 2 月， 3 月， 11 月. 因此， 只有 2.13， 3.13， 11.13 可能同时为星期五， 不可能有 4 个月的 13 日全为星期五.
　　注 1.1.1 鸽巢原理也称狄利克雷 (Dirichlet) 原理， 是因为他*先将此简单的结论应用到数论问题上， 得到了若干漂亮的结果.
利用鸽巢原理还可得到下述结果:
　　(1) 在边长为 2 的正方形内任取 5 点， 则存在至少两点， 它们之间的距离不超过 √2.
　　(2) 某学生有 37 天的时间准备考试， 根据过去他的经验至多需要复习 60 个小时， 但每天至少要复习 1 小时， 则无论怎样安排都存在连续的若干天， 使得他在这些天里恰好复习了 13 小时.
　　(3) 任意给定平面上的五个点 (没有三个点共线) 中， 则必有四个点是一个凸四边形的四个顶点.
　　1.2 鸽巢原理在组合与数论上的应用
　　定理 1.2.1 在 n + 1 个小于等于 2n 的不相等的正整数中， 一定存在两个数互素.
证明 将 1， 2， ， 2n 分成以下 n 组:
　　{1， 2}， {3， 4}， ， {2n . 1， 2n}，
　　从组中任取 n + 1 个不同的数， 由鸽巢原理知， 至少有两个数取自同一组， 它们是相邻的两数， 由于任何相邻的两数互素， 因此这两个数互素， 命题得证.
　　定理 1.2.2 设 a1， a2， ， an 是 1， 2， ， n 的一个排列， 则当 n 为奇数时，乘积 (a1 . 1)(a2 . 2) (an . n) 为偶数.
　　证明 当 n 为奇数时， 1， 2， ， n 和 a1， a2， ， an 中的奇数是n + 1 2 个， 而偶数只有n . 1 2 个， 因此在 a1 .1， a3 .3， a5 .5， ， an .n 中， a1， a3， a5， ， an 共n + 1 2 个至少有一个是奇数， 例如 ai， 从而 ai . i 是偶数， 于是得到整个乘积为偶数.
　　定理 1.2.3 设 x1， x2， ， xn 是 n 个正整数， 则其中存在连续的若干个数，其和是 n 的倍数.
　　证明 令 Si = x1 + x2 + + xi， i = 1， 2， ， n. 把 Si 除以 n 的余数记作 ri， 0 . ri . n . 1. 如果存在 i， 使得 ri = 0， 则 x1 + x2 + + xi 可以被 n整除， 命题得证. 如果对所有的 i， i = 1， 2， ， n， 都有 ri .= 0， 那么 n 个 ri 只能有 1， 2， ， n . 1 种可能的取值， 故由鸽巢原理知， 必存在 j 和 k 满足 rj = rk，j > k. 因此有
　　可以被 n 整除. 命题得证.
定理 1.2.4 在 1， 2， ， 2n 中任取 n + 1 个不同的数， 则其中至少有一个数是另一个数的倍数.
　　证明 由于任何正整数 n 都可以表示为 n = 2α β 的形式， 这里 α 为非负整数， β 为奇数. 设选出的 n + 1 个数为 a1， a2， ， an+1， 把它们依次表示为2α1β1， 2α2β2， ， 2αn+1βn+1， 其中 β1， β2， ， βn+1 是 n + 1 个奇数， 它们的取值只有 n 种可能， 即 1， 3， ， 2n . 1. 由鸽巢原理知， 必存在 i 和 j， 使得 βi = βj .
　　考虑 ai = 2αiβi 和 aj = 2αjβj ， 不妨设 ai < aj ， 则有
　　故 aj 是 ai 的倍数.
　　定理 1.2.5 (Dirichlet 逼近定理) 对任意给定的实数 x 和正整数 q， 一定有正整数 p . q 和整数 h 使得
　　证明 把左闭右开的实数区间 [0， 1) 等分成 q 个小区间(k = 1， 2， ， q). 再考察 q + 1 个 [0， 1) 中的实数 px . .px. (p = 0， 1， ， q). 根据鸽巢原理， 这 q + 1 个数中一定有两个属于同一区间 Ik， 即有 k ∈ {1， 2， ， q}， 0 . p′ < p′′ . q， 使得 p′x . .p′x. 和 p′′x . .p′′x. 都属于 Ik， 从而有，令 p = p′′ . p′， h = .p′′x .p′x.， 即得结论.
　　定理 1.2.6 (中国剩余定理) 令 m 和 n 为两互素的正整数， 并令 a 和 b 为两整数， 且以及， 则存在一个正整数 x， 使得 x 除以 m的余数为 a， 并且 x 除以 n 的余数为 b， 即 x 可以写成 x = pm + a 的同时， 又可写成 x = qn + b 的形式， 这里 p 和 q 是两个整数.