抽屉原理的公式是什么 抽屉原理的表现形式有哪些?

2022-12-01 08:52:19

1、知道抽屉数和至少数(同类),求物体时:物体数=(至少数-1)×抽屉数+1。当至少数为2时,物体数=抽屉数+1。

2、原理1:把多于n+1个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。

3、原理2:把多于mn(m乘n)+1(n不为0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于(m+1)的物体。

4、原理3:把无穷多件物体放入n个抽屉,则至少有一个抽屉里有无穷个物体。

表现形式

把它推广到一般情形有以下几种表现形式。

形式一:设把n+1个元素划分至n个集合中(A1,A2,…,An),用a1,a2,…,an分别表示这n个集合对应包含的元素个数,则:至少存在某个集合Ai,其包含元素个数值ai大于或等于2。

证明:(反证法)假设结论不成立,即对每一个ai都有ai<2,则因为ai是整数,应有ai≤1,于是有:

a1+a2+…+an≤1+1+…+1=n

所以,至少有一个ai≥2,即必有一个集合中含有两个或两个以上的元素。

形式二:设把nm+1个元素划分至n个集合中(A1,A2,…,An),用a1,a2,…,an表示这n个集合对应包含的元素个数,则:至少存在某个集合Ai,其包含元素个数值ai大于或等于m+1。

证明:(反证法)假设结论不成立,即对每一个ai都有ai

a1+a2+…+an≤m+m+…+m=nm

所以,至少有存在一个ai≥m+1

知识扩展——高斯函数[x]定义:对任意的实数x,[x]表示“不大于x的最大整数”。例如:[3.5]=3,[2.9]=2,[-2.5]=-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)=n

k个[n/k] ∴ a1+a2+…+ak

形式四:设把q1+q2+…+qn-n+1个元素分为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个i,使得ai大于或等于qi。

证明:(用反证法)假设结论不成立,即对每一个ai都有ai

于是有:a1+a2+…+an≤q1+q2+…+qn-n

所以,假设不成立,故必有一个i,在第i个集合中元素个数ai≥qi

形式五:证明:(用反证法)将无穷多个元素分为有限个集合,假设这有限个集合中的元素的个数都是有限个,则有限个有限数相加,所得的数必是有限数,这就与题设产生矛盾,所以,假设不成立,故必有一个集合含有无穷多个元素。(借由康托的无穷基数可将鸽巢原理推广到无穷集中。)

关闭
精彩放送