1、3.2 鸽巢原理1. 鸽巢原理2. Ramsey数1. 鸽巢原理鸽巢原理，又叫抽屉原则，结论非常简单。n+1只鸽子放入 n个鸽巢，则至少有一个鸽巢中至少有两只鸽子。例 1 13个人中至少有 2个人在同一个月过生日。例 2 从 1到 2n的正整数中任取 n+1个，则至少存在两个数，其中一个是另一个的倍数。设取出的 n+1个数为 a1a2 an+1。对每个 ak除去所有 2的因子，直至剩下一个奇数。例如 68=2217，即 68对应于 17。这样 n+1个数分别对应于 n+1个奇数 b1b2 bn+1。这 n+1个奇数一定都小于 2n，但是 1到 2n的奇数只有n个，因此根据鸽巢原理，至少有 2个
2、相同。不妨设 bi=bj=b，则 ai=2pb， aj=2qb。ai和 aj互不相同，因此必定一个是另一个的倍数。例 3 设 a1a2a3为任意 3个整数， b1b2b3为 a1a2a3的任一排列，则 a1-b1,a2-b2,a3-b3中至少有一个是偶数 。由鸽巢原理， a1a2a3除以 2的余数至少有 2个相同。设余数为 xxy，则 b1b2b3除以 2的余数也是 xxy。因此 a1-b1,a2-b2,a3-b3除以 2的余数中至少有一个是 0。另证：由于 (a1-b1)+(a2-b2)+(a3-b3)=0，因此这三个数中至少有一个是偶数。例 4 在边长为 1的等边三角形内任意取 5个点，则
3、至少存在两个点，其距离不超过 1/2。等边三角形三边的中点把等边三角形分成四个边长为 1/2的等边三角形。每个小等边三角形内的点之间的距离不超过 1/2。由鸽巢原理，任取 5个点中至少有两个落入同一个小等边三角形内，它们的距离不超过 1/2。例 5 设 a1,a2, am是正整数序列，则至少存在 一个 k和 l， 0kk，则 Sl -Sk是 m的倍数。根据 Si的定义，但是共有 m个 ri，根据鸽巢原理，至少有 2个相同。Sl -Sk= ak+1+al，故命题成立。例 6 设 a1,a2, a100是 由 1或 2组成的序列，已知从任意一个数开始的顺序 10个数的和不超过 16，证明 至少存在
4、 一个 k和 l(kr-1，则这 n个整数中至少有一个不小于 r。例 7 设 A=a1a2a20是 由 10个 0和 10个 1 组成的二进制数， B=b1b2b20是任意的 20位二进制数。C= b1b2b20b1b2b20=c1c2c40，则必存在某个 i，使得 cici+1ci+19与 a1a2a20至少有 10位对应相等。设 di (i=1,20) 表示 cici+1ci+19与 a1a2a20对应相等的位数，则. . . . .A BC第 i 格 第 i +19格1 2 19 20 1 2 19 201 2 19 20 1 19 20d1+d2+ d20=1020=200，其平均数为
5、 10。由推论 3，至少有某个 di不小于 10。例 8 假设序列 S=a1,a2, amn+1中的各个数互不相同，证明序列 S中可以找到一个长度为 m+1的增子序列或者长度为 n+1的减子序列；而且也可以找到一个长度为 n+1的增子序列或者长度为 m+1的减子序列。显然只需要证明一个即可。证法 1：从每个 ai开始往后选取最长的增子序列，设其长度为 li，从而得到序列 l1,l2, lmn+1。若存在某个 lim+1，则命题成立 。否则所有的 li 满足 1lim，但共有 mn+1个 li，因此由推论 2，至少有 (mn+1-1)/m+1=n+1个 li 相同。不妨设则可以证明因为若不然，假设 则有 矛盾。则可以证明这样就找到了一个长度为 n+1的减子序列，命题成立。证法 2：从每个 ai开始往后选取最长的增子序列和减子序列，设其长度分别为 li和 ki。若存在某个 lim+1，或者 kin+1，则命题成立 。否则， 1lim， 1kin，这样 mn+1对 (li, ki)只有 mn种取值可能，根据鸽巢原理，必有 2对相同。不妨设 (ls, ks)=(lt, kt)，且 slt；若 asat，则 kskt。都矛盾。因此命题成立。
