文档介绍：第3章容斥原理与鸽巢原理
De Morgan定理
容斥原理
容斥原理举例
棋盘多项式与有限制的排列
有禁区的排列
广义的容斥原理
广义容斥原理的应用
第二类Stirling数的展开式
欧拉函数(n)
n对夫妻问题
* Mobius反演定理
鸽巢原理
鸽巢原理举例
鸽巢原理的推广
* Ramsey数
1
鸽巢原理
1、366个人中必然有至少两人生日相同(不包括闰年);
2、抽屉里散放着10双手套,从中任意抽取11只,其中至少有两只是成双的;
3、某次会议有n位代表参加,则至少有两个人认识的人数是一样的;
4、任给5个整数,其中至少有3个数的和被3除尽;
2
鸽巢原理:n个鸽子巢,若有n+1只鸽子在里面,则至少有一个巢里的鸽子数不少于2。
抽屉原理:如果把n+1个物体放到n个抽屉里,则必有一个抽屉里至少放了两个物体。
鸽巢原理
3
任取11个数,求证其中至少有两个数它们的差是10的倍数。
证明:
一个数是不是10的倍数取决于这个数的个位数是不是0,是0就是10的倍数;
一个数的个位数只可能是0,1,...,9十个数,任取11个数,其中必有两个数个位数相同,
那么这两个数的差的个位数必然是0。
鸽巢原理举例
4
设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 ,则s1<s2<…<sm
鸽巢原理举例
5
(2)设在上面的序列中没有任何一个元素是m的倍数,
序列s1=a1,s2=a1+a2,s3=a1+a2+a3,…,
sm=a1+a2+…+am ,则s1<s2<…<sm
假定上面的序列中所有的项都非m的倍数,也就是r1,r2,…,rm无一为0,而且所有rh均小于m。
鸽巢原理举例
令sh≡rh(mod m),其中h=1,2,3,…,m。
6
不超过m-1的正整数只有m-1个,其中至少存在一对rL与rk,满足rL=rk。即sL和sk满足
sk≡sL(mod m)
设L>k。
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倍数。
鸽巢原理举例
7
,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个不同的正整数;
与已知条件矛盾。
鸽巢原理举例
8
设a1,a2,…,a100是由1和2组成的序列,已知从其中任意一个数开始的连续10个数的和不超过16,即对于1≤i≤91,恒有ai+ai+1+…+ai+9≤16
则至少存在h和k,k>h,使得
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
鸽巢原理举例
9
作序列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≤100
则:sk-sh=39
即:a1+a2+…+ak-(a1+a2+…+ah)=39也就是
ah+1+ah+2+…+ak=39
鸽巢原理举例
10