1. 首页 > 育儿知识

什么是抽屉原理(什么是抽屉原理技术问题)

本篇文章给大家谈谈什么是抽屉原理,以及什么是抽屉原理技术问题对应的知识点,希望对各位有所帮助,不要忘了收藏本站喔。

本文目录一览:

什么是抽屉原理

桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。

抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。”

抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

第一抽屉原理:

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

证明(反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n×1,而不是题设的n+k(k≥1),故不可能。

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

证明(反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能。

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

原理1 、2 、3都是第一抽屉原理的表述。

第二抽屉原理:

把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体(例如,将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)。

扩展资料:

一般表述:

在上面的第一个结论中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉,至少有2个东西在同一抽屉里。

在第二个结论中,不妨想象将5双手套分别编号,即号码为1,2,...,5的手套各有两只,同号的两只是一双。任取6只手套,它们的编号至多有5种,因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉,至少有2个东西在同一抽屉里。

抽屉原理的一种更一般的表述为:

“把多于kn+1个东西任意分放进n个空抽屉(k是正整数),那么一定有一个抽屉中放进了至少k+1个东西。”

利用上述原理容易证明:“任意7个整数中,至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能,所以7个整数中至少有3个数除以3所得余数相同,即它们两两之差是3的倍数。

如果问题所讨论的对象有无限多个,抽屉原理还有另一种表述:

“把无限多个东西任意分放进n个空抽屉(n是自然数),那么一定有一个抽屉中放进了无限多个东西。”

用高斯函数来叙述一般形式的抽屉原理的是:将m个元素放入n个抽屉,则在其中一个抽屉里至少会有

[(m-1)/n]+1个元素。

抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。

这个问题可以用如下方法简单明了地证出:

在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人。如果两人以前彼此认识,那么就在代表他们的两点间连成一条红线;否则连一条蓝线。考虑A点与其余各点间的5条连线AB,AC,...,AF,它们的颜色不超过2种。

根据抽屉原理可知其中至少有3条连线同色,不妨设AB,AC,AD同为红色。

如果BC,BD ,CD 3条连线中有一条(不妨设为BC)也为红色,那么三角形ABC即一个红色三角形,A、B、C代表的3个人以前彼此相识:如果BC、BD、CD 3条连线全为蓝色,那么三角形BCD即一个蓝色三角形,B、C、D代表的3个人以前彼此不相识。

不论哪种情形发生,都符合问题的结论。

六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例,这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。从六人集会问题的证明中,我们又一次看到了抽屉原理的应用。

表现形式:

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

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

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

a1+a2+…+an≤1+1+…+1=nn+1,这与题设矛盾。

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

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

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

a1+a2+…+an≤m+m+…+m=nmnm+1,这与题设相矛盾。

所以,至少有存在一个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+…+akn 这与题设相矛盾。所以,必有一个集合中元素个数大于或等于[n/k]

形式四:设把q1+q2+…+qn-n+1个元素分

为n个集合A1,A2,…,An,用a1,a2,…,an表示这n个集合里相应的元素个数,需要证明至少存在某个i,使得ai大于或等于qi。

证明:(用反证法)假设结论不成立,即对每一个ai都有aiqi,因为ai为整数,应有ai≤qi-1,

于是有:a1+a2+…+an≤q1+q2+…+qn-n q1+q2+…+qn-n+1这与题设矛盾。

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

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

参考资料:

百度百科-抽屉原理

抽屉原理是什么?

抽屉原理

一、 知识要点

抽屉原理又称鸽巢原理,它是组合数学的一个基本原理,最先是由德国数学家狭利克雷明确地提出来的,因此,也称为狭利克雷原理.

把3个苹果放进2个抽屉里,一定有一个抽屉里放了2个或2个以上的苹果.这个人所皆知的常识就是抽屉原理在日常生活中的体现.用它可以解决一些相当复杂甚至无从下手的问题.

原理1:把n+1个元素分成n类,不管怎么分,则一定有一类中有2个或2个以上的元素.

原理2:把m个元素任意放入n(n<m=个集合,则一定有一个集合呈至少要有k个元素.

其中 k= (当n能整除m时)

〔 〕+1 (当n不能整除m时)

(〔 〕表示不大于 的最大整数,即 的整数部分)

原理3:把无穷多个元素放入有限个集合里,则一定有一个集合里含有无穷多个元素.

二、 应用抽屉原理解题的步骤

第一步:分析题意.分清什么是“东西”,什么是“抽屉”,也就是什么作“东西”,什么可作“抽屉”.

第二步:制造抽屉.这个是关键的一步,这一步就是如何设计抽屉.根据题目条件和结论,结合有关的数学知识,抓住最基本的数量关系,设计和确定解决问题所需的抽屉及其个数,为使用抽屉铺平道路.

第三步:运用抽屉原理.观察题设条件,结合第二步,恰当应用各个原则或综合运用几个原则,以求问题之解决.

例1、 教室里有5名学生正在做作业,今天只有数学、英语、语文、地理四科作业

求证:这5名学生中,至少有两个人在做同一科作业.

证明:将5名学生看作5个苹果

将数学、英语、语文、地理作业各看成一个抽屉,共4个抽屉

由抽屉原理1,一定存在一个抽屉,在这个抽屉里至少有2个苹果.

即至少有两名学生在做同一科的作业.

例2、 木箱里装有红色球3个、黄色球5个、蓝色球7个,若蒙眼去摸,为保证取出的球中有两个球的颜色相同,则最少要取出多少个球?

把3种颜色看作3个抽屉

若要符合题意,则小球的数目必须大于3

大于3的最小数字是4

故至少取出4个小球才能符合要求

答:最少要取出4个球.

例3、 班上有50名学生,将书分给大家,至少要拿多少本,才能保证至少有一个学生能得到两本或两本以上的书.

把50名学生看作50个抽屉,把书看成苹果

根据原理1,书的数目要比学生的人数多

即书至少需要50+1=51本

答:最少需要51本.

例4、 在一条长100米的小路一旁植树101棵,不管怎样种,总有两棵树的距离不超过1米.

把这条小路分成每段1米长,共100段

每段看作是一个抽屉,共100个抽屉,把101棵树看作是101个苹果

于是101个苹果放入100个抽屉中,至少有一个抽屉中有两个苹果

即至少有一段有两棵或两棵以上的树

例5、 11名学生到老师家借书,老师是书房中有A、B、C、D四类书,每名学生最多可借两本不同类的书,最少借一本

试证明:必有两个学生所借的书的类型相同

证明:若学生只借一本书,则不同的类型有A、B、C、D四种

若学生借两本不同类型的书,则不同的类型有AB、AC、AD、BC、BD、CD六种

共有10种类型

把这10种类型看作10个“抽屉”

把11个学生看作11个“苹果”

如果谁借哪种类型的书,就进入哪个抽屉

由抽屉原理,至少有两个学生,他们所借的书的类型相同

例6、 有50名运动员进行某个项目的单循环赛,如果没有平局,也没有全胜

试证明:一定有两个运动员积分相同

证明:设每胜一局得一分

由于没有平局,也没有全胜,则得分情况只有1、2、3……49,只有49种可能

以这49种可能得分的情况为49个抽屉

现有50名运动员得分

则一定有两名运动员得分相同

例7、 体育用品仓库里有许多足球、排球和篮球,某班50名同学来仓库拿球,规定每个人至少拿1个球,至多拿2个球,问至少有几名同学所拿的球种类是一致的?

解题关键:利用抽屉原理2.

根据规定,多有同学拿球的配组方式共有以下9种:

{足}{排}{蓝}{足足}{排排}{蓝蓝}{足排}{足蓝}{排蓝}

以这9种配组方式制造9个抽屉

将这50个同学看作苹果

=5.5……5

由抽屉原理2k=〔 〕+1可得,至少有6人,他们所拿的球类是完全一致的

什么是“抽屉原理”?

抽屉原理 原理:多于n个的球以任意方式全部放入n个抽屉中,一定存在一个抽屉,它里面有两个或两个以上的球。 1. 任意11个整数中,一定有两个数,它们的差是10的倍数。 2. 设任意n+1个实数在[0

1)中,求证在它们中存在两个数且它们的差少于1/n。 3. 在前10个自然数中任取6个数,求证:一定存在两个数,其中一个是另一个的整数倍(如果把10改为200,6改为101,则是莫斯科第10届奥林匹克竞赛竞赛题。) 4. 在前91个自然数中任取10个数,求证其中存在两个数,它们相互的比值在[2/3,3/2]内(苏联基辅第49届数学竞赛题)。 5. 任意m个整数,求证:一定可以从找到若干整数,使得它们的和可被m整数(若m=100则是第12届莫斯科奥林匹克数学竞赛题)。 6. 任意给定10自然数,试证明:可以用减、乘两种运算把它们适当连起来,其结果能被1890整除。 其中一种简单的表述法为: 若有n个笼子和n+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少2只鸽子。 或者这么说: 若有K个笼子和KN+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少k+1只鸽子。

鸽巢原理,又名狄利克雷抽屉原理、鸽笼原理。 其中一种简单的表述法为: 若有n个笼子和n+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少2只鸽子。 或者这么说: 若有n个笼子和kn+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少k+1只鸽子。 拉姆齐定理是此原理的推广。 抽屉原理 原理一:如果把n+1个元素放入n个 *** 中,则至少有一个 *** 中有2个或2个以上的元素。 原理二:把m个元素任意放入n (mn) 个 *** 中,则至少有一个 *** 中含有k个或k个以上的元素,其中 (i) k=m/n 当n能整除m; (ii) k=[m/n]+1 当n不能整除m。 原理三:把无穷多个元素放入有限个 *** 里,则至少存在一个 *** 中个有无穷多个元素。 例题 在边长为2的正方形中,任意取5点,求证:至少有两个点之间的距离不大于√2。 在边长为1的正方形中,任意放入9个点,求证:在以这些点为顶点的诸多三角形中,必有一个三角形的面积不超过 1/8。 在直径为5的圆中放入10个点,求证:其中必有两个点的距离小于2。 求证:在任意给出的5个数中,必有3个数,其和能被3整除。 任给12个整数,求证:其中必有两个数,它们的和或者差恰是20的倍数。 证明:从任意给定的n个不同的自然数中,总能找到若干个,使它们的和是n的倍数。 求证:在任意给出的12个数中,一定存在8个整数,记为a1

a2

...

a8使得 (a1-a2)(a3-a4)(a5-a6)(a7-a8)能被1155整除。 已知7个自然数a1

a2

...

a7,把它们重新排列后得到b1

b2

...

b7,求证:(a1-b1)(a2-b2)...(a7-b7)为偶数。 在直角坐标系中,把横纵坐标全是整数的点称为整点。在坐标平面上任意给定5个整点,求证:其中一定有两个点,它们的联线中点仍为整点。 求证:在1

4

7

10

...

100中任选20个数,其中至少有不同的两组数,其和全等于104。 从自然数1

2

...

99

100中,任意取出51个数,求证:其中一定有两个数,它们中的一个是另一个的倍数。 任选6个人,试证:其中必有3人,他们相互认识或都不认识。 一个由21个小正方形组成的3x7矩形,任意给每一个小正方形任意涂上红色或蓝色,证明:不论怎样涂色,总可在图中找出一个矩形,它的4个角上的小正方形的颜色相同。 在平面上给出1993个点,并且从中任取3个点,其中就有两个点的距离小于1。证明:存在一个半径为1的圆,它至少包含了给出的1993个点中的997个点。 图片参考:geo.yahoo/serv?s=382076083t=1166921882f=-w63 『抽屉原理』是数学名家狄利克雷的著作,是一种重要的思考方法。关键是构造抽屉求出最少的抽屉

抽屉原理是什么意思?

抽屉原理:桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放不少于两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

扩展资料:

运用抽屉原理的核心是分析清楚问题中,哪个是物件,哪个是抽屉。例如,属相是有12个,那么任意37个人中,至少有一个属相是不少于4个人。这时将属相看成12个抽屉,则一个抽屉中有 37/12,即3余1,余数不考虑,而向上考虑取整数,所以这里是3+1=4个人,但这里需要注意的是,前面的余数1和这里加上的1是不一样的。

因此,在问题中,较多的一方就是物件,较少的一方就是抽屉,比如上述问题中的属相12个,就是对应抽屉,37个人就是对应物件,因为37相对12多。

参考资料来源:百度百科-抽屉原理

参考资料来源:百度百科-狄利克雷

什么是抽屉原理的介绍就聊到这里吧,感谢你花时间阅读本站内容,更多关于什么是抽屉原理技术问题、什么是抽屉原理的信息别忘了在本站进行查找喔。

本文由发布,不代表思恒百科立场,转载联系作者并注明出处:https://www.pneumabooks.com/yuerzhishi/68187.html

留言与评论(共有 0 条评论)
   
验证码:

联系我们

在线咨询:点击这里给我发消息

微信号:weixin888

工作日:9:30-18:30,节假日休息