组合数学第二章[鸽巢原理].pptVIP

第二章鸽巢原理;§2.1鸽巢原理根本形式; 鸽巢原理可做如下推论：

(1)如果n个物体放入n个盒子且没有一个盒子是空的，那么每个盒子恰好包含一个物体。

(2)如果n个物体放入n个盒子且没有盒子被放入多于一个的物体，那么每个盒子恰好包含一个物体。

使用鸽巢原理的重点在于如何构造鸽巢。;[例3]从1到2n的正整数中任取n+1个，那么这n+1个数中，至少有一对数，其中一个是另一个的倍数。

[证]设n+1个数是a1,a2,···,an+1。由于任一个整数可表示成2k×a。故可将每个数去掉一切2的因子，直至剩下一个奇数a为止，记组成序列r1,r2,,···,rn+1。这n+1个数仍在［1,2n]中，且都是奇数。而[1,2n]中只有n个奇数。故必有ri=rj=r,那么ai=2αr,aj=2βr。显然，其中的大数为小数的倍数。;[例4]设a1、a2、a3为任意3个整数，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被２除的余数必有一个为０。;[例5]设a1,a2,···,am是正整数序列，那么至少存在k和l,1≤k≤l≤m，使得和ak+ak+1+···+al是m的倍数。

[证]记Sk=a1+a2+···+ak，且记Sk≡rkmodm，其中0≤rkm，k=1,2,···,m。

假设存在l，使Sl≡0modm那么命题成立。否那么，1≤rk≤m-1，即m个余数置于m-1个盒子里，故存在rk=rh，即Sk≡Sh。不妨设h＞k，那么Sh-Sk=ak+1+ak+2+…+ah≡0modm。;[例6]设a1,a2,···,a100是由1和２组成的序列,从其任一数开始的顺序10个数的和不超过16．即

ai+ai+1+…+ai+9≤16，1≤i≤91

那么至少存在h和k，kh，使得

ah+ah+1+…+ak=39

[证]令Sj=a1+a2+…+aj，j=1,2,…,100。

显然有S1S2…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，kh，那么Sk-Sh=39，即ah+ah+1+…+ak=39。;§2.2??巢原理的加强形式; 上一小节的鸽巢原理一是这一原理的特殊情况，即m1=m2=…=mn=2。

[推论1]m只鸽子进n个巢，至少有一个巢里有只鸽子。

[推论2]n(m-1)+1只鸽子进n个巢，至少有一个巢内至少有m只鸽子。

[推论3]假设m1,m2,…,mn是正整数，且(m1+m2+…+mn)/n≥r，那么m1,…,mn中至少有一个不小于r。;[例1]如以下图的大小盘子，都被均匀地分成200个扇形。大盘中任选100个扇形图红色，余下100个图兰色。小盘中的扇形可任意涂成兰色或红色。证明，能够将两盘子的扇形对齐使得小盘子和大盘子上相同颜色重合的扇形数目超过100个。

[证]可考虑大盘固定，小盘转动，每转动一个扇形时匹配的扇形数mi，1≤i≤200。

当小盘转过一圈时，每个小盘上的扇形无论红或兰，都会与大盘上100个扇形匹配，故总匹配扇形数为200*100=20000，平均数为20000/200=100。故必有某mi≥100。;[例2]假设序列S={a1,a2,…,amn+1}中的各数是不等的．m,n是正整数，那么S有一长度为m+1的严格递增序列或长度为n+1的递减子序列，而且S有一长度为m+1的递减子序列或长度为n+1的递增子序列。

[证]由S中的每个ai向后选取最长递增子序列，设其长度为li，从而得到序列L={l1,l2,…,lmn+1}．假设存在lk≥m+1那么结论成立。; 否那么，所有的li∈[1,m]，其中必有

个li相等．不妨设为