组合数学课件--第三章第四节鸽巢原理.ppt

* * 第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数 3.12 鸽巢原理 1、366个人中必然有至少两人生日相同(不包括闰年)； 2、抽屉里散放着10双手套，从中任意抽取11只，其中至少有两只是成双的； 3、某次会议有n位代表参加，则至少有两个人认识的人数是一样的； 4、任给5个整数，其中至少有3个数的和被3除尽； 鸽巢原理：n个鸽子巢，若有n+1只鸽子在里面，则至少有一个巢里的鸽子数不少于2。 抽屉原理：如果把n+1个物体放到n个抽屉里，则必有一个抽屉里至少放了两个物体。 3.12 鸽巢原理 3.13.1 任取11个数，求证其中至少有两个数它们的差是10的倍数。 证明： 一个数是不是10的倍数取决于这个数的个位数是不是0，是0就是10的倍数； 一个数的个位数只可能是0,1,...,9十个数，任取11个数，其中必有两个数个位数相同， 那么这两个数的差的个位数必然是0。 3.13 鸽巢原理举例 例3.13.2 设a1,a2,…,am。是正整数的序列，则至少存在整数k和L, 1≤k≤L≤m,使得和ak+ak+1+…+aL是m的倍数。 证明： 有两种可能： (1)若有一个sh是m的倍数，那么上式成立。 构造一个序列s1=a1,s2=a1+a2,s3=a1+a2+a3,…, sm=a1+a2+…+am ,则s1s2…sm 3.13 鸽巢原理举例 (2)设在上面的序列中没有任何一个元素是m的倍数， 序列s1=a1,s2=a1+a2,s3=a1+a2+a3,…, sm=a1+a2+…+am ,则s1s2…sm 假定上面的序列中所有的项都非m的倍数，也就是r1,r2,…,rm无一为0，而且所有rh均小于m。 3.13 鸽巢原理举例 令sh≡rh(mod m),其中h=1,2,3,…,m。 不超过m-1的正整数只有m-1个，其中至少存在一对rL与rk,满足rL=rk。即sL和sk满足 sk≡sL(mod m) 设Lk。 sL=a1+a2+…+ak+ak+1+…+aL -) sk=a1+a2+…+ak sL-sk= ak+1+…+aL sL-sk=0 (mod m) 也就是说：sL-sk= ak+1+…+aL是m倍数。 3.13 鸽巢原理举例 3.13.3,A是{1,2,...,2n}中任意n+1个数，试证至少存在一对a,b∈A使得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 鸽巢原理举例 例3.13.4 设a1,a2,…,a100是由1和2组成的序列，已知从其中任意一个数开始的连续10个数的和不超过16，即对于1≤i≤91,恒有ai+ai+1+…+ai+9≤16 则至少存在h和k，kh,使得 ah+1+…+ak=39 证明： s100=(a1+a2+…+a10)+ (a11+a12+…+a20)+… +(a91+a92+…+a100) 根据条件：s100≤10×16=160 作序列s1=a1, s2=a1+a2,…, s100=a1+a2+…+a100。由于每个ai都是正整数，因此： s1 s2… s100 3.13 鸽巢原理举例 作序列s1,s2 ,…,s100 ,s1+39, s2+39,…, s100+39,共200项。 最后一项s100+39≤160+39=199。 但序列共200项。是从1到199的正整数。根据鸽巢原理，其中必有两项相等。 但前100项严格单调递增，后100项也严格单调递增。 存在h和k，有 sk=sh+39,1≤h,k≤