抽屉原理
6个回答
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。”
例1:400人中至少有两个人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个物体,由抽屉原理1可以得知:至少有两人的生日相同.
又如:我们从街上随便找来13人,就可断定他们中至少有两个人属相相同.
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.
解:从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原理1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.
例1:400人中至少有两个人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个物体,由抽屉原理1可以得知:至少有两人的生日相同.
又如:我们从街上随便找来13人,就可断定他们中至少有两个人属相相同.
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.
解:从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原理1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.
抽屉原理:
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。”
桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,有的抽屉可以放一个,有的可以放两个,有的可以放五个,但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。”
抽屉原理有时也被称为鸽巢原理(“如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子”)。它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原理。它是组合数学中一个重要的原理。
一. 抽屉原理最常见的形式
原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体。
[证明](反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体。
[证明](反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.
原理1 2都是第一抽屉原理的表述
第二抽屉原理:
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
[证明](反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能
二.应用抽屉原理解题
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
例1:400人中至少有两个人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个物体,由抽屉原理1可以得知:至少有两人的生日相同.
又如:我们从街上随便找来13人,就可断定他们中至少有两个人属相相同.
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.
解 :从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原理1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.
上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.(需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少.)
抽屉原理虽然简单,但应用却很广泛,它可以解答很多有趣的问题,其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。
(一) 整除问题
把所有整数按照除以某个自然数m的余数分为m类,叫做m的剩余类或同余类,用[0],[1],[2],…,[m-1]表示.每一个类含有无穷多个数,例如[1]中含有1,m+1,2m+1,3m+1,….在研究与整除有关的问题时,常用剩余类作为抽屉.根据抽屉原理,可以证明:任意n+1个自然数中,总有两个自然数的差是n的倍数。
例1 证明:任取8个自然数,必有两个数的差是7的倍数。
分析与解答 在与整除有关的问题中有这样的性质,如果两个整数a、b,它们除以自然数m的余数相同,那么它们的差a-b是m的倍数.根据这个性质,本题只需证明这8个自然数中有2个自然数,它们除以7的余数相同.我们可以把所有自然数按被7除所得的7种不同的余数0、1、2、3、4、5、6分成七类.也就是7个抽屉.任取8个自然数,根据抽屉原理,必有两个数在同一个抽屉中,也就是它们除以7的余数相同,因此这两个数的差一定是7的倍数。
例2:对于任意的五个自然数,证明其中必有3个数的和能被3整除.
证明∵任何数除以3所得余数只能是0,1,2,不妨分别构造为3个抽屉:
[0],[1],[2]
①若这五个自然数除以3后所得余数分别分布在这3个抽屉中,我们从这三个抽屉中各取1个,其和必能被3整除.
②若这5个余数分布在其中的两个抽屉中,则其中必有一个抽屉,包含有3个余数(抽屉原理),而这三个余数之和或为0,或为3,或为6,故所对应的3个自然数之和是3的倍数.
③若这5个余数分布在其中的一个抽屉中,很显然,必有3个自然数之和能被3整除.
例2′:对于任意的11个整数,证明其中一定有6个数,它们的和能被6整除.
证明:设这11个整数为:a1,a2,a3……a11 又6=2×3
①先考虑被3整除的情形
由例2知,在11个任意整数中,必存在:
3|a1+a2+a3,不妨设a1+a2+a3=b1;
同理,剩下的8个任意整数中,由例2,必存在:3 | a4+a5+a6.设a4+a5+a6=b2;
同理,其余的5个任意整数中,有:3|a7+a8+a9,设:a7+a8+a9=b3
②再考虑b1、b2、b3被2整除.
依据抽屉原理,b1、b2、b3这三个整数中,至少有两个是同奇或同偶,这两个同奇(或同偶)的整数之和必为偶数.不妨设2|b1+b2
则:6|b1+b2,即:6|a1+a2+a3+a4+a5+a6
∴任意11个整数,其中必有6个数的和是6的倍数.
例3: 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数.
分析:注意到这些数队以10的余数即个位数字,以0,1,…,9为标准制造10个抽屉,标以[0],[1],…,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数.
(二)面积问题
例:九条直线中的每一条直线都将正方形分成面积比为2:3的梯形,证明:这九条直线中至少有三条经过同一点.
证明:如图,设直线EF将正方形分成两个梯形,作中位线MN。由于这两个梯形的高相等, 故它们的面积之比等于中位线长的比,即|MH|:|NH| 。于是点H有确定的位置(它在正方形一对对边中点的连线上,且|MH|:|NH|=2:3). 由几何上的对称性,这种点共有四个(即图中的H、J、I、K).已知的九条适合条件的分割直线中的每一条必须经过H、J、I、K这四点中的一点.把H、J、I、K看成四个抽屉,九条直线当成9个物体,即可得出必定有3条分割线经过同一点.
(三)染色问题
例1正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.
证明:把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原理二,至少有三个面涂上相同的颜色.
例2 有5个小朋友,每人都从装有许多黑白围棋子的布袋中任意摸出3枚棋子.请你证明,这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。
分析与解答 首先要确定3枚棋子的颜色可以有多少种不同的情况,可以有:3黑,2黑1白,1黑2白,3白共4种配组情况,看作4个抽屉.根据抽屉原理,至少有两个小朋友摸出的棋子的颜色在同一个抽屉里,也就是他们所拿棋子的颜色配组是一样的。
例3:假设在一个平面上有任意六个点,无三点共线,每两点用红色或蓝色的线段连起来,都连好后,问你能不能找到一个由这些线构成的三角形,使三角形的三边同色?
解:首先可以从这六个点中任意选择一点,然后把这一点到其他五点间连五条线段,如图,在这五条线段中,至少有三条线段是同一种颜色,假定是红色,现在我们再单独来研究这三条红色的线。这三条线段的另一端或许是不同颜色,假设这三条线段(虚线)中其中一条是红色的,那么这条红色的线段和其他两条红色的线段便组成了我们所需要的同色三角形,如果这三条线段都是蓝色的,那么这三条线段也组成我们所需要的同色三角形。因而无论怎样着色,在这六点之间的所有线段中至少能找到一个同色三角形。
例3′(六人集会问题)证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
例3”:17个科学家中每个人与其余16个人通信,他们通信所讨论的仅有三个问题,而任两个科学家之间通信讨论的是同一个问题。证明:至少有三个科学家通信时讨论的是同一个问题。
解:不妨设A是某科学家,他与其余16位讨论仅三个问题,由鸽笼原理知,他至少与其中的6位讨论同一问题。设这6位科学家为B,C,D,E,F,G,讨论的是甲问题。
若这6位中有两位之间也讨论甲问题,则结论成立。否则他们6位只讨论乙、丙两问题。这样又由鸽笼原理知B至少与另三位讨论同一问题,不妨设这三位是C,D,E,且讨论的是乙问题。
若C,D,E中有两人也讨论乙问题,则结论也就成立了。否则,他们间只讨论丙问题,这样结论也成立。
三.制造抽屉是运用原则的一大关键
例1 从2、4、6、…、30这15个偶数中,任取9个数,证明其中一定有两个数之和是34。
分析与解答 我们用题目中的15个偶数制造8个抽屉:
凡是抽屉中有两个数的,都具有一个共同的特点:这两个数的和是34。现从题目中的15个偶数中任取9个数,由抽屉原理(因为抽屉只有8个),必有两个数在同一个抽屉中.由制造的抽屉的特点,这两个数的和是34。
例2:从1、2、3、4、…、19、20这20个自然数中,至少任选几个数,就可以保证其中一定包括两个数,它们的差是12。
分析与解答在这20个自然数中,差是12的有以下8对:{20,8},{19,7},{18,6},{17,5},{16,4},{15,3},{14,2},{13,1}。
另外还有4个不能配对的数{9},{10},{11},{12},共制成12个抽屉(每个括号看成一个抽屉).只要有两个数取自同一个抽屉,那么它们的差就等于12,根据抽屉原理至少任选13个数,即可办到(取12个数:从12个抽屉中各取一个数(例如取1,2,3,…,12),那么这12个数中任意两个数的差必不等于12)。
例3: 从1到20这20个数中,任取11个数,必有两个数,其中一个数是另一个数的倍数。
分析与解答 根据题目所要求证的问题,应考虑按照同一抽屉中,任意两数都具有倍数关系的原则制造抽屉.把这20个数按奇数及其倍数分成以下十组,看成10个抽屉(显然,它们具有上述性质):
{1,2,4,8,16},{3,6,12},{5,10,20},{7,14},{9,18},{11},{13},{15},{17},{19}。
从这10个数组的20个数中任取11个数,根据抽屉原理,至少有两个数取自同一个抽屉.由于凡在同一抽屉中的两个数都具有倍数关系,所以这两个数中,其中一个数一定是另一个数的倍数。
例4:某校校庆,来了n位校友,彼此认识的握手问候.请你证明无论什么情况,在这n个校友中至少有两人握手的次数一样多。
分析与解答 共有n位校友,每个人握手的次数最少是0次,即这个人与其他校友都没有握过手;最多有n-1次,即这个人与每位到会校友都握了手.然而,如果有一个校友握手的次数是0次,那么握手次数最多的不能多于n-2次;如果有一个校友握手的次数是n-1次,那么握手次数最少的不能少于1次.不管是前一种状态0、1、2、…、n-2,还是后一种状态1、2、3、…、n-1,握手次数都只有n-1种情况.把这n-1种情况看成n-1个抽屉,到会的n个校友每人按照其握手的次数归入相应的“抽屉”,根据抽屉原理,至少有两个人属于同一抽屉,则这两个人握手的次数一样多。
在有些问题中,“抽屉”和“物体”不是很明显的,需要精心制造“抽屉”和“物体”.如何制造“抽屉”和“物体”可能是很困难的,一方面需要认真地分析题目中的条件和问题,另一方面需要多做一些题积累经验。
抽屉原理
把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
形式一:证明:设把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+1
n个m 这与题设相矛盾。所以,至少有存在一个ai≥m+1
高斯函数:对任意的实数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:400人中至少有两个人的生日相同.分析:生日从1月1日排到12月31日,共有366个不相同的生日,我们把366个不同的生日看作366个抽屉,400人视为400个苹果,由表现形式1可知,至少有两人在同一个抽屉里,所以这400人中有两人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个苹果,由抽屉原理的表现形式1可以得知:至少有两人的生日相同.
例题2:任取5个整数,必然能够从中选出三个,使它们的和能够被3整除.
证明:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r0,r1,r2.至少有一类包含所给5个数中的至少两个.因此可能出现两种情况:1°.某一类至少包含三个数;2°.某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;若是第二种情况,在三类中各取一个数,其和也能被3整除..综上所述,原命题正确.
例题3:某校派出学生204人上山植树15301株,其中最少一人植树50株,最多一人植树100株,则至少有5人植树的株数相同.
证明:按植树的多少,从50到100株可以构造51个抽屉,则个问题就转化为至少有5人植树的株数在同一个抽屉里.
(用反证法)假设无5人或5人以上植树的株数在同一个抽屉里,那只有5人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:
4(50+51+…+100)=4× =15300<15301得出矛盾.因此,至少有5人植树的株数相同.
练习:1.边长为1的等边三角形内有5个点,那么这5个点中一定有距离小于0.5的两点.
2.边长为1的等边三角形内,若有n2+1个点,则至少存在2点距离小于 .
3.求证:任意四个整数中,至少有两个整数的差能够被3整除.
4.某校高一某班有50名新生,试说明其中一定有二人的熟人一样多.
5.某个年级有202人参加考试,满分为100分,且得分都为整数,总得分为10101分,则至少有3人得分相同.
“任意367个人中,必有生日相同的人。”
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
... ...
大家都会认为上面所述结论是正确的。这些结论是依据什么原理得出的呢?这个原理叫做抽屉原理。它的内容可以用形象的语言表述为:
“把m个东西任意分放进n个空抽屉里(m>n),那么一定有一个抽屉中放进了至少2个东西。”
在上面的第一个结论中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉,至少有2个东西在同一抽屉里。在第二个结论中,不妨想象将5双手套分别编号,即号码为1,2,...,5的手套各有两只,同号的两只是一双。任取6只手套,它们的编号至多有5种,因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉,至少有2个东西在同一抽屉里。
抽屉原理的一种更一般的表述为:
“把多于kn个东西任意分放进n个空抽屉(k是正整数),那么一定有一个抽屉中放进了至少k+1个东西。”
利用上述原理容易证明:“任意7个整数中,至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能,所以7个整数中至少有3个数除以3所得余数相同,即它们两两之差是3的倍数。
如果问题所讨论的对象有无限多个,抽屉原理还有另一种表述:
“把无限多个东西任意分放进n个空抽屉(n是自然数),那么一定有一个抽屉中放进了无限多个东西。”
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
1958年6/7月号的《美国数学月刊》上有这样一道题目:
“证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
这个问题可以用如下方法简单明了地证出:
在平面上用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+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。”
桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,有的抽屉可以放一个,有的可以放两个,有的可以放五个,但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。”
抽屉原理有时也被称为鸽巢原理(“如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子”)。它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原理。它是组合数学中一个重要的原理。
一. 抽屉原理最常见的形式
原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体。
[证明](反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体。
[证明](反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.
原理1 2都是第一抽屉原理的表述
第二抽屉原理:
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
[证明](反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能
二.应用抽屉原理解题
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
例1:400人中至少有两个人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个物体,由抽屉原理1可以得知:至少有两人的生日相同.
又如:我们从街上随便找来13人,就可断定他们中至少有两个人属相相同.
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.
解 :从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原理1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.
上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.(需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少.)
抽屉原理虽然简单,但应用却很广泛,它可以解答很多有趣的问题,其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。
(一) 整除问题
把所有整数按照除以某个自然数m的余数分为m类,叫做m的剩余类或同余类,用[0],[1],[2],…,[m-1]表示.每一个类含有无穷多个数,例如[1]中含有1,m+1,2m+1,3m+1,….在研究与整除有关的问题时,常用剩余类作为抽屉.根据抽屉原理,可以证明:任意n+1个自然数中,总有两个自然数的差是n的倍数。
例1 证明:任取8个自然数,必有两个数的差是7的倍数。
分析与解答 在与整除有关的问题中有这样的性质,如果两个整数a、b,它们除以自然数m的余数相同,那么它们的差a-b是m的倍数.根据这个性质,本题只需证明这8个自然数中有2个自然数,它们除以7的余数相同.我们可以把所有自然数按被7除所得的7种不同的余数0、1、2、3、4、5、6分成七类.也就是7个抽屉.任取8个自然数,根据抽屉原理,必有两个数在同一个抽屉中,也就是它们除以7的余数相同,因此这两个数的差一定是7的倍数。
例2:对于任意的五个自然数,证明其中必有3个数的和能被3整除.
证明∵任何数除以3所得余数只能是0,1,2,不妨分别构造为3个抽屉:
[0],[1],[2]
①若这五个自然数除以3后所得余数分别分布在这3个抽屉中,我们从这三个抽屉中各取1个,其和必能被3整除.
②若这5个余数分布在其中的两个抽屉中,则其中必有一个抽屉,包含有3个余数(抽屉原理),而这三个余数之和或为0,或为3,或为6,故所对应的3个自然数之和是3的倍数.
③若这5个余数分布在其中的一个抽屉中,很显然,必有3个自然数之和能被3整除.
例2′:对于任意的11个整数,证明其中一定有6个数,它们的和能被6整除.
证明:设这11个整数为:a1,a2,a3……a11 又6=2×3
①先考虑被3整除的情形
由例2知,在11个任意整数中,必存在:
3|a1+a2+a3,不妨设a1+a2+a3=b1;
同理,剩下的8个任意整数中,由例2,必存在:3 | a4+a5+a6.设a4+a5+a6=b2;
同理,其余的5个任意整数中,有:3|a7+a8+a9,设:a7+a8+a9=b3
②再考虑b1、b2、b3被2整除.
依据抽屉原理,b1、b2、b3这三个整数中,至少有两个是同奇或同偶,这两个同奇(或同偶)的整数之和必为偶数.不妨设2|b1+b2
则:6|b1+b2,即:6|a1+a2+a3+a4+a5+a6
∴任意11个整数,其中必有6个数的和是6的倍数.
例3: 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数.
分析:注意到这些数队以10的余数即个位数字,以0,1,…,9为标准制造10个抽屉,标以[0],[1],…,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数.
(二)面积问题
例:九条直线中的每一条直线都将正方形分成面积比为2:3的梯形,证明:这九条直线中至少有三条经过同一点.
证明:如图,设直线EF将正方形分成两个梯形,作中位线MN。由于这两个梯形的高相等, 故它们的面积之比等于中位线长的比,即|MH|:|NH| 。于是点H有确定的位置(它在正方形一对对边中点的连线上,且|MH|:|NH|=2:3). 由几何上的对称性,这种点共有四个(即图中的H、J、I、K).已知的九条适合条件的分割直线中的每一条必须经过H、J、I、K这四点中的一点.把H、J、I、K看成四个抽屉,九条直线当成9个物体,即可得出必定有3条分割线经过同一点.
(三)染色问题
例1正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.
证明:把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原理二,至少有三个面涂上相同的颜色.
例2 有5个小朋友,每人都从装有许多黑白围棋子的布袋中任意摸出3枚棋子.请你证明,这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。
分析与解答 首先要确定3枚棋子的颜色可以有多少种不同的情况,可以有:3黑,2黑1白,1黑2白,3白共4种配组情况,看作4个抽屉.根据抽屉原理,至少有两个小朋友摸出的棋子的颜色在同一个抽屉里,也就是他们所拿棋子的颜色配组是一样的。
例3:假设在一个平面上有任意六个点,无三点共线,每两点用红色或蓝色的线段连起来,都连好后,问你能不能找到一个由这些线构成的三角形,使三角形的三边同色?
解:首先可以从这六个点中任意选择一点,然后把这一点到其他五点间连五条线段,如图,在这五条线段中,至少有三条线段是同一种颜色,假定是红色,现在我们再单独来研究这三条红色的线。这三条线段的另一端或许是不同颜色,假设这三条线段(虚线)中其中一条是红色的,那么这条红色的线段和其他两条红色的线段便组成了我们所需要的同色三角形,如果这三条线段都是蓝色的,那么这三条线段也组成我们所需要的同色三角形。因而无论怎样着色,在这六点之间的所有线段中至少能找到一个同色三角形。
例3′(六人集会问题)证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
例3”:17个科学家中每个人与其余16个人通信,他们通信所讨论的仅有三个问题,而任两个科学家之间通信讨论的是同一个问题。证明:至少有三个科学家通信时讨论的是同一个问题。
解:不妨设A是某科学家,他与其余16位讨论仅三个问题,由鸽笼原理知,他至少与其中的6位讨论同一问题。设这6位科学家为B,C,D,E,F,G,讨论的是甲问题。
若这6位中有两位之间也讨论甲问题,则结论成立。否则他们6位只讨论乙、丙两问题。这样又由鸽笼原理知B至少与另三位讨论同一问题,不妨设这三位是C,D,E,且讨论的是乙问题。
若C,D,E中有两人也讨论乙问题,则结论也就成立了。否则,他们间只讨论丙问题,这样结论也成立。
三.制造抽屉是运用原则的一大关键
例1 从2、4、6、…、30这15个偶数中,任取9个数,证明其中一定有两个数之和是34。
分析与解答 我们用题目中的15个偶数制造8个抽屉:
凡是抽屉中有两个数的,都具有一个共同的特点:这两个数的和是34。现从题目中的15个偶数中任取9个数,由抽屉原理(因为抽屉只有8个),必有两个数在同一个抽屉中.由制造的抽屉的特点,这两个数的和是34。
例2:从1、2、3、4、…、19、20这20个自然数中,至少任选几个数,就可以保证其中一定包括两个数,它们的差是12。
分析与解答在这20个自然数中,差是12的有以下8对:{20,8},{19,7},{18,6},{17,5},{16,4},{15,3},{14,2},{13,1}。
另外还有4个不能配对的数{9},{10},{11},{12},共制成12个抽屉(每个括号看成一个抽屉).只要有两个数取自同一个抽屉,那么它们的差就等于12,根据抽屉原理至少任选13个数,即可办到(取12个数:从12个抽屉中各取一个数(例如取1,2,3,…,12),那么这12个数中任意两个数的差必不等于12)。
例3: 从1到20这20个数中,任取11个数,必有两个数,其中一个数是另一个数的倍数。
分析与解答 根据题目所要求证的问题,应考虑按照同一抽屉中,任意两数都具有倍数关系的原则制造抽屉.把这20个数按奇数及其倍数分成以下十组,看成10个抽屉(显然,它们具有上述性质):
{1,2,4,8,16},{3,6,12},{5,10,20},{7,14},{9,18},{11},{13},{15},{17},{19}。
从这10个数组的20个数中任取11个数,根据抽屉原理,至少有两个数取自同一个抽屉.由于凡在同一抽屉中的两个数都具有倍数关系,所以这两个数中,其中一个数一定是另一个数的倍数。
例4:某校校庆,来了n位校友,彼此认识的握手问候.请你证明无论什么情况,在这n个校友中至少有两人握手的次数一样多。
分析与解答 共有n位校友,每个人握手的次数最少是0次,即这个人与其他校友都没有握过手;最多有n-1次,即这个人与每位到会校友都握了手.然而,如果有一个校友握手的次数是0次,那么握手次数最多的不能多于n-2次;如果有一个校友握手的次数是n-1次,那么握手次数最少的不能少于1次.不管是前一种状态0、1、2、…、n-2,还是后一种状态1、2、3、…、n-1,握手次数都只有n-1种情况.把这n-1种情况看成n-1个抽屉,到会的n个校友每人按照其握手的次数归入相应的“抽屉”,根据抽屉原理,至少有两个人属于同一抽屉,则这两个人握手的次数一样多。
在有些问题中,“抽屉”和“物体”不是很明显的,需要精心制造“抽屉”和“物体”.如何制造“抽屉”和“物体”可能是很困难的,一方面需要认真地分析题目中的条件和问题,另一方面需要多做一些题积累经验。
抽屉原理
把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
形式一:证明:设把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+1
n个m 这与题设相矛盾。所以,至少有存在一个ai≥m+1
高斯函数:对任意的实数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:400人中至少有两个人的生日相同.分析:生日从1月1日排到12月31日,共有366个不相同的生日,我们把366个不同的生日看作366个抽屉,400人视为400个苹果,由表现形式1可知,至少有两人在同一个抽屉里,所以这400人中有两人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个苹果,由抽屉原理的表现形式1可以得知:至少有两人的生日相同.
例题2:任取5个整数,必然能够从中选出三个,使它们的和能够被3整除.
证明:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r0,r1,r2.至少有一类包含所给5个数中的至少两个.因此可能出现两种情况:1°.某一类至少包含三个数;2°.某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;若是第二种情况,在三类中各取一个数,其和也能被3整除..综上所述,原命题正确.
例题3:某校派出学生204人上山植树15301株,其中最少一人植树50株,最多一人植树100株,则至少有5人植树的株数相同.
证明:按植树的多少,从50到100株可以构造51个抽屉,则个问题就转化为至少有5人植树的株数在同一个抽屉里.
(用反证法)假设无5人或5人以上植树的株数在同一个抽屉里,那只有5人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:
4(50+51+…+100)=4× =15300<15301得出矛盾.因此,至少有5人植树的株数相同.
练习:1.边长为1的等边三角形内有5个点,那么这5个点中一定有距离小于0.5的两点.
2.边长为1的等边三角形内,若有n2+1个点,则至少存在2点距离小于 .
3.求证:任意四个整数中,至少有两个整数的差能够被3整除.
4.某校高一某班有50名新生,试说明其中一定有二人的熟人一样多.
5.某个年级有202人参加考试,满分为100分,且得分都为整数,总得分为10101分,则至少有3人得分相同.
“任意367个人中,必有生日相同的人。”
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
... ...
大家都会认为上面所述结论是正确的。这些结论是依据什么原理得出的呢?这个原理叫做抽屉原理。它的内容可以用形象的语言表述为:
“把m个东西任意分放进n个空抽屉里(m>n),那么一定有一个抽屉中放进了至少2个东西。”
在上面的第一个结论中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉,至少有2个东西在同一抽屉里。在第二个结论中,不妨想象将5双手套分别编号,即号码为1,2,...,5的手套各有两只,同号的两只是一双。任取6只手套,它们的编号至多有5种,因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉,至少有2个东西在同一抽屉里。
抽屉原理的一种更一般的表述为:
“把多于kn个东西任意分放进n个空抽屉(k是正整数),那么一定有一个抽屉中放进了至少k+1个东西。”
利用上述原理容易证明:“任意7个整数中,至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能,所以7个整数中至少有3个数除以3所得余数相同,即它们两两之差是3的倍数。
如果问题所讨论的对象有无限多个,抽屉原理还有另一种表述:
“把无限多个东西任意分放进n个空抽屉(n是自然数),那么一定有一个抽屉中放进了无限多个东西。”
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
1958年6/7月号的《美国数学月刊》上有这样一道题目:
“证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
这个问题可以用如下方法简单明了地证出:
在平面上用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个人以前彼此不相识。不论哪种情形发生,都符合问题的结论。
六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例,这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。从六人集会问题的证明中,我们又一次看到了抽屉原理的应用。
这是高中的排列组合问题
其实用红黄蓝绿四种颜色排成一排一共有4*3*2*1=24种排法
所以通讯员只能打出24种不同的信号,然而他打出50次信号,所以答案应该是至少有2中信号是重复的,这时,重复的信号出现了3次。
32班买了一些4角一张的画片,共花去35元.已知8角一张的画片比4角一张的画片多20张,这两种画片各买了多少张?
有蜘蛛、蜻蜓和蝉3种动物共18只,他们共有腿118条,翅膀20对,三种动物各有多少只?(其中蜘蛛有8条腿,蜻蜓有6条退和2对翅膀,蝉有6条腿和1对翅膀)
我六年级, 请用假设法或者1元1次方程解答.或者用算式`
谢谢, 我给150分`
回答好我再+分`
详细,点`
问题补充:... 32班就是三年级2班- -`
我都说了我不会`
也不想看到
一元二次方程`
不要有Y`
解:设4角的画片张数为X张,8角的画片张数为(X+20)张。
35元=350角
4X+8(X+20)=350
4X+8X+160=350
4X+8X=350-160
12X=190
X=95/6
X=15又5/6
X+20=(15又5/6)+20=(35又5/6)张
答:4角的画片张数为(15又5/6)张,8角的画片张数为(35又5/6)张。
2、
解:设蜻蜓有X只,蝉有[(20-2X)/1]只,蜘蛛有[18-X-(20-2X)/1]只。
6X+6[(20-2X)/1]+8[18-X-(20-2X)/1]=118
6X+120-12X+8[18-X-20+2X]=118
6X+120-12X+144-8X-160+16X=118
6X-12X-8X+16X=118-120-144+160
2X=14
X=7
(20-2X)/1=(20-2*7)/1=(20-14)/1=6/1=6只
18-X-(20-2X)/1=18-7-(20-2*7)/1=18-7-6=5只
答:蜻蜓有7只,蝉有6只,蜘蛛有5只。
其实用红黄蓝绿四种颜色排成一排一共有4*3*2*1=24种排法
所以通讯员只能打出24种不同的信号,然而他打出50次信号,所以答案应该是至少有2中信号是重复的,这时,重复的信号出现了3次。
32班买了一些4角一张的画片,共花去35元.已知8角一张的画片比4角一张的画片多20张,这两种画片各买了多少张?
有蜘蛛、蜻蜓和蝉3种动物共18只,他们共有腿118条,翅膀20对,三种动物各有多少只?(其中蜘蛛有8条腿,蜻蜓有6条退和2对翅膀,蝉有6条腿和1对翅膀)
我六年级, 请用假设法或者1元1次方程解答.或者用算式`
谢谢, 我给150分`
回答好我再+分`
详细,点`
问题补充:... 32班就是三年级2班- -`
我都说了我不会`
也不想看到
一元二次方程`
不要有Y`
解:设4角的画片张数为X张,8角的画片张数为(X+20)张。
35元=350角
4X+8(X+20)=350
4X+8X+160=350
4X+8X=350-160
12X=190
X=95/6
X=15又5/6
X+20=(15又5/6)+20=(35又5/6)张
答:4角的画片张数为(15又5/6)张,8角的画片张数为(35又5/6)张。
2、
解:设蜻蜓有X只,蝉有[(20-2X)/1]只,蜘蛛有[18-X-(20-2X)/1]只。
6X+6[(20-2X)/1]+8[18-X-(20-2X)/1]=118
6X+120-12X+8[18-X-20+2X]=118
6X+120-12X+144-8X-160+16X=118
6X-12X-8X+16X=118-120-144+160
2X=14
X=7
(20-2X)/1=(20-2*7)/1=(20-14)/1=6/1=6只
18-X-(20-2X)/1=18-7-(20-2*7)/1=18-7-6=5只
答:蜻蜓有7只,蝉有6只,蜘蛛有5只。
抽屉问题,又叫狄利克雷原则,原则一:把多于n个的元素,按任一确定的方式分成n个集合,那么一定至少有一个集合中,含有至少两个元素。原则二:把多于m×n个元素放入n个抽屉中,那么,一定有一个抽屉里有m+1个或者m+1个以上的元素。抽屉原则是证明符合某种条件的对象存在性问题有力工具。应用抽屉原则解决问题的关键是如何构造抽屉。
例1:在一个大口袋中装着红、黄、绿三种玻璃球各有很多个。如果每次随意拿3个球,拿11次,至少有两次玻璃球颜色状况完全相同,请说明理由。
分析:所谓两次玻璃球颜色状况完全相同,是指如果有一次拿的是1黄2绿,另一次也拿的是1黄2绿,它们的颜色状况就是完全相同。怎么说明呢?这就需要造抽屉,用抽屉原则来说明。随意拿出3个球,会有不同的状况,我们把它找全,每一种颜色状况就是一个抽屉,有多少种不同的颜色状况,就有多少个抽屉。
解:每次拿3个球,有10种不同的颜色状况,把这10种不同的颜色状况看成10个抽屉,拿的11次看成11个物体,根据抽屉原则一,把11个物体放入10个抽屉中,一定有两个或两个以上的物体。也就是说拿11次,一定至少有两次玻璃球的颜色状况完全相同。
例2:求证1997年1月出生的任意32个孩子中,至少有两个人是同一天出生的。
分析:1997年1月份共31天,为了回答上述问题,我们不妨假设1月份这31天为31个抽屉,而将1月份出生的任意32个孩子看作32个元素。根据抽屉原理一知,有一只抽屉里至少放入了两个元素。
解:答:1月份出生的任意32个孩子中,至少有两个人是同一天出生的。
练习:
1、求证:任意互异的8个整数中,一定存在6个整数x1、x2、x3、x4、x5、x6使得(x1-x2)·(x3-x4)·(x5-x6)恰是105的倍数。
分析:由于105=3×5×7,而3、5、7两两互质,所以只要能找到两个数,比如x1、x2,使得x1-x2是7的倍数,同理x3-x4是5的倍数,x5-x6是3的倍数,题目即得证。
解:根据抽屉原理一,在所给的任意8个整数中,必有两个整数被7除的余数相同,不妨设这两个数为x1、x2,则有7|(x1-x2),或表示为:x1-x2=7k1(其中k1为不等于零的整数)。在余下的6个数中,必有两个数被5除的余数相同,不妨设这两个数为x3、x4,使得x3、x4满足:x3-x4=5k2(k2为非零整数)。在余下的4个数中,必有两个整数被3除所得余数相同,不妨设这两个数为x5、x6,使得x5-x6=3k3(k3为非零整数)。
(x1-x2)·(x3-x4)·(x5-x6)
=7k1·5k2·3k3
=105×整数
即:从任意给定的互异的8个整数中,一定可以找到6个数x1、x2、x3、x4、x5、x6使得(x1-x2)·(x3-x4)·(x5-x6)是105的倍数。
2、一个袋里有四种不同颜色的小球,每次摸出两个,要保证有10次所摸的结果是一样的,至少要摸多少次?
分析:当摸出的两个球的颜色相同时,可以有四种不同的结果。当摸出的两个球的颜色不同时,最多可以有3+2+1种不同的结果。将上述10种不同的结果作为10个抽屉。
解:要求10次摸出的结果相同,依抽屉原理二,至少要摸9×10+1=91(次)。
3、 一个圆上有40条直径,在每条直径两端各填上一个数,所填数字可以从1到20中任意选。一定存在两条直径,两端点数字之和相等。
分析:我们做抽屉的方向一定是当每条直径的两端从1到20中任选数字填在上面时,会有多少种不同的和。把这些不同的和分别作为抽屉。再去与直径的条数做比较,就可以得出结论。
解:直径两端和最小的是2,最大的是40。因此,共有39种不同的和,把39种不同的和看成39个抽屉,直径的条数是40,大于39,所以一定存在着两条直径,两端数字之和相等。
4、能否在8行8列的方格表的每一个空格中分别填上1、2、3这三个数字中的任意一个,使得每一行、每一列及对角线AC、BD上的各个数字的和各不相同?对你的结论加以说明。
分析与解答:8行8列及两条对角线,共有18条“线”,每条“线”上都填有8个数字,要使各条“线”上的数字和均不相同,那么各条“线”上的数字和的取值情况应不少于18种。下面我们来分析一下各条“线”上取不同和的情况有多少种。如果某一条“线”上的8个数字都填上最小的数1,则可得到数字和的最小值8;如果某一条“线”上的8个空格中都填上最大的数3,那么可得到数字和的最大值24。由于数字及数字和均为整数,所以从8到24共有17种不同的值。我们将数字和的17种不同的值看作17个抽屉,而将18条“线”看作18个元素。根据抽屉原理一,将18个元素放入17个抽屉中,一定有一只抽屉中放入了至少两个元素。即18条“线”上的数字和至少有两个相同,所以不可能使18条“线”上的各数字和互不相同。
5、由6个队参加的单循环比赛(每两个队都要比赛一场),无论比赛进行到什么时候,一定存在两个队,这两个队比赛过的场次数相同。
分析:无论比赛进行到什么时候,所有比赛过的比赛过的场次从0场到5场都有可能出现。因此,就会有5个不同的抽屉。
解:参赛的队有6个,有5个抽屉,根据抽屉原则一,无论比赛进行到什么时候,一定有两个队比赛过的场次相同。
例1:在一个大口袋中装着红、黄、绿三种玻璃球各有很多个。如果每次随意拿3个球,拿11次,至少有两次玻璃球颜色状况完全相同,请说明理由。
分析:所谓两次玻璃球颜色状况完全相同,是指如果有一次拿的是1黄2绿,另一次也拿的是1黄2绿,它们的颜色状况就是完全相同。怎么说明呢?这就需要造抽屉,用抽屉原则来说明。随意拿出3个球,会有不同的状况,我们把它找全,每一种颜色状况就是一个抽屉,有多少种不同的颜色状况,就有多少个抽屉。
解:每次拿3个球,有10种不同的颜色状况,把这10种不同的颜色状况看成10个抽屉,拿的11次看成11个物体,根据抽屉原则一,把11个物体放入10个抽屉中,一定有两个或两个以上的物体。也就是说拿11次,一定至少有两次玻璃球的颜色状况完全相同。
例2:求证1997年1月出生的任意32个孩子中,至少有两个人是同一天出生的。
分析:1997年1月份共31天,为了回答上述问题,我们不妨假设1月份这31天为31个抽屉,而将1月份出生的任意32个孩子看作32个元素。根据抽屉原理一知,有一只抽屉里至少放入了两个元素。
解:答:1月份出生的任意32个孩子中,至少有两个人是同一天出生的。
练习:
1、求证:任意互异的8个整数中,一定存在6个整数x1、x2、x3、x4、x5、x6使得(x1-x2)·(x3-x4)·(x5-x6)恰是105的倍数。
分析:由于105=3×5×7,而3、5、7两两互质,所以只要能找到两个数,比如x1、x2,使得x1-x2是7的倍数,同理x3-x4是5的倍数,x5-x6是3的倍数,题目即得证。
解:根据抽屉原理一,在所给的任意8个整数中,必有两个整数被7除的余数相同,不妨设这两个数为x1、x2,则有7|(x1-x2),或表示为:x1-x2=7k1(其中k1为不等于零的整数)。在余下的6个数中,必有两个数被5除的余数相同,不妨设这两个数为x3、x4,使得x3、x4满足:x3-x4=5k2(k2为非零整数)。在余下的4个数中,必有两个整数被3除所得余数相同,不妨设这两个数为x5、x6,使得x5-x6=3k3(k3为非零整数)。
(x1-x2)·(x3-x4)·(x5-x6)
=7k1·5k2·3k3
=105×整数
即:从任意给定的互异的8个整数中,一定可以找到6个数x1、x2、x3、x4、x5、x6使得(x1-x2)·(x3-x4)·(x5-x6)是105的倍数。
2、一个袋里有四种不同颜色的小球,每次摸出两个,要保证有10次所摸的结果是一样的,至少要摸多少次?
分析:当摸出的两个球的颜色相同时,可以有四种不同的结果。当摸出的两个球的颜色不同时,最多可以有3+2+1种不同的结果。将上述10种不同的结果作为10个抽屉。
解:要求10次摸出的结果相同,依抽屉原理二,至少要摸9×10+1=91(次)。
3、 一个圆上有40条直径,在每条直径两端各填上一个数,所填数字可以从1到20中任意选。一定存在两条直径,两端点数字之和相等。
分析:我们做抽屉的方向一定是当每条直径的两端从1到20中任选数字填在上面时,会有多少种不同的和。把这些不同的和分别作为抽屉。再去与直径的条数做比较,就可以得出结论。
解:直径两端和最小的是2,最大的是40。因此,共有39种不同的和,把39种不同的和看成39个抽屉,直径的条数是40,大于39,所以一定存在着两条直径,两端数字之和相等。
4、能否在8行8列的方格表的每一个空格中分别填上1、2、3这三个数字中的任意一个,使得每一行、每一列及对角线AC、BD上的各个数字的和各不相同?对你的结论加以说明。
分析与解答:8行8列及两条对角线,共有18条“线”,每条“线”上都填有8个数字,要使各条“线”上的数字和均不相同,那么各条“线”上的数字和的取值情况应不少于18种。下面我们来分析一下各条“线”上取不同和的情况有多少种。如果某一条“线”上的8个数字都填上最小的数1,则可得到数字和的最小值8;如果某一条“线”上的8个空格中都填上最大的数3,那么可得到数字和的最大值24。由于数字及数字和均为整数,所以从8到24共有17种不同的值。我们将数字和的17种不同的值看作17个抽屉,而将18条“线”看作18个元素。根据抽屉原理一,将18个元素放入17个抽屉中,一定有一只抽屉中放入了至少两个元素。即18条“线”上的数字和至少有两个相同,所以不可能使18条“线”上的各数字和互不相同。
5、由6个队参加的单循环比赛(每两个队都要比赛一场),无论比赛进行到什么时候,一定存在两个队,这两个队比赛过的场次数相同。
分析:无论比赛进行到什么时候,所有比赛过的比赛过的场次从0场到5场都有可能出现。因此,就会有5个不同的抽屉。
解:参赛的队有6个,有5个抽屉,根据抽屉原则一,无论比赛进行到什么时候,一定有两个队比赛过的场次相同。
原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体。
[证明](反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体。
[证明](反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.
原理1 2都是第一抽屉原理的表述
第二抽屉原理:
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
[证明](反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能
[证明](反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体。
[证明](反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.
原理1 2都是第一抽屉原理的表述
第二抽屉原理:
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
[证明](反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能
抽屉原理 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,有的抽屉可以放一个,有的可以放两个,有的可以放五个,但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。”
抽屉原理有时也被称为鸽巢原理(“如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子”)。它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原理。它是组合数学中一个重要的原理。
一. 抽屉原理最常见的形式
原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体。
[证明](反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体。
[证明](反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.
原理1 2都是第一抽屉原理的表述
第二抽屉原理:
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
[证明](反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能
二.应用抽屉原理解题
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
例1:400人中至少有两个人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个物体,由抽屉原理1可以得知:至少有两人的生日相同.
又如:我们从街上随便找来13人,就可断定他们中至少有两个人属相相同.
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.
解 :从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原理1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.
上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.(需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少.)
抽屉原理虽然简单,但应用却很广泛,它可以解答很多有趣的问题,其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。
(一) 整除问题
把所有整数按照除以某个自然数m的余数分为m类,叫做m的剩余类或同余类,用[0],[1],[2],…,[m-1]表示.每一个类含有无穷多个数,例如[1]中含有1,m+1,2m+1,3m+1,….在研究与整除有关的问题时,常用剩余类作为抽屉.根据抽屉原理,可以证明:任意n+1个自然数中,总有两个自然数的差是n的倍数。
例1 证明:任取8个自然数,必有两个数的差是7的倍数。
分析与解答 在与整除有关的问题中有这样的性质,如果两个整数a、b,它们除以自然数m的余数相同,那么它们的差a-b是m的倍数.根据这个性质,本题只需证明这8个自然数中有2个自然数,它们除以7的余数相同.我们可以把所有自然数按被7除所得的7种不同的余数0、1、2、3、4、5、6分成七类.也就是7个抽屉.任取8个自然数,根据抽屉原理,必有两个数在同一个抽屉中,也就是它们除以7的余数相同,因此这两个数的差一定是7的倍数。
例2:对于任意的五个自然数,证明其中必有3个数的和能被3整除.
证明∵任何数除以3所得余数只能是0,1,2,不妨分别构造为3个抽屉:
[0],[1],[2]
①若这五个自然数除以3后所得余数分别分布在这3个抽屉中,我们从这三个抽屉中各取1个,其和必能被3整除.
②若这5个余数分布在其中的两个抽屉中,则其中必有一个抽屉,包含有3个余数(抽屉原理),而这三个余数之和或为0,或为3,或为6,故所对应的3个自然数之和是3的倍数.
③若这5个余数分布在其中的一个抽屉中,很显然,必有3个自然数之和能被3整除.
例2′:对于任意的11个整数,证明其中一定有6个数,它们的和能被6整除.
证明:设这11个整数为:a1,a2,a3……a11 又6=2×3
①先考虑被3整除的情形
由例2知,在11个任意整数中,必存在:
3|a1+a2+a3,不妨设a1+a2+a3=b1;
同理,剩下的8个任意整数中,由例2,必存在:3 | a4+a5+a6.设a4+a5+a6=b2;
同理,其余的5个任意整数中,有:3|a7+a8+a9,设:a7+a8+a9=b3
②再考虑b1、b2、b3被2整除.
依据抽屉原理,b1、b2、b3这三个整数中,至少有两个是同奇或同偶,这两个同奇(或同偶)的整数之和必为偶数.不妨设2|b1+b2
则:6|b1+b2,即:6|a1+a2+a3+a4+a5+a6
∴任意11个整数,其中必有6个数的和是6的倍数.
例3: 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数.
分析:注意到这些数队以10的余数即个位数字,以0,1,…,9为标准制造10个抽屉,标以[0],[1],…,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数.
(二)面积问题
例:九条直线中的每一条直线都将正方形分成面积比为2:3的梯形,证明:这九条直线中至少有三条经过同一点.
证明:如图,设直线EF将正方形分成两个梯形,作中位线MN。由于这两个梯形的高相等, 故它们的面积之比等于中位线长的比,即|MH|:|NH| 。于是点H有确定的位置(它在正方形一对对边中点的连线上,且|MH|:|NH|=2:3). 由几何上的对称性,这种点共有四个(即图中的H、J、I、K).已知的九条适合条件的分割直线中的每一条必须经过H、J、I、K这四点中的一点.把H、J、I、K看成四个抽屉,九条直线当成9个物体,即可得出必定有3条分割线经过同一点.
(三)染色问题
例1正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.
证明:把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原理二,至少有三个面涂上相同的颜色.
例2 有5个小朋友,每人都从装有许多黑白围棋子的布袋中任意摸出3枚棋子.请你证明,这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。
分析与解答 首先要确定3枚棋子的颜色可以有多少种不同的情况,可以有:3黑,2黑1白,1黑2白,3白共4种配组情况,看作4个抽屉.根据抽屉原理,至少有两个小朋友摸出的棋子的颜色在同一个抽屉里,也就是他们所拿棋子的颜色配组是一样的。
例3:假设在一个平面上有任意六个点,无三点共线,每两点用红色或蓝色的线段连起来,都连好后,问你能不能找到一个由这些线构成的三角形,使三角形的三边同色?
解:首先可以从这六个点中任意选择一点,然后把这一点到其他五点间连五条线段,如图,在这五条线段中,至少有三条线段是同一种颜色,假定是红色,现在我们再单独来研究这三条红色的线。这三条线段的另一端或许是不同颜色,假设这三条线段(虚线)中其中一条是红色的,那么这条红色的线段和其他两条红色的线段便组成了我们所需要的同色三角形,如果这三条线段都是蓝色的,那么这三条线段也组成我们所需要的同色三角形。因而无论怎样着色,在这六点之间的所有线段中至少能找到一个同色三角形。
例3′(六人集会问题)证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
例3”:17个科学家中每个人与其余16个人通信,他们通信所讨论的仅有三个问题,而任两个科学家之间通信讨论的是同一个问题。证明:至少有三个科学家通信时讨论的是同一个问题。
解:不妨设A是某科学家,他与其余16位讨论仅三个问题,由鸽笼原理知,他至少与其中的6位讨论同一问题。设这6位科学家为B,C,D,E,F,G,讨论的是甲问题。
若这6位中有两位之间也讨论甲问题,则结论成立。否则他们6位只讨论乙、丙两问题。这样又由鸽笼原理知B至少与另三位讨论同一问题,不妨设这三位是C,D,E,且讨论的是乙问题。
若C,D,E中有两人也讨论乙问题,则结论也就成立了。否则,他们间只讨论丙问题,这样结论也成立。
三.制造抽屉是运用原则的一大关键
例1 从2、4、6、…、30这15个偶数中,任取9个数,证明其中一定有两个数之和是34。
分析与解答 我们用题目中的15个偶数制造8个抽屉:
凡是抽屉中有两个数的,都具有一个共同的特点:这两个数的和是34。现从题目中的15个偶数中任取9个数,由抽屉原理(因为抽屉只有8个),必有两个数在同一个抽屉中.由制造的抽屉的特点,这两个数的和是34。
例2:从1、2、3、4、…、19、20这20个自然数中,至少任选几个数,就可以保证其中一定包括两个数,它们的差是12。
分析与解答在这20个自然数中,差是12的有以下8对:{20,8},{19,7},{18,6},{17,5},{16,4},{15,3},{14,2},{13,1}。
另外还有4个不能配对的数{9},{10},{11},{12},共制成12个抽屉(每个括号看成一个抽屉).只要有两个数取自同一个抽屉,那么它们的差就等于12,根据抽屉原理至少任选13个数,即可办到(取12个数:从12个抽屉中各取一个数(例如取1,2,3,…,12),那么这12个数中任意两个数的差必不等于12)。
例3: 从1到20这20个数中,任取11个数,必有两个数,其中一个数是另一个数的倍数。
分析与解答 根据题目所要求证的问题,应考虑按照同一抽屉中,任意两数都具有倍数关系的原则制造抽屉.把这20个数按奇数及其倍数分成以下十组,看成10个抽屉(显然,它们具有上述性质):
{1,2,4,8,16},{3,6,12},{5,10,20},{7,14},{9,18},{11},{13},{15},{17},{19}。
从这10个数组的20个数中任取11个数,根据抽屉原理,至少有两个数取自同一个抽屉.由于凡在同一抽屉中的两个数都具有倍数关系,所以这两个数中,其中一个数一定是另一个数的倍数。
例4:某校校庆,来了n位校友,彼此认识的握手问候.请你证明无论什么情况,在这n个校友中至少有两人握手的次数一样多。
分析与解答 共有n位校友,每个人握手的次数最少是0次,即这个人与其他校友都没有握过手;最多有n-1次,即这个人与每位到会校友都握了手.然而,如果有一个校友握手的次数是0次,那么握手次数最多的不能多于n-2次;如果有一个校友握手的次数是n-1次,那么握手次数最少的不能少于1次.不管是前一种状态0、1、2、…、n-2,还是后一种状态1、2、3、…、n-1,握手次数都只有n-1种情况.把这n-1种情况看成n-1个抽屉,到会的n个校友每人按照其握手的次数归入相应的“抽屉”,根据抽屉原理,至少有两个人属于同一抽屉,则这两个人握手的次数一样多。
在有些问题中,“抽屉”和“物体”不是很明显的,需要精心制造“抽屉”和“物体”.如何制造“抽屉”和“物体”可能是很困难的,一方面需要认真地分析题目中的条件和问题,另一方面需要多做一些题积累经验。
抽屉原理
把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
形式一:证明:设把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+1
n个m 这与题设相矛盾。所以,至少有存在一个ai≥m+1
高斯函数:对任意的实数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:400人中至少有两个人的生日相同.分析:生日从1月1日排到12月31日,共有366个不相同的生日,我们把366个不同的生日看作366个抽屉,400人视为400个苹果,由表现形式1可知,至少有两人在同一个抽屉里,所以这400人中有两人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个苹果,由抽屉原理的表现形式1可以得知:至少有两人的生日相同.
例题2:任取5个整数,必然能够从中选出三个,使它们的和能够被3整除.
证明:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r0,r1,r2.至少有一类包含所给5个数中的至少两个.因此可能出现两种情况:1°.某一类至少包含三个数;2°.某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;若是第二种情况,在三类中各取一个数,其和也能被3整除..综上所述,原命题正确.
例题3:某校派出学生204人上山植树15301株,其中最少一人植树50株,最多一人植树100株,则至少有5人植树的株数相同.
证明:按植树的多少,从50到100株可以构造51个抽屉,则个问题就转化为至少有5人植树的株数在同一个抽屉里.
(用反证法)假设无5人或5人以上植树的株数在同一个抽屉里,那只有5人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:
4(50+51+…+100)=4× =15300<15301得出矛盾.因此,至少有5人植树的株数相同.
练习:1.边长为1的等边三角形内有5个点,那么这5个点中一定有距离小于0.5的两点.
2.边长为1的等边三角形内,若有n2+1个点,则至少存在2点距离小于 .
3.求证:任意四个整数中,至少有两个整数的差能够被3整除.
4.某校高一某班有50名新生,试说明其中一定有二人的熟人一样多.
5.某个年级有202人参加考试,满分为100分,且得分都为整数,总得分为10101分,则至少有3人得分相同.
“任意367个人中,必有生日相同的人。”
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
... ...
大家都会认为上面所述结论是正确的。这些结论是依据什么原理得出的呢?这个原理叫做抽屉原理。它的内容可以用形象的语言表述为:
“把m个东西任意分放进n个空抽屉里(m>n),那么一定有一个抽屉中放进了至少2个东西。”
在上面的第一个结论中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉,至少有2个东西在同一抽屉里。在第二个结论中,不妨想象将5双手套分别编号,即号码为1,2,...,5的手套各有两只,同号的两只是一双。任取6只手套,它们的编号至多有5种,因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉,至少有2个东西在同一抽屉里。
抽屉原理的一种更一般的表述为:
“把多于kn个东西任意分放进n个空抽屉(k是正整数),那么一定有一个抽屉中放进了至少k+1个东西。”
利用上述原理容易证明:“任意7个整数中,至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能,所以7个整数中至少有3个数除以3所得余数相同,即它们两两之差是3的倍数。
如果问题所讨论的对象有无限多个,抽屉原理还有另一种表述:
“把无限多个东西任意分放进n个空抽屉(n是自然数),那么一定有一个抽屉中放进了无限多个东西。”
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
1958年6/7月号的《美国数学月刊》上有这样一道题目:
“证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
这个问题可以用如下方法简单明了地证出:
在平面上用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+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素。”
抽屉原理有时也被称为鸽巢原理(“如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子”)。它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原理。它是组合数学中一个重要的原理。
一. 抽屉原理最常见的形式
原理1 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体。
[证明](反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),这不可能.
原理2 把多于mn个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体。
[证明](反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能.
原理1 2都是第一抽屉原理的表述
第二抽屉原理:
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
[证明](反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能
二.应用抽屉原理解题
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
例1:400人中至少有两个人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个物体,由抽屉原理1可以得知:至少有两人的生日相同.
又如:我们从街上随便找来13人,就可断定他们中至少有两个人属相相同.
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具,每个小朋友任意选择两件,那么不管怎样挑选,在任意七个小朋友中总有两个彼此选的玩具都相同,试说明道理.
解 :从三种玩具中挑选两件,搭配方式只能是下面六种:(兔、兔),(兔、熊猫),(兔、长颈鹿),(熊猫、熊猫),(熊猫、长颈鹿),(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉,把7个小朋友看作物体,那么根据原理1,至少有两个物体要放进同一个抽屉里,也就是说,至少两人挑选玩具采用同一搭配方式,选的玩具相同.
上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题,不错,这正是抽屉原则的主要作用.(需要说明的是,运用抽屉原则只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少.)
抽屉原理虽然简单,但应用却很广泛,它可以解答很多有趣的问题,其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。
(一) 整除问题
把所有整数按照除以某个自然数m的余数分为m类,叫做m的剩余类或同余类,用[0],[1],[2],…,[m-1]表示.每一个类含有无穷多个数,例如[1]中含有1,m+1,2m+1,3m+1,….在研究与整除有关的问题时,常用剩余类作为抽屉.根据抽屉原理,可以证明:任意n+1个自然数中,总有两个自然数的差是n的倍数。
例1 证明:任取8个自然数,必有两个数的差是7的倍数。
分析与解答 在与整除有关的问题中有这样的性质,如果两个整数a、b,它们除以自然数m的余数相同,那么它们的差a-b是m的倍数.根据这个性质,本题只需证明这8个自然数中有2个自然数,它们除以7的余数相同.我们可以把所有自然数按被7除所得的7种不同的余数0、1、2、3、4、5、6分成七类.也就是7个抽屉.任取8个自然数,根据抽屉原理,必有两个数在同一个抽屉中,也就是它们除以7的余数相同,因此这两个数的差一定是7的倍数。
例2:对于任意的五个自然数,证明其中必有3个数的和能被3整除.
证明∵任何数除以3所得余数只能是0,1,2,不妨分别构造为3个抽屉:
[0],[1],[2]
①若这五个自然数除以3后所得余数分别分布在这3个抽屉中,我们从这三个抽屉中各取1个,其和必能被3整除.
②若这5个余数分布在其中的两个抽屉中,则其中必有一个抽屉,包含有3个余数(抽屉原理),而这三个余数之和或为0,或为3,或为6,故所对应的3个自然数之和是3的倍数.
③若这5个余数分布在其中的一个抽屉中,很显然,必有3个自然数之和能被3整除.
例2′:对于任意的11个整数,证明其中一定有6个数,它们的和能被6整除.
证明:设这11个整数为:a1,a2,a3……a11 又6=2×3
①先考虑被3整除的情形
由例2知,在11个任意整数中,必存在:
3|a1+a2+a3,不妨设a1+a2+a3=b1;
同理,剩下的8个任意整数中,由例2,必存在:3 | a4+a5+a6.设a4+a5+a6=b2;
同理,其余的5个任意整数中,有:3|a7+a8+a9,设:a7+a8+a9=b3
②再考虑b1、b2、b3被2整除.
依据抽屉原理,b1、b2、b3这三个整数中,至少有两个是同奇或同偶,这两个同奇(或同偶)的整数之和必为偶数.不妨设2|b1+b2
则:6|b1+b2,即:6|a1+a2+a3+a4+a5+a6
∴任意11个整数,其中必有6个数的和是6的倍数.
例3: 任意给定7个不同的自然数,求证其中必有两个整数,其和或差是10的倍数.
分析:注意到这些数队以10的余数即个位数字,以0,1,…,9为标准制造10个抽屉,标以[0],[1],…,[9].若有两数落入同一抽屉,其差是10的倍数,只是仅有7个自然数,似不便运用抽屉原则,再作调整:[6],[7],[8],[9]四个抽屉分别与[4],[3],[2],[1]合并,则可保证至少有一个抽屉里有两个数,它们的和或差是10的倍数.
(二)面积问题
例:九条直线中的每一条直线都将正方形分成面积比为2:3的梯形,证明:这九条直线中至少有三条经过同一点.
证明:如图,设直线EF将正方形分成两个梯形,作中位线MN。由于这两个梯形的高相等, 故它们的面积之比等于中位线长的比,即|MH|:|NH| 。于是点H有确定的位置(它在正方形一对对边中点的连线上,且|MH|:|NH|=2:3). 由几何上的对称性,这种点共有四个(即图中的H、J、I、K).已知的九条适合条件的分割直线中的每一条必须经过H、J、I、K这四点中的一点.把H、J、I、K看成四个抽屉,九条直线当成9个物体,即可得出必定有3条分割线经过同一点.
(三)染色问题
例1正方体各面上涂上红色或蓝色的油漆(每面只涂一种色),证明正方体一定有三个面颜色相同.
证明:把两种颜色当作两个抽屉,把正方体六个面当作物体,那么6=2×2+2,根据原理二,至少有三个面涂上相同的颜色.
例2 有5个小朋友,每人都从装有许多黑白围棋子的布袋中任意摸出3枚棋子.请你证明,这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。
分析与解答 首先要确定3枚棋子的颜色可以有多少种不同的情况,可以有:3黑,2黑1白,1黑2白,3白共4种配组情况,看作4个抽屉.根据抽屉原理,至少有两个小朋友摸出的棋子的颜色在同一个抽屉里,也就是他们所拿棋子的颜色配组是一样的。
例3:假设在一个平面上有任意六个点,无三点共线,每两点用红色或蓝色的线段连起来,都连好后,问你能不能找到一个由这些线构成的三角形,使三角形的三边同色?
解:首先可以从这六个点中任意选择一点,然后把这一点到其他五点间连五条线段,如图,在这五条线段中,至少有三条线段是同一种颜色,假定是红色,现在我们再单独来研究这三条红色的线。这三条线段的另一端或许是不同颜色,假设这三条线段(虚线)中其中一条是红色的,那么这条红色的线段和其他两条红色的线段便组成了我们所需要的同色三角形,如果这三条线段都是蓝色的,那么这三条线段也组成我们所需要的同色三角形。因而无论怎样着色,在这六点之间的所有线段中至少能找到一个同色三角形。
例3′(六人集会问题)证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
例3”:17个科学家中每个人与其余16个人通信,他们通信所讨论的仅有三个问题,而任两个科学家之间通信讨论的是同一个问题。证明:至少有三个科学家通信时讨论的是同一个问题。
解:不妨设A是某科学家,他与其余16位讨论仅三个问题,由鸽笼原理知,他至少与其中的6位讨论同一问题。设这6位科学家为B,C,D,E,F,G,讨论的是甲问题。
若这6位中有两位之间也讨论甲问题,则结论成立。否则他们6位只讨论乙、丙两问题。这样又由鸽笼原理知B至少与另三位讨论同一问题,不妨设这三位是C,D,E,且讨论的是乙问题。
若C,D,E中有两人也讨论乙问题,则结论也就成立了。否则,他们间只讨论丙问题,这样结论也成立。
三.制造抽屉是运用原则的一大关键
例1 从2、4、6、…、30这15个偶数中,任取9个数,证明其中一定有两个数之和是34。
分析与解答 我们用题目中的15个偶数制造8个抽屉:
凡是抽屉中有两个数的,都具有一个共同的特点:这两个数的和是34。现从题目中的15个偶数中任取9个数,由抽屉原理(因为抽屉只有8个),必有两个数在同一个抽屉中.由制造的抽屉的特点,这两个数的和是34。
例2:从1、2、3、4、…、19、20这20个自然数中,至少任选几个数,就可以保证其中一定包括两个数,它们的差是12。
分析与解答在这20个自然数中,差是12的有以下8对:{20,8},{19,7},{18,6},{17,5},{16,4},{15,3},{14,2},{13,1}。
另外还有4个不能配对的数{9},{10},{11},{12},共制成12个抽屉(每个括号看成一个抽屉).只要有两个数取自同一个抽屉,那么它们的差就等于12,根据抽屉原理至少任选13个数,即可办到(取12个数:从12个抽屉中各取一个数(例如取1,2,3,…,12),那么这12个数中任意两个数的差必不等于12)。
例3: 从1到20这20个数中,任取11个数,必有两个数,其中一个数是另一个数的倍数。
分析与解答 根据题目所要求证的问题,应考虑按照同一抽屉中,任意两数都具有倍数关系的原则制造抽屉.把这20个数按奇数及其倍数分成以下十组,看成10个抽屉(显然,它们具有上述性质):
{1,2,4,8,16},{3,6,12},{5,10,20},{7,14},{9,18},{11},{13},{15},{17},{19}。
从这10个数组的20个数中任取11个数,根据抽屉原理,至少有两个数取自同一个抽屉.由于凡在同一抽屉中的两个数都具有倍数关系,所以这两个数中,其中一个数一定是另一个数的倍数。
例4:某校校庆,来了n位校友,彼此认识的握手问候.请你证明无论什么情况,在这n个校友中至少有两人握手的次数一样多。
分析与解答 共有n位校友,每个人握手的次数最少是0次,即这个人与其他校友都没有握过手;最多有n-1次,即这个人与每位到会校友都握了手.然而,如果有一个校友握手的次数是0次,那么握手次数最多的不能多于n-2次;如果有一个校友握手的次数是n-1次,那么握手次数最少的不能少于1次.不管是前一种状态0、1、2、…、n-2,还是后一种状态1、2、3、…、n-1,握手次数都只有n-1种情况.把这n-1种情况看成n-1个抽屉,到会的n个校友每人按照其握手的次数归入相应的“抽屉”,根据抽屉原理,至少有两个人属于同一抽屉,则这两个人握手的次数一样多。
在有些问题中,“抽屉”和“物体”不是很明显的,需要精心制造“抽屉”和“物体”.如何制造“抽屉”和“物体”可能是很困难的,一方面需要认真地分析题目中的条件和问题,另一方面需要多做一些题积累经验。
抽屉原理
把八个苹果任意地放进七个抽屉里,不论怎样放,至少有一个抽屉放有两个或两个以上的苹果。抽屉原则有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题,因此,也称为狄利克雷原则。它是组合数学中一个重要的原理。把它推广到一般情形有以下几种表现形式。
形式一:证明:设把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+1
n个m 这与题设相矛盾。所以,至少有存在一个ai≥m+1
高斯函数:对任意的实数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:400人中至少有两个人的生日相同.分析:生日从1月1日排到12月31日,共有366个不相同的生日,我们把366个不同的生日看作366个抽屉,400人视为400个苹果,由表现形式1可知,至少有两人在同一个抽屉里,所以这400人中有两人的生日相同.
解:将一年中的366天视为366个抽屉,400个人看作400个苹果,由抽屉原理的表现形式1可以得知:至少有两人的生日相同.
例题2:任取5个整数,必然能够从中选出三个,使它们的和能够被3整除.
证明:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r0,r1,r2.至少有一类包含所给5个数中的至少两个.因此可能出现两种情况:1°.某一类至少包含三个数;2°.某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;若是第二种情况,在三类中各取一个数,其和也能被3整除..综上所述,原命题正确.
例题3:某校派出学生204人上山植树15301株,其中最少一人植树50株,最多一人植树100株,则至少有5人植树的株数相同.
证明:按植树的多少,从50到100株可以构造51个抽屉,则个问题就转化为至少有5人植树的株数在同一个抽屉里.
(用反证法)假设无5人或5人以上植树的株数在同一个抽屉里,那只有5人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:
4(50+51+…+100)=4× =15300<15301得出矛盾.因此,至少有5人植树的株数相同.
练习:1.边长为1的等边三角形内有5个点,那么这5个点中一定有距离小于0.5的两点.
2.边长为1的等边三角形内,若有n2+1个点,则至少存在2点距离小于 .
3.求证:任意四个整数中,至少有两个整数的差能够被3整除.
4.某校高一某班有50名新生,试说明其中一定有二人的熟人一样多.
5.某个年级有202人参加考试,满分为100分,且得分都为整数,总得分为10101分,则至少有3人得分相同.
“任意367个人中,必有生日相同的人。”
“从任意5双手套中任取6只,其中至少有2只恰为一双手套。”
“从数1,2,...,10中任取6个数,其中至少有2个数为奇偶性不同。”
... ...
大家都会认为上面所述结论是正确的。这些结论是依据什么原理得出的呢?这个原理叫做抽屉原理。它的内容可以用形象的语言表述为:
“把m个东西任意分放进n个空抽屉里(m>n),那么一定有一个抽屉中放进了至少2个东西。”
在上面的第一个结论中,由于一年最多有366天,因此在367人中至少有2人出生在同月同日。这相当于把367个东西放入 366个抽屉,至少有2个东西在同一抽屉里。在第二个结论中,不妨想象将5双手套分别编号,即号码为1,2,...,5的手套各有两只,同号的两只是一双。任取6只手套,它们的编号至多有5种,因此其中至少有两只的号码相同。这相当于把6个东西放入5个抽屉,至少有2个东西在同一抽屉里。
抽屉原理的一种更一般的表述为:
“把多于kn个东西任意分放进n个空抽屉(k是正整数),那么一定有一个抽屉中放进了至少k+1个东西。”
利用上述原理容易证明:“任意7个整数中,至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能,所以7个整数中至少有3个数除以3所得余数相同,即它们两两之差是3的倍数。
如果问题所讨论的对象有无限多个,抽屉原理还有另一种表述:
“把无限多个东西任意分放进n个空抽屉(n是自然数),那么一定有一个抽屉中放进了无限多个东西。”
抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。
1958年6/7月号的《美国数学月刊》上有这样一道题目:
“证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”
这个问题可以用如下方法简单明了地证出:
在平面上用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个人以前彼此不相识。不论哪种情形发生,都符合问题的结论。
六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例,这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。从六人集会问题的证明中,我们又一次看到了抽屉原理的应用。
相关问答
抽屉的屉怎么读
抽屉的屉怎么读 拼音:tì 简体部首:尸 五笔:NANV 总笔画:8 解释: 1.器物中可以拿出的盛放物体的部分,常常是匣形或是分层的格架:抽~。笼~。 2.某些床或椅子的架子上可以取下的部分:床...
全文抽屉原理
5+1=6 用假设法解释:如果取到的手套全都是正面或反面的,最多能取5次,第6次取到的必定是相反的手套,这样就能成为一双。所以至少要取出6只手套。
抽屉原理
原理 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里有2个或2个以上的物体 原理2 把多于mn(m乘以n)个的物体放到n个抽屉里,则至少有一个抽屉里有m+1个或多于m+1个的物体。 1....
全文妈妈的抽屉里可能会写些什么?
妈妈的抽屉里可能写的最多的就是你们生活中一些让她感到开心幸福的事情或者不高兴的事情。 还有就是记录你们的成长的一些事情和对你们的希望。 还有就是和你父亲的一些情感方面的问题。
抽屉原理是谁发现的
抽屉原理又称鸽巢原理,它是组合数学的一个基本原理,最先是由德国数学家狭利克雷提出来的,因此,也称为狭利克雷原理或狄利克雷原则。
抽屉原理是什么
抽屉原理:桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集...
全文抽屉原理是谁发明的
狄利克雷。抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里至少有两个元素.”抽屉原理有时也被称为...
全文抽屉原理是谁发现的?
三个公式: 1、把多于n+1个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。 2、把多于mn+1个的物体放到n个抽屉里,则至少有一个抽屉里有不少于m+1的物体。 3、把无穷多件物体...
全文热门问答
- 1天道好玩吗?
- 2求解 这句话的意思:杀强官弱,注意离婚再嫁良夫
- 3如何评价电影《何以为家》?
- 4秦时明月中墨儿是谁
- 5为何孙悟空,猪八戒,沙僧都不敢骑白龙马?
- 6没有吃到苦,哪能尝到甜的滋味。什么意思?
- 7除超级英雄电影外改编自漫画的好莱坞电影有哪些?
- 8在西方文明史中书籍起到了怎样的作用和贡献?
- 9七龙珠哪一集有超级赛亚人4?
- 10Mr英语什么意思?音标怎么写的?
- 11死神完结了吗
- 12一什么鱼塘
- 1380-85连环画能卖多少钱?
- 14萱草的花语是什么
- 15一道简单智力题
- 16一部奥特曼电影,很久以前看的有点不记得了,开头讲一个男意外获得了赛罗的变身器,他们好像就一群人还
- 17一石二鸟的典故?
- 18荒岛余生的主要内容是什么
- 19抹香鲸的生活习性
- 20怎么样才能增高呢
- 21有一部小说我忘记名字了,结局是女主离开男主生了一个女儿在国外生活,但最后他们还是团聚咯求名字求名字啊
- 22亲们介绍几部优秀的动画片看看,最好是国产的?
- 23中文翻译成韩语,谢谢^^
- 24史莱克七怪到最后的魂环都是什么颜色的?
- 25求关于主角男扮女装(或女扮男装)的动漫
- 2630KM是多少里路啊
- 27求电视剧名字(演员也不知道)
- 28儿子今年刚上小学,我想给他买英语方面的学习磁带听。买什么好呢?请网友们给个建议呢。
- 29长弓手的《无限恐怖》第四部什么时候出版?
- 30求星无言的小说最好女尊的女主要强大小虐也可以
热门搜索更多
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- X
- Y
- Z
- 爱过了恨过了放下吧佛歌原唱
- 阿坝蜂王和中蜂蜂王的区别
- 爱尔兰旅游景点
- 爱护小树苗看图说话
- 爱奇艺投屏会员
- 阿胶阿胶的作用和功效
- 爱的荡漾国语版全集
- 安眠的纯音乐
- 爱情的情话短句
- 安全文章精选500字
- 安居乐业造句子
- 安全方面的幼儿歌曲有哪些
- 安徽理工大学招生分数线
- 傲慢与偏见英国版
- 暗花电影
- 暗格里的秘密哪里可以免费观看
- 阿长与山海经阅读心得
- ai朗读配音
- 爱莲说mp3
- 安全第一儿歌
- 爱阅读小说网
- 奥运会篮球西班牙
- 阿胶浆增强免疫力
- 安徒生童话主要内容50字左右
- 安徽芜湖天气预报
- 阿神的实况教
- 爱您是我难言的痛
- 澳洲大学专业排名榜
- 爱丽丝梦游仙境梗概英文版
- 安慰失眠人的句子
- 白夜行亮司和雪穗
- 补充养老金
- 北京三十天的天气预报
- 巴山楚水凄凉地
- 不乱丢垃圾作文
- 不良人第三部
- 北京郭德纲
- 板砖修仙者2全集
- 冰莲花叶罗丽精灵梦
- 不良人侯卿广播剧全集
- 鞭炮声音效mp3
- 办公室搞笑段子大全爆笑视频
- 巴黎野玫瑰
- 悲惨世界名著
- 表扬孩子乐于助人的话
- 白蛇传第二部
- 北京舞蹈学院研究生
- 包青天电视剧93版不卡免费观看
- 霸王龙的玩偶
- 不开心的英语翻译
- 八三版射雕英雄传主题曲
- 百年孤独作者马尔克斯
- 八上古诗词鉴赏
- 博伽梵往世书
- 表格制作
- 宝可梦日月动画
- 背诵的内容
- 八仙在哪里过海
- 本番
- 百家讲坛王立群史记全集
- 陈逸安相声
- 创新主题的相声
- 吃糖糕琴书
- 慈溪快板说唱老话
- 程久红说快板
- 传统相声打捧哏
- 蔡小五评书
- 常富宽相声
- 粗野的快板音乐风格
- 蔡文利二人转
- 初级入门快板
- 潮汕快板呱仔
- 蔡明当评委的相声
- 崔增光快板
- 吃粽子快板
- 陈佩斯岳云鹏孟鹤堂相声
- 潮汕女人说书
- 传统相声名家
- 蔡小分二人转
- 参加相声大赛
- 程贵田相声
- 唱戏配的快板
- 畜类拔萃相声
- 茶馆之说书人小说免费阅读
- 初二人转
- 出现在相声作品里
- 春节大鼓素材
- 崔莺莺小红娘二人转
- 春节联合会相声
- 唱鼓词金丝带
- 第3套全国小学生广播体操
- 动物谜语儿童5一6
- 地铁的英文单词怎么读
- 电竞大神爱上我莫北
- 都市超级医圣葛东旭免费阅读全文
- 大汗行宫介绍
- 都市极品神医免费全文阅读
- 大学物理学教材
- 大秦帝国之纵横天下
- 的功效与作用及禁忌
- 单机角色手游
- 豆腐猪血的功效与作用
- 点歌的人原唱完整版mp3
- 电台暖心小短文文本
- 毒蛙
- 电影道士下山
- 狄成狂枭小说
- 当下的力量吧
- 杜甫论诗绝句
- 东东的不死传说
- 打篮球的300字作文
- 大叔适渴而止全文免费
- 蛋挞皮有几种做法
- 大宋少年志免费下载
- 大青树下的小学人教版
- 弹丸论破动漫第一季
- 代号幽灵的特种兵小说
- 大拇指上有个硬块
- 大学材料科学与工程是什么专业
- 蛋黄果的功效
- 二人转梁红唱小拜年
- 二人转三娘教子上下集
- 二人转小全集大全
- 二人转玉米牙
- 二人转新婚夜闹洞房
- 二人转全本正戏哭戏
- 二人转白小姐
- 儿童快板表演歌颂祖国
- 二人转四大骚
- 二人转演员改行游戏主播
- 二人转鞋拔子
- 二人转魏三搞笑女扮男装
- 二人转楼台会韩子平全集
- 儿时玩伴相声小品
- 二人转演员黄英的照片
- 二人转全部正戏包公吊孝
- 儿童学琴书
- 二人转的素材
- 二人转演员姜大成正戏
- 二人转二人转孟姜女哭长城
- 二人转女夹男
- 儿童长杉相声服
- 二人转演员何晓影多大岁数
- 二人转保定
- 二人转武松哭灵选段
- 二人转起源于辽宁
- 二人转演员男胖子
- 二人转董明珠唱的黄梅戏
- 二人转京东大鼓前奏简谱
- 二人转红尘情歌
- 非凡中文儿歌钢琴结尾万能
- 防烫伤儿歌
- 菲儿歌曲爱情36度8字幕
- 方言背儿歌
- 放首儿歌鲁冰花歌曲
- 放小鸭嘎嘎儿歌
- 防涨水儿歌
- 丰收的儿歌快乐的唱
- 放风筝的儿歌大全
- 菲儿歌曲情歌对唱十五首
- 飞吧小蜜蜂儿歌的歌词
- 放生歌曲简谱儿歌钢琴版
- 方言念儿歌
- 番茄酱英文儿歌律动完整版
- 复习儿歌导入部分
- 父亲这首儿歌怎么唱
- 非常有趣的儿歌有哪些
- 放一个儿歌动画版
- 仿写一首传统特殊儿歌
- 防溺水儿歌手势版
- 飞跃四季的英文儿歌怎么读
- 菲儿歌曲联唱千年等一回
- 飞来三只啄木鸟儿歌
- 菲儿歌曲你是唐曾还是法海
- 饭前洗手的儿歌
- 仿写儿歌前面空两格吗
- 福禄寿乐队杜雪儿歌曲
- 仿写跟谁走儿歌一年级
- 蜂的拼音儿歌大全简单
- 发现一只小猫儿歌
- 关于咖啡感悟人生的优美句子
- 郭子仪与李白
- 古典音乐的特点
- 高级感女生头像动漫
- 感觉自己活着很累
- 高中语文被动句
- 国外自由行旅游
- 关公拿刀有什么讲究
- 歌曲拔根芦柴花原唱
- 歌曲就忘了吧
- 钢琴 纯音乐
- 广场舞多情的月亮
- 格尔木大草原
- 狗尾续貂是什么意思成语故事
- 国家公务员职位级别
- 光棍电影院手机在线
- 光子嫩肤护肤
- 广播节目单
- 古代超级搞笑古言小说
- 哥谭第二季全集免费
- 更换汽车灯泡
- 歌曲赢天下
- 鬼头桃菜
- 鬼谷子什么书
- 关于春天的美文美段
- 歌颂祖国的纯音乐
- 跟女生聊天的正确打开方式
- 国学经典自我介绍
- 桂林阳朔必玩旅游景点
- 瓜子听书
- 和马季说相声的搭档
- 狐狸英语怎么读
- 菏泽郓城快板
- 河洛大鼓呼延庆打擂
- 红色的英语单词怎么读
- 火山二人转七岁红直播
- 黄氏女游阴二人转
- 互损比相声还劲爆
- 衡阳渔鼓传承人蒋中良
- 呼家将43集评书
- 黑呼转评书
- 黑妖二人转
- 湖南相声演员田汉
- 黄小飞二人转最新演出
- 湖南南风艺术培训学校音乐
- 海滩大鼓包
- 回龙传河洛大鼓
- 红楼梦20回评书
- 欢乐喜剧人相声团体排名
- 呼市大盛魁相声茶馆电话
- 好梦春相声
- 黄莺声相声词
- 华娱之印象轻言说书人
- 和珅的真实医生长篇评书
- 邯郸市武安县快板
- 侯宝林相声经典下象棋
- 红色的英语怎么读
- 华县说书大全
- 红梅随想曲快板
- 韩云飞李增瑞相声大全
- 经典搞笑的儿歌有哪些
- 江上渔者小班儿歌
- 接吻鱼儿歌
- 犟马儿歌曲
- 经典儿歌演奏弹唱
- 金牌每课通一年级上英语
- 九年级下册英语7单元
- 剑桥彩虹少儿英语第2集
- 加油英语儿歌
- 吉的堡少儿英语还有吗
- 进场儿歌
- 鸡英语儿歌
- 加油鸭儿歌舞蹈完整版
- 介绍小学用英语
- 嘉定区少儿英语口语
- 景色很美儿歌
- 蒋小函的儿歌有哪些歌词
- 脚丫太大儿歌
- 剂的拼音儿歌启蒙
- 绝句儿歌律动
- 金泫雅red儿歌
- 冀教版小学英语利弊
- 今天是正月初一英语怎么说
- 贾玲唱的儿歌大全
- 家里有只小羊羔儿歌
- 今夜dj儿歌
- 简短舒缓儿歌有哪些歌名
- 金猪宝贝儿歌
- 吉多烈儿歌歌词
- 吉他入门零基础儿歌弹唱
- 快乐过六一儿歌
- 开心豆少儿英语 级别
- 开头是两只老虎是什么儿歌
- 酷酷的卡车儿歌歌词歌谱
- 快乐小宝贝抓蝴蝶儿歌
- 开小差儿歌
- 开心儿歌是哪个公司的产品
- 客家童谣找马儿歌
- 快乐一家的儿歌
- 看完儿歌300首的读后感
- 卡车挖掘机的儿歌
- 开学啦儿童儿歌
- 快乐宝宝卡通儿歌
- 考虑英文儿歌弹唱面试题目
- 快乐家的小宝贝儿歌
- 快乐的六一儿歌五线谱
- 口才儿歌情景剧
- 可爱的宠物去哪了儿歌
- 开心版英语三年级上册mp3
- 困难的拼音儿歌大全歌
- 看世界儿歌
- 口香糖儿歌
- 可爱的小动物完整儿歌内容
- 开在荒野的花儿歌词
- 口手目耳足的儿歌
- 可以比赛的儿歌钢琴曲
- 可爱的孩子上学啦儿歌
- 快乐英文儿歌简笔
- 哭着叫爸爸的儿歌叫什么
- 磕儿歌原唱张冬玲牛在飞
- 陆少的暖婚
- 老韩
- 蓝色骨头
- 灵霄宝殿
- 榴莲飘飘
- 鹭科
- 李东勋
- 鹭群
- 鹿鼎记电影
- 莲隐
- 陆谷孙
- 励志剧
- 六零年代空间女
- 灵果
- 领悟能力
- 灵吉菩萨
- 老鼠精
- 龙血神帝
- 蓝妮
- 陆原李梦瑶
- 刘彻
- 陆观澜
- 老年迪斯科
- 隆裕皇后
- 蓝风筝
- 流星蝴蝶剑下载
- 雷锋做好事
- 李统藏
- 鹭类
- 梨花如雪
- 马三立 单口相声
- 明太鱼的营养
- 漫威之我的超能力女儿
- 免费阅读我的徒弟都是大反派
- 漫画在线看
- 卖报小郎君原来我是妖二代
- 每当我走过老师的窗前简谱
- 漫画史上最强赘婿
- 免费pdf转word软件
- 马齿苋晒干的方法
- 磨耳朵英语音频
- 美女与野兽格林童话
- 明天会更好歌歌曲歌词
- 免费的少年派2
- 孟嘉
- 免费听小说相遇终有时
- 免费听音乐的软件推荐
- 魔道祖师番外草丛
- 莫扎特在线音乐播放
- 描述心情的50个英语形容词
- 明哲保身的意思解释
- 免费大学生简历模板
- 马浚伟
- 民间歇后语
- 民调局异闻录全文免费
- 母女系列小说
- 猫咪开心叫声
- 描写一种昆虫的作文
- mp4音乐格式转换器
- mp4歌曲免费下载高清
- 女生搞笑名字
- 怒放电视剧全集下载
- 泥疗膏的功效
- 你是不是欠g了阅读txt下载
- 女人花二胡曲
- 哪吒汽车v价格
- 暖心甜妻:凌总晚安
- 女人胸无遮
- 女儿情原唱吴静歌曲
- 娘子周杰伦
- 暖心伤感情话短句
- 逆天超市系统
- 你好旧时光结局怎么样
- 女神的上门医婿免费阅读
- 牛郎织女的故事英文版简短
- 你在他乡还好吗艾可儿歌词
- 纽约英语
- 南屏晚钟纯音乐
- 倪海厦视频教程全集伤寒论
- 女总裁的女总裁的贴身兵王
- 南风天
- 你好星期六2023莲花楼
- 南昌到昆明旅游团报价
- 南昌旅游景点攻略
- 女生有双下巴怎么减掉
- 你的圈子决定了你的人生
- 女人低调而又霸气的句子
- 你不懂我我不怪你余秋雨
- 女人戴蜜蜡的功效与作用
- 南太湖旅游度假区
- old macdonald歌曲三年级英语
- or英语造句三年级简单
- 欧美小学生怎么学英语的
- 欧洲小学生英语
- 欧美小学生怎么学英语写作
- 欧洲小学生英语水平等级
- 欧美小学生英语分级
- 欧啦英语三年级上册
- orange的用法三年级英语
- 欧美小学生英语
- 欧文小学生英语
- 偶遇英语小学生
- oh三年级英语什么意思
- 欧洲小学生自学英语难吗
- 瓯海区小学三年级英语
- 欧洲小镇三年级作文英语
- 欧洲三年级造句英语简单
- on the farm英语儿歌三年级
- 偶遇造句子三年级上册英语
- O元三年级英语上册跟读
- our school三年级英语28页
- 欧拉英语译林三年级
- ot三年级英语单词
- 欧美小学生学英语
- owl三年级英语单词
- 欧洲小学生自学英语软件
- 偶遇小学生英语
- 欧美小学生怎么学英语好
- 欧洲小学生自学英语
- 欧洲小学生英语水平考试
- 皮沙发掉漆后如何修复
- 普组词是什么
- 皮肤黑素怎么改善
- 琵琶语手机铃声免费下载
- 缥缈有声小说在线
- 鹏易哥哥讲的睡前故事
- 苹果手机怎么边打游戏边听歌
- 朋友别哭萨克斯演奏降e
- 漂亮美人鱼
- 琵琶行歌曲和原文一样吗
- 破天一剑手游
- 蒲松龄促织
- 评书,岳飞传
- 拍照翻译英语单词
- 破格-强者思维
- 普陀山旅游西天景区
- 菩提子是什么树上的
- 陪读妈妈的完整版故事
- 泡泡影视天堂影视
- 跑车儿歌
- 琵琶行的音频
- 平定安史之乱是谁
- 霹雳全集顺序
- 盆底肌肉松驰
- 品传统文化
- 攀枝花高铁时刻表
- pdf下载免费中文版
- 破釜沉舟小古文朗读视频
- 朋友的姐姐电影观看
- 泡茶是用生决明子还是熟决明子
- 全能相师有声小说在线收听
- 情牵梦爱有声小说
- 全知读者视角有声读物
- 屈原郭沫若
- 启蒙有声书英语
- 七猫小说怎么有声版本
- 汽车总动员故事
- 曲黎敏有声书
- 求放过有声小说
- 青云仕途关晓凡有声小说
- 迁坟的小说有声
- 青岛出版社会说话儿童有声书
- 七年级上册政治知识点
- 穷爸爸富爸爸英文有声读物
- 趣威新年有声书
- 情景配乐有声小说有哪些
- 庆余年有声书种子
- 妻荣夫贵之穿越星际有声小说
- 千古玦尘小说有声版
- 全能鬼剑系统
- 庆余年469有声小说
- 青囊尸衣2有声小说在线收听
- 情色有声书
- 去有声读物
- 权力争锋有声小说在线免费收听
- 青雪主讲有声小说之盗墓笔记
- 琴帝有声小说手机版本
- 全校都以为我们是死敌有声小说
- 妻子的淫语有声读物
- 乾隆皇帝有声小说任景
- 人生若只如初见的美句
- 任达华翁虹演的电影
- 如沟通和已沟通的区别
- 热提拉美容抗皱
- 人们尊重自然的例子
- 人的日语怎么说
- 日本女同电视剧
- 人际互动的主要形式
- 人皮书
- 人教版pep英语六年级上册
- 若羌红枣多少钱一斤
- 人道大圣小说免费看
- 日语日期的读法
- 人生金句名言
- 儒林外史中范进的故事
- 人生失去目标
- 绕口令 英文
- 儒林外史第十三回
- 认识自己从了解情绪开始
- 日语电视剧双字幕版
- 任天堂switch游戏下载
- 人教版六年级英语重点知识点总结
- 让我遗憾的一件事作文
- 容易入睡的睡前故事
- 日语问候语
- 人生不如意的感悟句子
- 仁爱英语八年级下册单词默写版
- 如何学考驾照
- 壬辰寒食阅读答案
- 如何配汽车钥匙
- 深圳英语中考听说训练
- 厦门中考英语试卷上海
- 深圳中考英语占比重
- 商丘中考英语怎样学好
- 苏州中考英语满分的人
- 山西中考线上考试英语
- 深圳中考英语经验分享
- 山东安徽中考英语
- 苏州2021英语中考指南
- 山东枣庄中考英语复习
- 苏州 中考英语作文分数
- 深圳英语中考模拟盐田
- 深圳中考英语考完
- 山西中考英语高频短语
- 深圳中考英语作文得分
- 陕西中考英语情况分析
- 上海英语三模中考
- 上海 中考 英语语法
- 上海中考英语包含
- 思博中考卷英语
- 厦门中考2023英语试卷
- 深圳中考英语初三
- 松滋中考2021试卷英语
- 上海2022英语中考听力
- 苏州英语中考单词练习
- 时尚词汇闪过英语中考
- 深圳龙岗中考英语作文
- 苏州中考满分英语范文
- 宿迁英语中考满分多少
- 陕西中考英语必背
- 退休失业金能领到吗
- 童摇和儿歌
- 听小说免费下载mp3
- 天气预报忠县天气预报
- 头晕自救
- 泰康养老社区保险产品
- 推广企业文化方法
- 托县天气预报天气
- 团建西班牙语
- 她的小梨涡完结了吗
- 天下第一师兄
- 天赐小说
- 唐朝长安是现在的哪里
- 塔克拉玛干沙漠形成原因
- 童话幻灭纯音乐
- 提高英语阅读的书
- 唐太宗和武则天的关系
- 太上武神诀境界划分
- 胎心仪监测
- 兔死狐悲是什么意思?
- 腿的英语怎么念
- 提醒用英语怎么说
- 苔伴奏音乐
- 天阶夜色凉如水什么季节
- 太平轮彼岸全集
- 通用作文800字
- 题画 清袁枚
- 听写英语软件
- 唐宋八大家韩愈
- 腿窝拔罐
- 我的世界怪物学院凋零骷髅小说
- 唯美的现代小说句子
- 武侠小说大旗英雄传
- 万界次元商店八零
- 网络代购小说
- 我和学神官宣了小说免费
- 吾爱文学网武侠小说
- 武侠小说中中情毒
- 我和傻儿子小说
- 王爷的神医弃妃小说
- 文本编辑软件下载
- 王爷的妃小说下载
- 网游之无敌奶爸精校下载
- 武神空间小说在线阅读
- 顽太的全部小说
- 完本玄幻修仙有女主小说
- 王爷虐情系列小说
- 乌龙茶的猜想下载
- 我的人鱼王子
- 我变成了树小说
- 渥丹脉脉写的小说
- 完结动漫排行榜玄幻小说
- 我在古代当迷弟穿书小说
- 文笔好的小说现代
- 完结末世游戏类小说
- 豌豆小说铺黑暗之旅
- 我又嫁入豪门小说下载
- 味觉猎人免费电子书
- 无限yy小说免费阅读
- 五界至尊完本全集
- 相声生活趣谈岳云鹏
- 相声游戏人
- 相声徐德亮小时候
- 薛刚反唐评书68
- 相声逗你玩mtv
- 相声儿歌新唱词
- 小学相声关于雷峰
- 仙君归来评书
- 相声谦哥真逗
- 相声演员练功的内容
- 相声有新人李丁
- 小学数学多人快板
- 相声电台节目文案
- 相声泰斗幼年趣事
- 相声谝闲传
- 相声演员陈寒柏刘骥
- 相声最火的歌
- 相声侃方言
- 相声欢乐喜剧人大潘
- 相声当代的发展
- 相声演员烧饼完整版
- 相声演员沈春和
- 相声杨达简历
- 相声太平年
- 修真小说排叶清音
- 小学生的简短相声
- 现代短相声
- 小学校园二人相声剧本
- 相声演员孙九香的年龄
- 西河大鼓唱腔