§8 鸽巢原理之一 §8 鸽巢原理之一 鸽巢原理是组合数学中最简单也是最基本的原理，也叫 抽屉原理。即 “若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。” 例１ 367人中至少有２人的生日相同。 例２ 10双手套中任取11只，其中至少有两只是完整配对的。 例３ 参加一会议的人中至少有２人认识的别的参加者的人数相等。 例４ 从1到2n的正整数中任取n+1个，则这n+1个数中，至少有一对数， 其中一个是另一个的倍数。 证 设n+1个数是 a1 , a2 , ··· , an+1。每个数去掉一切2的因子， 直至剩下一个奇数为止。组成序列 r1 , r2, ··· , rn+1。这n+1个数仍在 ［1 , 2n]中，且都是奇数。而[1 , 2n]中只有n个奇数 . 故必有 ri = rj = r , 则 src="3_8_1.gif" align="middle" width="144" height="30">,若αi＞αj ，则 ai 是 aj 的倍数。 例5 设 a1 , a2 , ··· , am是正整数序列，则至少存在k和 l , 1≤k≤ l ≤m， 使得和 ak + ak+1 + ··· + al 是m的倍数。 证 设,Sh≡ rh mod m , 0≤rh≤m-1，h = 1 , 2 , ··· , m . 若存在l , Sl≡0 mod m 则命题成立．否则，1≤rh≤m-1．但h = 1 , 2 , ··· , m．由鸽巢原理，故存在 rk = rh , 即 Sk≡ Sh，不妨设 h ＞k．则 Sh－Sk = ak+1 + ak+2 +… + ah ≡0 mod m 例６ 设 a1 , a2 , a3为任意３个整数，b1b2b3为a1 , a2 , a3的任一排列， 则 a1－b1 , a2－b2 , a3－b3中至少有一个是偶数． 证 由鸽巢原理， a1 , a2 , a3必有两个同奇偶．设这３个数被２除的余数为 xxy， 于是b1 , b2 , b3中被２除的余数有２个x，一个y．这样a1－b1 , a2－b2 , a3－b3 被２除的余数必有一个为０． 例７ 设a1 , a2 , ··· , a100是由 1和２组成的序列 , 已知从其任一数开始的顺序10个数的 和不超过16．即 ai + ai+1 +… + ai+9 ≤16，1≤ i ≤91 则至少存在 h 和 k ，k > h，使得 ah + ah+1 +… + ak = 39 证 令，j =1 , 2 , … ,100 显然S1＜S2＜…＜S100，且 S100=(a1 + … +a10)+(a11 + … +a20)+…+(a91 + … +a100) 根据假定有 S100≤10×16=160， 作序列S1, S2 , … , S100 , S1 +39, … , S100+39 .共200项．其中最大项 S100+39≤160+39由鸽巢原理，必有两项相等． 而且必是前段中某项与后段中某项相等．设 Sk=Sh + 39，k＞h, Sk－Sh =39 即 ah + ah+1 +… + ak = 39
