《组合数学课件--第三章第四节鸽巢原理》由会员分享，可在线阅读，更多相关《组合数学课件--第三章第四节鸽巢原理（38页珍藏版）》请在金锄头文库上搜索。
1、1,第3章 容斥原理与鸽巢原理,3.1 De Morgan定理 3.2 容斥原理 3.3 容斥原理举例 3.4 棋盘多项式与有限制的排列 3.5 有禁区的排列 3.6 广义的容斥原理 3.7 广义容斥原理的应用 2.8 第二类Stirling数的展开式 2.9 欧拉函数(n) 2.10 n对夫妻问题 *2.11 Mobius反演定理 2.12 鸽巢原理 2.13 鸽巢原理举例 2.14 鸽巢原理的推广 *2.15 Ramsey数,2,3.12 鸽巢原理,1、366个人中必然有至少两人生日相同(不包括闰年)； 2、抽屉里散放着10双手套，从中任意抽取11只，其中至少有两只是成双的； 3、某次会议
2、有n位代表参加，则至少有两个人认识的人数是一样的； 4、任给5个整数，其中至少有3个数的和被3除尽；,3,鸽巢原理：n个鸽子巢，若有n+1只鸽子在里面，则至少有一个巢里的鸽子数不少于2。,抽屉原理：如果把n+1个物体放到n个抽屉里，则必有一个抽屉里至少放了两个物体。,3.12 鸽巢原理,4,3.13.1 任取11个数，求证其中至少有两个数它们的差是10的倍数。,证明：,一个数是不是10的倍数取决于这个数的个位数是不是0，是0就是10的倍数；,一个数的个位数只可能是0,1,.,9十个数，任取11个数，其中必有两个数个位数相同，,那么这两个数的差的个位数必然是0。,3.13 鸽巢原理举例,5,例3
3、.13.2 设a1,a2,am。是正整数的序列，则至少存在整数k和L, 1kLm,使得和ak+ak+1+aL是m的倍数。,证明：,有两种可能：,(1)若有一个sh是m的倍数，那么上式成立。,构造一个序列s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am ,则s1s2sm,3.13 鸽巢原理举例,6,(2)设在上面的序列中没有任何一个元素是m的倍数，,序列s1=a1,s2=a1+a2,s3=a1+a2+a3,sm=a1+a2+am ,则s1s2k。 sL=a1+a2+ak+ak+1+aL -) sk=a1+a2+ak sL-sk= ak+1+aL,sL-sk=0 (mo
4、d m) 也就是说：sL-sk= ak+1+aL是m倍数。,3.13 鸽巢原理举例,8,3.13.3,A是1,2,.,2n中任意n+1个数，试证至少存在一对a,bA使得a与b互素。,相邻数互素；,证明：,从A中任意取n+1个数，必有两个数相邻，相邻数互素；,设这n+1个数为a1,a2,an+1，如果两两不相邻；,构造序列a1,a1+1,a2,a2+1,an,an+1,an+1，是2n+1个不同的正整数；,与已知条件矛盾。,3.13 鸽巢原理举例,9,例3.13.4 设a1,a2,a100是由1和2组成的序列，已知从其中任意一个数开始的连续10个数的和不超过16，即对于1i91,恒有ai+ai+
5、1+ai+916 则至少存在h和k，kh,使得 ah+1+ak=39,证明：,s100=(a1+a2+a10)+ (a11+a12+a20)+ +(a91+a92+a100)根据条件：s1001016=160,作序列s1=a1, s2=a1+a2, s100=a1+a2+a100。由于每个ai都是正整数，因此： s1 s29n-36,X的非空子集的数目？,C(9,1)+C(9,2)+C(9,9),X的任何子集的元素和都小于或等于9n-36,解这个不等式可得：n60.77 n是正整数，因此n60 因此：9n60。,=29-1=511,3.13 鸽巢原理举例,*,16,3.14 鸽巢原理的推广,推
6、广形式之一,设k和n都是任意的正整数，若至少有kn+1只鸽子分配在n个鸽巢里，则至少存在一个鸽巢中有不少于k+1只鸽子。,推论3.7 m只鸽子，n个鸽巢，则至少有一个鸽巢里有不少于,只鸽子。,17,推论3.8 若取n(m-1)+1个球放进n个盒子，则至少有1个盒子的球数不少于m个。,推论3.9 若m1,m2,mn是n个正整数，而且,则m1,m2,mn中至少有1个数不小于r。,3.14 鸽巢原理的推广,18,例3.14.8：设A= a1a2a20是10个0和10个1组成的20位进制数。B=b1b2b20是任意的20位2进制数。C=b1b2b20b1b2b20= C1C2C40,则存在某个i,1i
7、21,使得CiCi+1Ci+19与a1a2a20至少有10位对应数字相同。,.,.,.,.,.,.,A,C,第 i 格,第 i +19格,1 2 19 20 1 2 19 20,1 2 19 20 1 19 20,B,3.14 鸽巢原理的推广,19,.,A,1 2 19 20,4、因此必有一次相同数字的格数不少于10位,1、假想着A如图所示从左向右一格一格移动。,2、在移动到最后时。每一个bj都遍历了a1,a2,a20。因为A中有10个0和10个1，每一个bj都有10位次对应相等。,3、在20次的移动过程中共有1020=200位次对应相等。,3.14 鸽巢原理的推广,20,定理.7若序列,的n
8、2+1个元素是不相等的实数，则从这个序列中至少可选出一组由n+1个元素组成的或为单调增或为单调减的子序列。,例如：对于序列：5,3,16,10,15,14,9,11,6,7。共32+1个元素。,证明1：从序列中的每一个元素ai向后可选出若干个单调增子序列，其中有一个元素最多的单调增子序列，设其元素个数为li,i=1,2,n2+1,于是得一序列,3.14 鸽巢原理的推广,21,1：若序列(L)中有一个元素lkn+1,则定理得证。,2：设不存在元素个数超过n的单调增子序列，即:,根据鸽巢原理的推论3.7，至少存在n+1个：,的值相等,3.14 鸽巢原理的推广,22,设k1k2kn+1 ,已知条件中
9、al是不同的实数，则有如下结论,如若不然，设kikj,有akiakj,从akj开始向后的最长的单调增序列为l，从aki开始向后的最长的单调增序列也是l，,如果把元素aki加到从akj开始的长度为l的单调增序列的前面，构成从aki开始的长度为l+1的单调增序列，这和l是从aki向后的最长单调增序列的假设矛盾。,3.14 鸽巢原理的推广,23,序列(A)是一个单调减子序列，这就证明了若不存在n+1个元素的单调增子序列，便存在一个有n+1个元素的单调减子序列。,3.14 鸽巢原理的推广,24,例3.14.9：随意地给正十边形的10个顶点编上号码1,2,3,4,5,6,7,8,9,10,求证：必有一个
10、顶点及与之相邻的两顶点之和不小于17。,证明：以A1,A2,A3,A10表示正十边形的10个顶点，,以qi表示顶点Ai与Ai相邻的两顶点号码之和,求qi,=(1+2+10)3=165,3.14 鸽巢原理的推广,因此必存在qi17,25,例3.14.10：下图中画出了3行9列共27个小方格，将每一个方格涂上红色或者蓝色，证明：无论如何涂色，其中必有至少两列它们的涂色方式完全相同。,解：每个方格的涂色方案有红和蓝2种，每列有3个格子，因此每列有：,222=8种涂色方案。,现在有9列，根据鸽巢原理，必有至少两列它们的涂色方式完全相同。,3.14 鸽巢原理的推广,26,3.57,n是大于等于3的整数，
11、则下列数的集合：2-1,22-1,23-1,.,2n-1-1中存在一数被n除尽。,首先这是n-1个奇数，假如n是偶数时，不可能成立；,当n=4时，数列为1，3，7不可能被4除尽。,3.14 鸽巢原理的推广,27,3.57,n是大于1的奇数，则下列数的集合：2-1,22-1,23-1,.,2n-1-1,2n-1中至少存在一数被n除尽。,证：,2-1,22-1,23-1,.,2n-1-1,2n-1整除n可得n个余数，,除以n的余数共有0,1,2,n-1个。,如果2-1,22-1,23-1,.,2n-1-1,2n-1除以n所得余数互不相等,则结论成立。,否则：,3.14 鸽巢原理的推广,28,设a,bn,ab, 2a-1(modn)=2b-1(modn)=r,
