抽屉原理（二）.doc

抽屉原理
把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。
抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
形式一:
证明:设把n+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个ai大于或等于2
(用反证法)假设结论不成立,即对每一个ai都有ai<2,则因为ai是整数,应有ai≤1,于是有:
a1+a2+…+an≤1+1+…+1=n<n+1
这与题设矛盾。
所以,至少有一个ai≥2,即必有一个集合中含有两个或两个以上的元素。
形式二:
设把n·m+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个ai大于或等于m+1。
(用反证法)假设结论不成立,即对每一个ai都有ai<m+1,则因为ai是整数,应有ai≤m,于是有:
a1+a2+…+an≤m+m+…+m=n·m
n个m
<n·m+1
这与题设相矛盾。
所以,至少有存在一个ai≥m+1
高斯函数:
对任意的实数x,
[x]表示“不大于x的最大整数”.
例如:[]=3,[]=2,
[-]=-3,[7]=7,……
一般地,我们有:[x]≤x<[x]+1
形式三:
证明:设把n个元素分为k个集合A1,A2,…,Ak,用a1,a2,…,ak表示这k个集合里相应的元素个数,需要证明至少存在某个ai大于或等于[n/k]。
(用反证法)假设结论不成立,即对每一个ai都有ai<[n/k],于是有:
a1+a2+…+ak<[n/k]+[n/k]+…+[n/k]
k个[n/k]
=k·[n/k]≤k·(n/k)=n
∴ a1+a2+…+ak<n
这与题设相矛盾。
所以,必有一个集合中元素个数大于或等于[n/k]
形式四:
证明:设把q1+q2+…+qn-n+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个i,使得ai大于或等于qi。
(用反证法)假设结论不成立,即对每一个ai都有ai<qi,因为ai为整数,应有ai≤qi-1,于是有:
a1+a2+…+an≤q1+q2+…+qn-n
<q1+q2+…+qn-n+1
这与题设矛盾。
所以,假设不成立,故必有一个i,在第i个集合中元素个数ai≥qi
形式五:
证明:(用反证法)将无穷多个元素分为有限个集合,假设这有限个集合中的元素的个数都是有限个,则有限个有限数相加,所得的数必是有限数,这就与题设产生矛盾,所以,假设不成立,故必有一个集合含有无穷多个元素。
例题1:400人中至少有两个人的生日相同.
分析:生日从1月1日排到12月31日,共有366个不相同的生日,我们把366个不同的生日看作366个抽屉,400人视为400个苹果,由表现形式1可知,至少有两人在同一个抽屉里,所以这400人中有两人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个苹果,由抽