如果物体的个数比抽屉多两个、三个、四个、我们又能得出什么结论呢的答案?
抽屉原理 - 基本简介
抽屉原理图册
“任意367个人中,必有生日相同的人。”
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
大家都会认为上面所述结论是正确的。这些结论是依据什么原理得出的呢?这个原理叫做抽屉原理。“抽屉原理”最先是由19世纪的德国数学家迪里赫莱(Dirichlet)运用于解决数学问题的,所以又称“迪里赫莱原理”,也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果,任意分放在9个抽屉里,则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的,但应用它却可以解决许多有趣的问题,并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类数学竞赛中的重要内容, 它的内容可以用形象的语言表述为:
“把m个东西任意分放进n个空抽屉里(m>n),那么一定有一个抽屉中放进了至少2个东西。”
在上面的第一个结论中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉,至少有2个东西在同一抽屉里。在第二个结论中,不妨想象将5双手套分别编号,即号码为1,2,...,5的手套各有两只,同号的两只是一双。任取6只手套,它们的编号至多有5种,因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉,至少有2个东西在同一抽屉里。
第一抽屉原理
原理1: 把多于n+1个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。
证明(反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),故不可能。
原理2 :把多于mn(m乘以n)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于m+1的物体。
证明(反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能。
原理3 :把无穷多件物体放入n个抽屉,则至少有一个抽屉里 有无穷个物体。
原理1 、2 、3都是第一抽屉原理的表述。
第二抽屉原理
把(mn——1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体(例如,将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)。
证明(反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能。
抽屉原理 - 证明
这个问题可以用如下方法简单明了地证出:
在平面上用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个人以前彼此不相识。不论哪种情形发生,都符合问题的结论。
六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例,这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。从六人集会问题的证明中,我们又一次看到了抽屉原理的应用。
抽屉原理 - 一般表述
在上面的第一个结论中,由于一年最多有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都有ai<2,则因为ai是整数,应有ai≤1,于是有:
a1+a2+…+an≤1+1+…+1=n<n+1,这与题设矛盾。
所以,至少有一个ai≥2,即必有一个集合中含有两个或两个以上的元素。
形式二:设把nm+1个元素划分至n个集合中(A1,A2,…,An),用a1,a2,…,an表示这n个集合对应包含的元素个数,则:至少存在某个集合Ai,其包含元素个数值ai大于或等于m+1。
证明:(反证法)假设结论不成立,即对每一个ai都有ai<m+1,则因为ai是整数,应有ai≤m,于是有:
a1+a2+…+an≤m+m+…+m=nm<nm+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+…+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.抽屉原则有几种最常见的形式: 原则1 如果把n+k(k≥1)个物体放进n只抽屉里,则至少有一只抽屉要放进两个或更多个物体: ____原则本身十分浅显,为了加深对它的认识,我们还是运用反证法给予证明;如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.原则虽简单.巧妙地运用原则却可十分便利地解决一些看上去相当复杂、甚至感到无从下手的总是,比如说,我们可以断言在我国至少有两个人出生的时间相差不超过4秒钟,这是个惊人的结论,该是经过很多人的艰苦劳动,统计所得的吧!不,只须我们稍动手算一下:不妨假设人的寿命不超过4万天(约110岁,超过这个年龄数的人为数甚少),则10亿人口安排在8亿6千4百万个“抽屉”里,根据原则1,即知结论成立. 下面我们再举一个例子: 例1 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理. 解 从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原则1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同。 原则2 如果把mn+k(k≥1)个物体放进n个抽屉,则至少有一个抽屉至多放进m+1个物体.证明同原则相仿.若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能。原则1可看作原则2的物例(m=1) 例2 正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同. 证明把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原则二,至少有三个面涂上相同的颜色。 例3 把1到10的自然数摆成一个圆圈,证明一定存在在个相邻的数,它们的和数大于17. 证明 如图12-1,设a1,a2,a3,…,a9,a10分别代表不超过10的十个自然数,它们围成一个圈,三个相邻的数的组成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5),…,(a9,a10,a1),(a10,a1,a2)共十组.现把它们看作十个抽屉,每个抽屉的物体数是a1+a2+a3,a2+a3+a4,a3+a4+a5,…a9+a10+a1,a10+a1+a2,由于 (a1+a2+a3)+(a2+a3+a4)+…+(a9+a10+a1)+(a10+a1+a2) =3(a1+a2+…+a9+a10) =3×(1+2+…+9+10) ____根据原则2,至少有一个括号内的三数和不少于17,即至少有三个相邻的数的和不小于17.原则1、原则2可归结到期更一般形式: 原则3 把m1+m2+…+mn+k(k≥1)个物体放入n个抽屉里,那么或在第一个抽屉里至少放入m1+1个物体,或在第二个抽屉里至少放入m2+1个物体,……,或在第n个抽屉里至少放入mn+1个物体。 证明 假定第一个抽屉放入物体的数不超过m1个,第二个抽屉放入物体的数不超过m2个,……,第n个抽屉放入物体的个数不超过mn,那么放入所有抽屉的物体总数不超过m1+m2+…+mn个,与题设矛盾。 例4 有红袜2双,白袜3双,黑袜4双,黄袜5双,蓝袜6双(每双袜子包装在一起)若取出9双,证明其中必有黑袜或黄袜2双。 证明 除可能取出红袜、白袜3双外.还至少从其它三种颜色的袜子里取出4双,根据原理3,必在黑袜或黄袜、蓝袜里取2双。上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少。 2.制造抽屉是运用原则的一大关键 ____首先要指出的是,对于同一问题,常可依据情况,从不同角度设计抽屉,从而导致不同的制造抽屉的方式. 例5 在边长为1的正方形内,任意给定13个点,试证:其中必有4个点,以此4点为顶点的四边开面积不超过 (假定四点在一直线上构成面积为零的四边形). 证明 如图12-2把正方形分成四个相同的小正方形。因13=3×4+1,根据原则2,总有4点落在同一个小正方形内(或边界上),以此4点为顶点的四边形的面积不超过小正方形的面积,也就不超过整个正方形面积的 。事实上,由于解决问题的核心在于将正方形分割成四个面积相等的部分,所以还可以把正方形按图12-3(此处无图)所示的形式分割. ____合理地制造抽屉必须建立在充分考虑问题自身特点的基础上. 例6 在一条笔直的马路旁种树,从起点起,每隔一米种一棵树,如果把三块“爱护树木”的小牌分别挂在三棵树上,那么不管怎样挂,至少有两棵挂牌的树之间的距离是偶数(以米为单位),这是为什么? 解 如图12-4(设挂牌的三棵树依次为A、B、C.AB=a,BC=b,若a、b中有一为偶数,命题得证.否则a、b均为奇数,则AC=a+b为偶数,命题得证.换一个角度考虑:给每棵树上编上号,于是两棵树之间的距离就是号码差,由于树的号码只能为奇数和偶数两类,那么挂牌的三棵树号码至少有两个同为奇数或偶数,它们的差必为偶数,问题得证.后一证明十分巧妙,通过编号码,将两树间距离转化为号码差.这种转化的思想方法是一种非常重要的数学方法 例7 从自然数1,2,3,…99,100这100个数中随意取出51个数来,求证:其中一定有两个数,,它们中的一个是另一个的倍数. 分析设法制造抽屉:(1)不超过50个;(2)每个抽屉的里的数(除仅有的一个外),其中一个数是另一个数的倍数,一个自然数的想法是从数的质因数表示形式入手. 解 设第一个抽屉里放进数:1,1×2,1×22,1×23,1×24,1×25,1×26;第二个抽屉时放进数:3,3×2,3×22,3×23,3×24,3×25;第三个抽屉里放进数:5,5×2,5×22,5×23,5×24;………………第二十五个抽屉里放进数:49,49×2;第二十六个抽屉里放进数:51.………………第五十个抽屉里放进数:99.那么随意取出51个数中,必有两个数同属一个抽屉,其中一个数是另一个数的倍数.制造抽屉并非总是一帆风顺的,有时要边制造边调整、改进. 例8 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数. 分析注意到这些数队以10的余数即个位数字,以0,1,…,9为标准制造10个抽屉,标以[0],[1],…,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数. 3.较复杂的问题须反复地运用抽屉原则,将复杂问题转化为简单问题. 例9 以(x,y,z)表示三元有序整数组,其中x、y、z为整数,试证:在任意七个三元整数组中,至少有两个三元数组,它们的x、y、z元中有两对都是奇数或都是偶数. 分析 设七个三元素组为A1(x1,y1,z1)、A2(x2,y2,z2)、…、A7(x7,y7,z7).现在逐步探索,从x元开始,由抽屉原则,x1,x2,…,x7这七个数中,必定有四个数具有相同的奇偶性,不妨设这四个数是x1,x2,x3,x4且为偶数,接着集中考虑A1、A2、A3、A4这四组数的y元,若比如y1,y2,y3,y4中有两个是偶数,则问题已证,否则至多有一个是偶数,比如y4是偶数,这时我们再来集中考虑A1、A2、A3的z元.在z1,z2,z3中,由抽屉原则必有两个数具有相同的奇偶性,如z1、z2,这时无论它们是奇数,还是偶数,问题都已得到证明. 下面介绍一个著名问题. 例10 任选6人,试证其中必有3人,他们互相认识或都不认识. 分析 用A、B、C、D、E、F表示这6个人,首先以A为中心考虑,他与另外五个人B、C、D、E、F只有两种可能的关系:认识或不认识,那么由抽屉原则,他必定与其中某三人认识或不认识,现不妨设A认识B、C、D三人,当B、C、D三人都互不认识时,问题得证;当B、C、D三人中有两人认识,如B、C认识时,则A、B、C互相认识,问题也得证.本例和上例都采用了舍去保留、化繁为简、逐步缩小考虑范围的方法. 例11 a,b,c,d为四个任意给定的整数,求证:以下六个差数b-a,c-a,d-a,c-b,d-b,d-c的乘积一定可以被12整除. 证明 把这6个差数的乘积记为p,我们必须且只须证明:3与4都可以整除p,以下分两步进行. 第一步,把a,b,c,d按以3为除数的余数来分类,这样的类只有三个,故知a,b,c,d中至少有2个除以3的余数相同,例如,不妨设为a,b,这时3可整除b-a,从而3可整除p. 第二步,再把a,b,c,d按以4为除数的余数来分类,这种类至多只有四个,如果a,b,c,d中有二数除以4的余数相同,那么与第一步类似,我们立即可作出4可整除p的结论. 设a,b,c,d四数除以4的余数不同,由此推知,a,b,c,d之中必有二个奇数(不妨设为a,b),也必有二个偶数(设为c,d),这时b-a为偶数,d-c也是偶数,故4可整除(b-a)(d-c),自然也可得出4可整除p.如果能进一步灵活运用原则,不仅制造抽屉,还根据问题的特征,制造出放进抽屉的物体,则更可收到意想不到的效果. 例12 求证:从任意n个自然数a1,a2,…,an中可以找到若干个数,使它们的和是n的倍数. 分析以0,1,…,n-1即被n除的余数分类制造抽屉的合理的,但把什么样的数作为抽屉里的物体呢?扣住“和”,构造下列和数: S1=a1, S2=a1+a2, S=a1+a2+a3, ………… Sn=a1+a2+…+an, 其中任意两个和数之差仍为和数,若他们之中有一是n的倍数,问题得证,否则至少有两个数被n除余数相同,则它们的差即它们中若干数(包括1个)的和是n的倍数,问题同样得证. 例子3 910瓶红、蓝墨水,排成130行,每行7瓶,证明:不论怎样排列,红蓝墨水瓶的颜色次序必定出现下述两种情况之一种:(1)至少有三行完全相同;(2)至少有两组(四行)每组的两行完全相同. 解 910瓶红、蓝墨水排成130行,每行7瓶,对一行来说,每个位置上有红蓝两种可能,因此,一行的红、蓝墨水排法有27=128种,对每一种不同排法设为一种“行式”,共有128种行式.现有130行,在其中任取129行,依抽屉原则知,必有两行A、B行式相同.除A、B外余下128行,若有一行P与A行式相同,知满足(1)至少有三行A、B、P完全相同,若在这128行中设直一行5A行或相同,那么这128行至多有127种行式,依抽屉原则,必有两行C、D具有相同行式,这样便找到了(A、B),(C、D)两组(四行),且两组两行完全相同. http://www.mathfan.com/Soft/jstd/jsjc/as/200405/221.html
补充:
抽屉原则(又称抽屉原理) chōu tì yuán zé 抽屉原则,又叫狄利克雷原则,或“鸽笼原则”、“重叠原则”。将m件物品按任何方式放入n(n<m)个抽屉,则必至少有一个抽屉里放有两件或两件以上的物品。可用于解决许多数学问题。
目录
举例
常见形式
原则1
原则2
原则3
制造抽屉
例5
例6
例7
例8
例9
例10
例11
例12
例13
举例
常见形式
原则1
原则2
原则3
制造抽屉
例5
例6
例7
例8
例9
例10
例11
例12
例13
展开
编辑本段举例 大家知道,两个抽屉要放置三只苹果,那么一定有两只苹果放在同一个抽屉里,更一般地说,只要被放置的苹果数比抽屉数目大,就一定会有两只或更多只的苹果放进同一个抽屉,可不要小看这一简单事实,它包含着一个重要而又十分基本的原则——抽屉原则. 编辑本段常见形式 抽屉原则有几种最常见的形式: 原则1 如果把n+k(k≥1)个物体放进n只抽屉里,则至少有一只抽屉要放进两个或更多个物体: 原则本身十分浅显,为了加深对它的认识,我们还是运用反证法给予证明;如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能. 原则虽简单.巧妙地运用原则却可十分便利地解决一些看上去相当复杂、甚至感到无从下手的问题,比如说,我们可以断言在我国至少有两个人出生的时间相差不超过4秒钟,这是个惊人的结论,该是经过很多人的艰苦劳动,统计所得的吧!不,只须我们稍动手算一下:不妨假设人的寿命不超过4万天(约110岁,超过这个年龄数的人为数甚少),则10亿人口安排在8亿6千4百万个“抽屉”里,根据原则1,即知结论成立. 下面我们再举一个例子: 例1 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理. 解 从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原则1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同。 原则2 如果把mn+k(k≥1)个物体放进n个抽屉,则至少有一个抽屉至多放进m+1个物体. 证明同原则相仿.若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能。原则1可看作原则2的物例(m=1) 例2 正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同. 证明把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原则二,至少有三个面涂上相同的颜色。 例3 把1到10的自然数摆成一个圆圈,证明一定存在三个相邻的数,它们的和数大于17. 证明 设a1,a2,a3,…,a9,a10分别代表不超过10的十个自然数,它们围成一个圈,三个相邻的数的组成是(a1,a2,a3),(a2,a3,a4),(a3,a4,a5),…,(a9,a10,a1),(a10,a1,a2)共十组.现把它们看作十个抽屉,每个抽屉的物体数是a1+a2+a3,a2+a3+a4,a3+a4+a5,…a9+a10+a1,a10+a1+a2,由于 (a1+a2+a3)+(a2+a3+a4)+…+(a9+a10+a1)+(a10+a1+a2) =3(a1+a2+…+a9+a10) =3×(1+2+…+9+10) =165=16*10+5(m=16,k=5) 根据原则2,至少有一个括号内的三数和不少于17,即至少有三个相邻的数的和不小于17. 原则1、原则2可归结到更一般形式: 原则3 把m1+m2+…+mn+k(k≥1)个物体放入n个抽屉里,那么或在第一个抽屉里至少放入m1+1个物体,或在第二个抽屉里至少放入m2+1个物体,……,或在第n个抽屉里至少放入mn+1个物体。 证明 假定第一个抽屉放入物体的数不超过m1个,第二个抽屉放入物体的数不超过m2个,……,第n个抽屉放入物体的个数不超过mn,那么放入所有抽屉的物体总数不超过m1+m2+…+mn个,与题设矛盾。 例4 有红袜2双,白袜3双,黑袜4双,黄袜5双,蓝袜6双(每双袜子包装在一起)若取出9双,证明其中必有黑袜、蓝袜或黄袜2双。 证明 除可能取出红袜2双、白袜3双外.还至少从其它三种颜色的袜子里取出4双,根据原理3,必在黑袜或黄袜、蓝袜里取2双。上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少。 编辑本段制造抽屉 制造抽屉是运用原则的一大关键 ____首先要指出的是,对于同一问题,常可依据情况,从不同角度设计抽屉,从而导致不同的制造抽屉的方式. 例5 在边长为1的正方形内,任意给定13个点,试证:其中必有4个点,以此4点为顶点的四边形面积不超过 1/4(假定四点在一直线上构成面积为零的四边形). 证明 如图12-2把正方形分成四个相同的小正方形。因13=3×4+1,根据原则2,总有4点落在同一个小正方形内(或边界上),以此4点为顶点的四边形的面积不超过小正方形的面积,也就不超过整个正方形面积的 1/4。事实上,由于解决问题的核心在于将正方形分割成四个面积相等的部分,所以还可以把正方形按图12-3(此处无图)所示的形式分割. ____合理地制造抽屉必须建立在充分考虑问题自身特点的基础上. 例6 在一条笔直的马路旁种树,从起点起,每隔一米种一棵树,如果把三块“爱护树木”的小牌分别挂在三棵树上,那么不管怎样挂,至少有两棵挂牌的树之间的距离是偶数(以米为单位),这是为什么? 解 如图12-4(设挂牌的三棵树依次为A、B、C.AB=a,BC=b,若a、b中有一为偶数,命题得证.否则a、b均为奇数,则AC=a+b为偶数,命题得证. 换一个角度考虑:给每棵树上编上号,于是两棵树之间的距离就是号码差,由于树的号码只能为奇数和偶数两类,那么挂牌的三棵树号码至少有两个同为奇数或偶数,它们的差必为偶数,问题得证. 后一证明十分巧妙,通过编号码,将两树间距离转化为号码差.这种转化的思想方法是一种非常重要的数学方法. 例7 从自然数1,2,3,…99,100这100个数中随意取出51个数来,求证:其中一定有两个数,它们中的一个是另一个的倍数. 分析设法制造抽屉: (1)不超过50个; (2)每个抽屉的里的数(除仅有的一个外),其中一个数是另一个数的倍数,一个自然数的想法是从数的质因数表示形式入手. 解 设第一个抽屉里放进数:1,1×2,1×22,1×23,1×24,1×25,1×26;第二个抽屉时放进数:3,3×2,3×22,3×23,3×24,3×25;第三个抽屉里放进数:5,5×2,5×22,5×23,5×24;………………第二十五个抽屉里放进数:49,49×2;第二十六个抽屉里放进数:51.………………第五十个抽屉里放进数:99.那么随意取出51个数中,必有两个数同属一个抽屉,其中一个数是另一个数的倍数.制造抽屉并非总是一帆风顺的,有时要边制造边调整、改进. 例8 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数. 分析 注意到这些数队除以10的余数即个位数字,以0,1,…,9为标准制造10个抽屉,标以[0],[1],…,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数. 3.较复杂的问题须反复地运用抽屉原则,将复杂问题转化为简单问题. 例9 以(x,y,z)表示三元有序整数组,其中x、y、z为整数,试证:在任意七个三元整数组中,至少有两个三元数组,它们的x、y、z元中有两对都是奇数或都是偶数. 分析 设七个三元素组为A1(x1,y1,z1)、A2(x2,y2,z2)、…、A7(x7,y7,z7).现在逐步探索,从x元开始,由抽屉原则,x1,x2,…,x7这七个数中,必定有四个数具有相同的奇偶性,不妨设这四个数是x1,x2,x3,x4且为偶数,接着集中考虑A1、A2、A3、A4这四组数的y元,若比如y1,y2,y3,y4中有两个是偶数,则问题已证,否则至多有一个是偶数,比如y4是偶数,这时我们再来集中考虑A1、A2、A3的z元.在z1,z2,z3中,由抽屉原则必有两个数具有相同的奇偶性,如z1、z2,这时无论它们是奇数,还是偶数,问题都已得到证明. 下面介绍一个著名问题. 例10 任选6人,试证其中必有3人,他们互相认识或都不认识. 分析 用A、B、C、D、E、F表示这6个人,首先以A为中心考虑,他与另外五个人B、C、D、E、F只有两种可能的关系:认识或不认识,那么由抽屉原则,他必定与其中某三人认识或不认识,现不妨设A认识B、C、D三人,当B、C、D三人都互不认识时,问题得证;当B、C、D三人中有两人认识,如B、C认识时,则A、B、C互相认识,问题也得证.本例和上例都采用了舍去保留、化繁为简、逐步缩小考虑范围的方法. 例11 a,b,c,d为四个任意给定的整数,求证:以下六个差数b-a,c-a,d-a,c-b,d-b,d-c的乘积一定可以被12整除. 证明 把这6个差数的乘积记为p,我们必须且只须证明:3与4都可以整除p,以下分两步进行. 第一步,把a,b,c,d按以3为除数的余数来分类,这样的类只有三个,故知a,b,c,d中至少有2个除以3的余数相同,例如,不妨设为a,b,这时3可整除b-a,从而3可整除p. 第二步,再把a,b,c,d按以4为除数的余数来分类,这种类至多只有四个,如果a,b,c,d中有二数除以4的余数相同,那么与第一步类似,我们立即可作出4可整除p的结论. 设a,b,c,d四数除以4的余数不同,由此推知,a,b,c,d之中必有二个奇数(不妨设为a,b),也必有二个偶数(设为c,d),这时b-a为偶数,d-c也是偶数,故4可整除(b-a)(d-c),自然也可得出4可整除p.如果能进一步灵活运用原则,不仅制造抽屉,还根据问题的特征,制造出放进抽屉的物体,则更可收到意想不到的效果. 例12 求证:从任意n个自然数a1,a2,…,an中可以找到若干个数,使它们的和是n的倍数. 分析以0,1,…,n-1即被n除的余数分类制造抽屉的合理的,但把什么样的数作为抽屉里的物体呢?扣住“和”,构造下列和数: S1=a1, S2=a1+a2, S=a1+a2+a3, ………… Sn=a1+a2+…+an, 其中任意两个和数之差仍为和数,若他们之中有一是n的倍数,问题得证,否则至少有两个数被n除余数相同,则它们的差即它们中若干数(包括1个)的和是n的倍数,问题同样得证. 例13 910瓶红、蓝墨水,排成130行,每行7瓶,证明:不论怎样排列,红蓝墨水瓶的颜色次序必定出现下述两种情况之一种:(1)至少有三行完全相同;(2)至少有两组(四行)每组的两行完全相同. 解 910瓶红、蓝墨水排成130行,每行7瓶,对一行来说,每个位置上有红蓝两种可能,因此,一行的红、蓝墨水排法有27=128种,对每一种不同排法设为一种“行式”,共有128种行式.现有130行,在其中任取129行,依抽屉原则知,必有两行A、B行式相同.除A、B外余下128行,若有一行P与A行式相同,知满足(1)至少有三行A、B、P完全相同,若在这128行中设直一行5A行或相同,那么这128行至多有127种行式,依抽屉原则,必有两行C、D具有相同行式,这样便找到了(A、B),(C、D)两组(四行),且两组两行完全相同
追问:
我真的不需要你这些信息
人教版六年级下册数学广角解读
接着,可以继续提问:如果要放的铅笔数比文具盒的数量多2,多3,多4呢?引导学生发现:只要铅笔数比文具盒的数量多,这个结论都是成立的。通过这样的教学过程,有助于发展学生的类推能力,形成比较抽象的数学思维。2.例2。编写意图本例介绍了另一种类型的“抽屉问题”,即“把多于 kn个的物体任意分放进n 个空抽屉(k...
4-20抽屉原理
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体(例如,将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2)。例题三: ☆☆☆ 某班同学去买书,语数外三种,任意买1 2 3本。至少有多少才能发生相同的结果?任意6个不同的自然...
我要奥赛题!!
把5个苹果放到4个抽屉中,必然有一个抽屉中至少有2个苹果,这是抽屉原理的通俗解释。一般地,我们将它表述为:第一抽屉原理:把(mn+1)个物体放入n个抽屉,其中必有一个抽屉中至少有(m+1)个物体。 使用抽屉原理解题,关键是构造抽屉。一般说来,数的奇偶性、剩余类、数的分组、染色、线段与平面图形的划分等,都可作...
把若干个苹果放进9个抽屉 不管怎么放 要保证总有一个抽屉里至少放进4个...
如果把 5 个苹果放进两个抽屉里,上述结果当然还能成立。能不能有更强一点的结果呢?我们发现把 5 个苹果往两个抽屉里放,即使每个抽屉都放 2 个还剩 1 个苹果,这个苹果无论放到哪个抽屉里都会出现有一个抽屉里有 3 个苹果。同样,如果苹果个数变为 7 个,那么就可以保证有一个抽屉里至少有 ...
小学数学问题~~超级简单!急用
式子 5乘以3加1=16.此答案已经给奥数老师看过,没有问题.很简单.2题,其实不要想得太复杂,都参加了兴趣组,就意味着至少报一科参加一项,或最多参加4项,抽屉问题关键是找出抽屉的个数,参加一科的有4种情况,看作4个抽屉.参加2科学习的有3+2+1=6种,(数美,数书,数英,美书.美英.书英)看作6...
数学中的抽屉原理问题怎么解决?
抽屉原理又称鸽巢原理,它是组合数学的一个基本原理,最先是由德国数学家狭利克雷明确地提出来的,因此,也称为狭利克雷原理。抽屉原理 “任意367个人中,必有生日相同的人。”“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”“从数1,2,...,10中任取6个数,其中至少有2个数为...
有9个苹果,放入5个抽屉,则至少有两个抽屉放的同样多,为什么?
给5个抽屉编号为1,2,3,4,5.先每个抽屉放一个,还剩4个。再一个一个随意向抽屉放:第一种情况5个苹果在同一抽屉有5种情况,有4个抽屉苹果数一样多;第二,4个苹果同在一个抽屉有5×4=20种情况,有3个抽屉一样多;第三,3个苹果同在一个抽屉有A,两个抽屉同时各有3个苹果5×4,B一...
老师发糖给同学有草莓荔枝芒果3种口味每种足够多每人发2个共有35名同 ...
由题目可知,有三种口味的糖,每人发2个,则3个人为一组,分别为草莓和荔枝;草莓和芒果以及荔枝和芒果,三个组看成是三个抽屉,总人数除以抽屉数解答即可。解题过程如下:解:35÷3=11……2 竖式如下:十位:1×3=3,个位:1×3=3,5-3=2,所以商是11,余2。答:至少11名同学口味一样。
希望小学六一班有学生41人同一月份出生的学生至少有几人?
结果为至少有4人。解析:本题考查的是除法的应用,本题考点是抽屉原理,在此抽屉问题中,至少数=物体数除以抽屉数的商+1(有余的情况下)。由题意可知,一年有12个月,那么把这12个月看做12个抽屉,要求至少有多少名同学在同一个月过生日,可以考虑最差情况:41名尽量平均分配在12个抽屉中,利用...
什么是“抽屉原理”?
抽屉原理 原理:多于n个的球以任意方式全部放入n个抽屉中,一定存在一个抽屉,它里面有两个或两个以上的球。 1. 任意11个整数中,一定有两个数,它们的差是10的倍数。 2. 设任意n+1个实数在[0 1)中,求证在它们中存在两个数且它们的差少于1\/n。 3. 在前10个自然数中任取6个数,求证:...
错任再晟: 思考如果物体个数比抽屉多两个三个,
普安县18542588847: 什么是”抽屉原则”,数学精英学的 - ?
错任再晟: 抽屉原理有时也被称为鸽巢原理.它是组合数学中一个重要的原理.抽屉原则一:如果把(n+1)个物体放在n个抽屉里,那么必有一个抽屉中至少放有2个物体. 例:把4个物体放在3个抽屉里,也就是把4分解成三个整数的和,那么就有以下四...
普安县18542588847: 把m个物体任意放进n个抽屉中(2n >m>n,n是非0自然数),那么一定有一个抽屉中至少放进了2个物体, - ?
错任再晟: 第一个:你把N个物体分别放入n个抽屉里,但是因为m>n,所以肯定还有剩余的没放,那没放的就必须放进n个抽屉里,m最少也是n+1,所以第一个成立;第二个,假设kn个物体平均地放到n个抽屉里,那每个抽屉都有k个(假如你不这样平均分那么肯定有抽屉里的物体>=k+1),由于物体>kn,所以至少是kn+1,剩下的要放到抽屉里,就至少有一个抽屉里的物体>=k+1了.
普安县18542588847: 抽屉原理怎么解释?
错任再晟: 原理就是 现在有多个抽屉 有比抽屉个数多的物体往抽屉里面放 那首先要先保证每个抽屉里面都有物体,换句话说,先保证不让空抽屉出现 等每个抽屉都有1个物体了,再往随便哪个抽屉里面放一个物体. 依次类推,直到每个抽屉都有两个物体了,再到每个抽屉都有三个物体......
普安县18542588847: 六年级数学广角?
错任再晟: 差是12的倍数即差能被12整除,除数为12的余数有0---11共12种可能.这12种可能构建12个抽屉,根据抽屉原理只要苹果数(物体数)比抽屉多就能保证总有一个抽屉至少有2个苹果(物体).比12多,多1就可以,12+1=13.
普安县18542588847: 抽屉原理说把多于N个的物体放入N个抽屉里,至少有一个抽屉里的物体不少于两个,怎么不是一个呢? - ?
错任再晟: 把两个变成一个,是完全正确的,但是改成一个,抽屉原理也就没什么意思了. 把1个物体放入N个抽屉里,至少有一个抽屉里的物体不少于一个.这句话也没错啊. 5只鸟飞进4个鸟笼,不一定每个笼子里至少有一只鸟,有可能物质鸟全飞进一只笼子里,肯定的是有一个笼子里的鸟不少于1只. 抽屉原理最重要的是极端思维吧.没必要想那么复杂.N+1个物体放入N个抽屉里,最极端的情况,每个抽屉里都有物体,那么第N+1个物体无论放入哪个抽屉里都能保证有一个抽屉里不少于两个物体.
普安县18542588847: 小学二年级数学题:某艺术班有62位学生,其中会钢琴的11个,会长笛的56个,还有4个两样都不会,问 - ?
错任再晟: 这类题的解法称作“抽屉法”.就是用抽屉比喻有几个位置,而有若干个物体放到这些抽屉里,要求每个抽屉都有物体,如果物体数量多余抽屉显然就有部分抽屉必须放1个以上物体.那么有几个抽屉必须放1个以上物体呢?显然物体总数比抽屉总数多几个(如果没有抽屉放2个),就有几个抽屉放2个物体.于是可知,现在有62-4=58个“抽屉”(学生),放11+56件“物体”(技艺),总数为11+56=67,那么就有:67-58=9个“抽屉”,放2件东西(会2样技艺)
普安县18542588847: 抽屉原理是怎么个意思??
错任再晟: 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放两个苹果.这一现象就是我们所说的“抽屉原理”. 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里有两个元素.” 抽屉原理有时也被称为鸽巢原理(“如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子”).它是组合数学中一个重要的原理
普安县18542588847: 如果物体是抽屉的倍数 假如物体是12 抽屉是2 那还用加1么 - ?
错任再晟: 不用了,当物体是抽屉的倍数时,就不用加1了.你六年级?抽屉原理很难的,关键要找到什么是物体,什么是抽屉,对不起,废话有点多了,不过很高兴帮到你.
普安县18542588847: 急!抽屉原理 - ?
错任再晟: 原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体. 原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体 1、六一儿童节时,莉莉姐姐送给每个小朋友两个玩具(从她带...