容斥原理与抽屉原理

容斥原理与抽屉原理 抽屉原理 常见形式 第一抽屉原理 原理1: 把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。 抽屉原理 证明(反证法):如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k?1)，故不可能。 原理2 :把多于mn(m乘以n)个的物体放到n个抽屉里，则至少有一个抽屉里有不少于m+1的物体。 证明(反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。 原理3 :把无穷多件物体放入n个抽屉，则至少有一个抽屉里 有无穷个物体。 原理1 、2 、3都是第一抽屉原理的 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 述。 第二抽屉原理 把(mn,1)个物体放入n个抽屉中，其中必有一个抽屉中至多有(m—1)个物体。 证明(反证法):若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。 基本介绍 应用抽屉原理解题 抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。 例1:同年出生的400人中至少有2个人的生日相同。 解:将一年中的365天视为365个抽屉，400个人看作400个物体，由抽屉原理1可以得知:至少有2人的生日相同. 400/365=1„35,1+1=2 又如:我们从街上随便找来13人，就可断定他们中至少有两个人属相相同。 “从任意5双手套中任取6只，其中至少有2只恰为一双手套。” “从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同。” 例2: 幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道理. 解 :从三种玩具中挑选两件，搭配方式只能是下面六种:(兔、兔)，(兔、熊猫)，(兔、长颈鹿)，(熊猫、熊猫)，(熊猫、长颈鹿)，(长颈鹿、长颈鹿)。把每种搭配方式看作一个抽屉，把7个小朋友看作物体，那么根据原理1，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式，选的玩具相同. 上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题，不错，这正是抽屉原则的主要作用.(需要说明的是，运用抽屉原则只是肯定了“存在”、“总有”、“至少有”，却不能确切地指出哪个抽屉里存在多少. 抽屉原理虽然简单，但应用却很广泛，它可以解答很多有趣的问题，其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。 制造抽屉是运用原则的一大关键 例1 从2、4、6、„、30这15个偶数中，任取9个数，证明其中一定有两个数之和是34。 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 与解答 我们用题目中的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个校友每人按照其握手的次数归入相应的“抽屉”，根据抽屉原理，至少有两个人属于同一抽屉，则这两个人握手的次数一样多。 在有些问题中，“抽屉”和“物体”不是很明显的，需要精心制造“抽屉”和“物体”.如何制造“抽屉”和“物体”可能是很困难的，一方面需要认真地分析题目中的条件和问题，另一方面需要多做一些题积累经验。 例5:15个网球分成数量不同的4堆，数量最多的一堆至少有多少个球, 分析与解答 此题实际是求出15可分拆多少种4个互不相同的整数之和，而15=1+2+3+9=1+2+4+8=1+2+5+7=1+3+4+7=1+3+5+6=2+3+4+6，所以最 [1]多一堆的球数可能是9、8、7、6，其中至少有6个。 整除问题 把所有整数按照除以某个自然数m的余数分为m类，叫做m的剩余类或同余类，用[0]，[1]，[2]，„，[m-1]表示.每一个类含有无穷多个数，例如[1]中含有1，m+1，2m+1，3m+1，„.在研究与整除有关的问题时，常用剩余类作为抽屉.根据抽屉原理，可以证明:任意n+1个自然数中，总有两个自然数的差是n的倍数。(证明:n+1个自然数被n整除余数至少有两个相等(抽屉原理)，不妨记为m=a1*n+b n=a2*n+b，则m-n整除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个抽屉中(即抽屉中分别为含有余数为0,1,2的数)，我们从这三个抽屉中各取1个(如1~5中取3,4,5)，其和(3+4+5=12)必能被3整除. ?若这5个余数分布在其中的两个抽屉中，则其中必有一个抽屉至少包含有3个余数(抽屉原理)，即一个抽屉包含1个余数，另一个包含4个，或者一个包含2个余数另一个抽屉包含3个。从余数多的那个抽屉里选出三个余数，其代数和或为0，或为3，或为6，均为3的倍数，故所对应的3个自然数之和是3的倍数. ?若这5个余数分布在其中的一个抽屉中，很显然，从此抽屉中任意取出三个余数，同情况?，余数之和可被3整除，故其对应的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为 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 制造10个抽屉，标以[0]，[1]，„，[9].若有两数落入同一抽屉，其差是10的倍数，只是仅有7个自然数，似不便运用抽屉原则，再作调整:[6]，[7]，[8]，[9]四个抽屉分别与[4]，[3]，[2]，[1]合并，则可保证至少有一个抽屉里有两个数，它们的和或差是10的倍数. 抽屉原理 - 表述 抽屉原理的一种更一般的表述为: “把多于kn+1个东西任意分放进n个空抽屉(k是正整数)，那么一定有一个抽屉中放进了至少k+1个东西。” 利用上述原理容易证明:“任意7个整数中，至少有3个数的两两之差是3的倍数。”因为任一整数除以3时余数只有0、1、2三种可能，所以7个整数中至少有3个数除以3所得余数相同，即它们两两之差是3的倍数。 如果问题所讨论的对象有无限多个，抽屉原理还有另一种表述: “把无限多个东西任意分放进n个空抽屉(n是自然数)，那么一定有一个抽屉中放进了无限多个东西。” 抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。 面积问题 例:九条直线中的每一条直线都将正方形分成面积比为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)?抽屉数]+1 染色问题 例1正方体各面上涂上红色或蓝色的油漆(每面只涂一种色)，证明正方体一定有三个面颜色相同. 证明:正方形有6个面 由最多[(m-1)?n]+1 得出[(6-1)?2]+1=[2.5]+1=3 例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中有两人也讨论乙问题，则结论也就成立了。否则，他们间只讨论丙问题，这样结论也成立。 狄利克雷原则 含义 把八个苹果任意地放进七个抽屉里，不论怎样放，至少有一个抽屉放有两个或两个以上的苹果。抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证明一些数论中的问题，因此，也称为狄利克雷原则。它是组合数学中一个重要的原理。 表现形式 把它推广到一般情形有以下几种表现形式。 形式一:设把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=nn)，那么一定有一个抽屉中放进了至少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个人以前彼此不相识。不论哪种情形发生，都符合问题的结论。 六人集会问题是组合数学中著名的拉姆塞定理的一个最简单的特例，这个简单问题的证明思想可用来得出另外一些深入的结论。这些结论构成了组合数学中的重要内容-----拉姆塞理论。从六人集会问题的证明中，我们又一次看到了抽屉原理的应用。 抽屉问题经典练习 系列之一 1(木箱里装有红色球3个、黄色球5个、蓝色球7个，若蒙眼去摸，为保证取出的球中有两个球的颜色不相同，则最少要取出多少个球, 解:把3种颜色看作3个抽屉，要符合题意，则小球的数目必须大于7，故至少取出8个小球才能符合要求。 2(一幅扑克牌有54张，最少要抽取几张牌，方能保证其中至少有2张牌有相同的点数, 解:点数为1(A)、2、3、4、5、6、7、8、9、10、11(J)、12(Q)、13(K)的牌各取1张，再取大王、小王各1张，一共15张，这15张牌中，没有两张的点数相同。这样，如果任意再取1张的话，它的点数必为1,13中的一个，于是有2张点数相同。 3(11名学生到老师家借书，老师是书房中有A、B、C、D四类书，每名学生最多可借两本不同类的书，最少借一本。试证明:必有两个学生所借的书的类型相同。 证明:若学生只借一本书，则不同的类型有A、B、C、D四种，若学生借两本不同类型的书，则不同的类型有AB、AC、AD、BC、BD、CD六种。共有10种类型，把这10种类型看作10个“抽屉”，把11个学生看作11个“苹果”。如果谁借哪种类型的书，就进入哪个抽屉，由抽屉原理，至少有两个学生，他们所借的书的类型相同。 4(有50名运动员进行某个项目的单循环赛，如果没有平局，也没有全胜，试证明:一定有两个运动员积分相同。 证明:设每胜一局得一分，由于没有平局，也没有全胜，则得分情况只有1、2、3„„49，只有49种可能，以这49种可能得分的情况为49个抽屉，现有50名运动员得分，则一定有两名运动员得分相同。 5(体育用品仓库里有许多足球、排球和篮球，某班50名同学来仓库拿球，规定每个人至少拿1个球，至多拿2个球，问至少有几名同学所拿的球种类是一致的, 解:根据规定，多有同学拿球的配组方式共有以下9种:,足,,排,,蓝,,足足,,排排,,蓝蓝,,足排,,足蓝,,排蓝,。以这9种配组方式制造9个抽屉，将这50个同学看作苹果50?9 =5„„5 由抽屉原理2:k=[m/n ]+1可得，至少有6人，他们所拿的球类是完全一致的。 6(某校有55个同学参加数学竞赛，已知将参赛人任意分成四组，则必有一组的女生多于2人，又知参赛者中任何10人中必有男生，则参赛男生的人数为__________人。 解:因为任意分成四组，必有一组的女生多于2人，所以女生至少有4×2+1=9(人);因为任意10人中必有男生，所以女生人数至多有9人。所以女生有9人，男生有55,9=46(人) 系列之二 7、 证明:从1，3，5，„„，99中任选26个数，其中必有两个数的和是100。 解析:将这50个奇数按照和为100，放进25个抽屉:(1，99)，(3，97)，(5，95)，„„，(49 ，51)。根据抽屉原理，从中选出26个数，则必定有两个数来自同一个抽屉，那么这两个数的和即为100。 8。 某旅游车上有47名乘客，每位乘客都只带有一种水果。如果乘客中有人带梨，并且其中任何两位乘客中至少有一个人带苹果，那么乘客中有______人带苹果。 解析:由题意，不带苹果的乘客不多于一名，但又确实有不带苹果的乘客，所以不带苹果的乘客恰有一名，所以带苹果的就有46人。 9。 一些苹果和梨混放在一个筐里，小明把这筐水果分成了若干堆，后来发现无论怎么分，总能从这若干堆里找到两堆，把这两堆水果合并在一起后，苹果和梨的个数是偶数，那么小明至少把这些水果分成了_______堆。 解析:要求把其中两堆合并在一起后，苹果和梨的个数一定是偶数，那么这两堆水果中，苹果和梨的奇偶性必须相同。对于每一堆苹果和梨，奇偶可能性有4种:(奇，奇)，(奇，偶)，(偶，奇)，(偶，偶)，所以根据抽屉原理可知最少分了4+1=5筐。 10。 有黑色、白色、蓝色手套各5只(不分左右手)，至少要拿出_____只(拿的时候不许看颜色)，才能使拿出的手套中一定有两双是同颜色的。 解析:考虑最坏情况，假设拿了3只黑色、1只白色和1只蓝色，则只有一双同颜色的，但是再多拿一只，不论什么颜色，则一定会有两双同颜色的，所以至少要拿6只。 11。从前25个自然数中任意取出7个数，证明:取出的数中一定有两个数，这两个数中大数不超过小数的1.5倍。 证明:把前25个自然数分成下面6组: 1; ? 2，3; ? 4，5，6; ? 7，8，9，10; ? 11，12，13，14，15，16; ? 17，18，19，20，21，22，23， ? 因为从前25个自然数中任意取出7个数，所以至少有两个数取自上面第?组到第?组中的某同一组，这两个数中大数就不超过小数的1.5倍。 12(一副扑克牌有四种花色，每种花色各有13张，现在从中任意抽牌。问最少抽几张牌，才能保证有4张牌是同一种花色的, 解析:根据抽屉原理，当每次取出4张牌时，则至少可以保障每种花色一样一张，按此类推，当取出12张牌时，则至少可以保障每种花色一样三张，但还要加上大小怪，所以当抽取第15张牌时，无论是什么花色，都可以至少保障有4张牌是同一种花色。 13(从1、2、3、4„„、12这12个自然数中，至少任选几个，就可以保证其中一定包括两个数，他们的差是7, 【解析】在这12个自然数中，差是7的自然树有以下5对:{12，5}{11，4}{10，3}{9，2}{8，1}。另外，还有2个在该范围取不到差值为7的配对的数是{6}、{7}。根据抽屉原理，共构造了7个抽屉。只要有两个数是取自同一个抽屉，那么它们的差就等于7。这7个抽屉可以表示为{12，5}{11，4}{10，3}{9，2}{8，1}{6}{7}，显然从7个抽屉中取8个数，则一定可以使有两个数字来源于同一个抽屉，也即作差为7。 系列之三 1(某幼儿班有40名小朋友，现有各种玩具122件，把这些玩具全部分给小朋友，是否会有小朋友得到4件或4件以上的玩具, 分析与解:将40名小朋友看成40个抽屉。今有玩具122件，122=3×40+2。应用抽屉原理2，取n=40，m=3，立即知道:至少有一个抽屉中放有4件或4件以上的玩具。也就是说，至少会有一个小朋友得到4件或4件以上的玩具。 2(一个布袋中有40块相同的木块，其中编上号码1，2，3，4的各有10块。问:一次至少要取出多少木块，才能保证其中至少有3块号码相同的木块, 分析与解:将1，2，3，4四种号码看成4个抽屉。要保证有一个抽屉中至少有3件物品，根据抽屉原理2，至少要有4×2+1=9(件)物品。所以一次至少要取出9块木块，才能保证其中有3块号码相同的木块。 3(六年级有100名学生，他们都订阅甲、乙、丙三种杂志中的一种、二种或三种。问:至少有多少名学生订阅的杂志种类相同, 分析与解:首先应当弄清订阅杂志的种类共有多少种不同的情况。 订一种杂志有:订甲、订乙、订丙3种情况; 订二种杂志有:订甲乙、订乙丙、订丙甲3种情况; 订三种杂志有:订甲乙丙1种情况。 总共有3+3+1=7(种)订阅方法。我们将这7种订法看成是7个“抽屉”，把100名学生看作100件物品。因为100=14×7+2。根据抽屉原理2，至少有14+1=15(人)所订阅的报刊种类是相同的。 4(篮子里有苹果、梨、桃和桔子，现有81个小朋友，如果每个小朋友都从中任意拿两个水果，那么至少有多少个小朋友拿的水果是相同的, 分析与解:首先应弄清不同的水果搭配有多少种。两个水果是相同的有4种，两个水果不同有6种:苹果和梨、苹果和桃、苹果和桔子、梨和桃、梨和桔子、桃和桔子。所以不同的水果搭配共有4+6=10(种)。将这10种搭配作为10个“抽屉”。 81?10=8„„1(个)。 根据抽屉原理2，至少有8+1=9(个)小朋友拿的水果相同。 5(学校开办了语文、数学、美术三个课外学习班，每个学生最多可以参加两个(可以不参加)。问:至少有多少名学生，才能保证有不少于5名同学参加学习班的情况完全相同, 分析与解:首先要弄清参加学习班有多少种不同情况。不参加学习班有1种情况，只参加一个学习班有3种情况，参加两个学习班有语文和数学、语文和美术、数学和美术3种情况。共有1+3+3=7(种)情况。将这7种情况作为7个“抽屉”，根据抽屉原理2，要保证不少于5名同学参加学习班的情况相同，要有学生 7×(5-1)+1=29(名)。 6. 在1，4，7，10，„，100中任选20个数，其中至少有不同的两对数，其和等于104。 分析:解这道题，可以考虑先将4与100，7与97，49与55„„，这些和等于104的两个数组成一组，构成16个抽屉，剩下1和52再构成2个抽屉，这样，即使20个数中取到了1和52，剩下的18个数还必须至少有两个数取自前面16个抽屉中的两个抽屉，从而有不同的两组数，其和等 于104;如果取不到1和52，或1和52不全取到，那么和等于104的数组将多于两组。 解:1，4，7，10，„„，100中共有34个数，将其分成{4，100}，{7，97}，„„，{49，55}，{1}，{52}共18个抽屉，从这18个抽屉中任取20个数，若取到1和52，则剩下的18个数取自前16个抽屉，至少有4个数取自某两个抽屉中，结论成立;若不全取1和52，则有多于18个数取自前16个抽屉，结论亦成立。 系列之四 1. 任意5个自然数中，必可找出3个数，使这三个数的和能被3整除。 分析:解这个问题，注意到一个数被3除的余数只有0，1，2三个，可以用余数来构造抽屉。 解:以一个数被3除的余数0、1、2构造抽屉，共有3个抽屉。任意五个数放入这三个抽屉中，若每个抽屉内均有数，则各抽屉取一个数，这三个数的和是3的倍数，结论成立;若至少有一个抽屉内没有数，那么5个数中必有三个数在同一抽屉内，这三个数的和是3的倍数，结论亦成立。 2. 在边长为1的正方形内，任意放入9个点，证明在以这些点为顶点的三角形中，必有一个三角形的面积不超过1/8. 解:分别连结正方形两组对边的中点，将正方形分为四个全等的小正方形，则各个小正方形的面积均为1/4 。把这四个小正方形看作4个抽屉，将9个点随意放入4个抽屉中，据抽屉原理，至少有一个小正方形中有3个点。显然，以这三个点为顶点的三角形的面积不超过1/8 。 反思:将边长为1的正方形分成4个面积均为1/4 的小正方形，从而构造出4个抽屉，是解决本题的关键。我们知道。将正方形分成面积均为1/4 的图形的方法不只一种，如可连结两条对角线将正方形分成4个全等的直角三角形，这4个图形的面积也都是1/4 ，但这样构造抽屉不能证到结论。可见，如何构造抽屉是利用抽屉原理解决问题的关键。 3( 班上有50名学生，将书分给大家，至少要拿多少本，才能保证至少有一个学生能得到两本或两本以上的书。 解:把50名学生看作50个抽屉，把书看成苹果 ，根据原理1，书的数目要比学生的人数多，即书至少需要50+1=51本. 4( 在一条长100米的小路一旁植树101棵，不管怎样种，总有两棵树的距离不超过1米。 解:把这条小路分成每段1米长，共100段，每段看作是一个抽屉，共100个抽屉，把101棵树看作是101个苹果 ，于是101个苹果放入100个抽屉中，至少有一个抽屉中有两个苹果 ，即至少有一段有两棵或两棵以上的树 . 容斥原理 容斥原理1 如果被计数的事物有A、B两类，那么，A类B类元素个数总和= 属于A类元素个数+ 属于B类元素个数—既是A类又是B类的元素个数。(A?B = A+B - A?B) 例1 一次期末考试，某班有15人数学得满分，有12人语文得满分，并且有4人语、数都是满分，那么这个班至少有一门得满分的同学有多少人, 分析 依题意，被计数的事物有语、数得满分两类，“数学得满分”称为“A类元素”，“语文得满分”称为“B类元素”，“语、数都是满分”称为“既是A类又是B类的元素”，“至少有一门得满分的同学”称为“A类和B类元素个数”的总和。 答案 15+12-4=23 试一试 电视台向100人调查前一天收看电视的情况，有62人看过2频道，34人看过8频道，其中11人两个频道都看过。两个频道都没看过的有多少人, 100-(62+34-11)=15 容斥原理2 如果被计数的事物有A、B、C三类，那么，A类和B类和C类元素个数总和= A类元素个数+ B类元素个数+C类元素个数—既是A类又是B类的元素个数—既是A类又是C类的元素个数—既是B类又是C类的元素个数+既是A类又是B类而且是C类的元素个数。(A?B?C = A+B+C - A?B - B?C - C?A + A?B?C) 例1 某校六?班有学生45人，每人在暑假里都参加体育训练队，其中参加足球队的有25人，参加排球队的有22人，参加游泳队的有24人，足球、 排球都参加的有12人，足球、游泳都参加的有9人，排球、游泳都参加的有8人，问:三项都参加的有多少人, 分析:参加足球队的人数25人为A类元素，参加排球队人数22人为B类元素，参加游泳队的人数24人为C类元素，既是A类又是B类的为足球排球都参加的12人，既是B类又C类的为足球游泳都参加的9人，既是C类又是A类的为排球游泳都参加的8人，三项都参加的是A类B类C类的总和设为X。注意:这个题说的每人都参加了体育训练队，所以这个班的总人数即为A类B类和C类的总和。 答案:25+22+24-12-9-8+X=45 解得X=3 例2 在1到1000的自然数中，能被3或5整除的数共有多少个,不能被3或5整除的数共有多少个, 分析:显然，这是一个重复计数问题(当然，如果不怕麻烦你可以分别去数3的倍数，5的倍数)。我们可以把“能被3或5整除的数”分别看成A类元素和B类元素，能“同时被3或5整除的数(15的倍数)”就是被重复计算的数，即“既是A类又是B类的元素”。求的是“A类或B类元素个数”。现在我们还不能直接计算，必须先求出所需条件。 1000?3=333„„1，能被3整除的数有333个(想一想，这是为什么,)同理，可以求出其他的条件。 例3 分母是1001的最简分数一共有多少个, 分析:这一题实际上就是找分子中不能与1001进行约分的数。由于1001=7×11×13，所以就是找不能被7，11，13整除的数。 解答:1~1001中，有7的倍数1001/7 = 143 (个);有11的倍数1001/11 = 91 (个)，有13的倍数1001/13 = 77 (个);有7´11=77的倍数1001/77 = 13 (个)，有7´13=91的倍数1001/91 = 11 (个)，有11´13=143的倍数1001/43 = 7 (个).有1001的倍数1个。 由容斥原理知:在1~1001中，能被7或11或13整除的数有(143+91+7)-(13+11+7)+1=281(个)，从而不能被7、11或13整除的数有1001-281=720(个).也就是说，分母为1001的最简分数有720个。 例4 某个班的全体学生在进行了短跑、游泳、投掷三个项目的测试后，有4名学生在这三个项目上都没有达到优秀，其余每人至少有一项达到了优秀，达到了优秀的这部分学生情况如下表: 短跑 游泳 投掷 短跑、游泳 短跑、投掷 游泳、投掷 短跑、游泳、投掷 1 7 1 8 1 5 6 6 5 2 求这个班的学生共有多少人, 分析:这个班的学生数，应包括达到优秀和没有达到优秀的。 试一试:一个班有42人，参加合唱队的有30人，参加美术组的有25人，有5人什么都没有参加，求两种都参加的有多少人, 例5 在一根长的木棍上有三种刻度线，第一种刻度线将木棍分成10等份，第二种将木棍分成12等份，第三种将木棍分成15等份。如果沿每条刻度线将木棍锯断，木棍总共被锯成多少段, 分析: 很显然，要计算木棍被锯成多少段，只需要计算出木棍上共有多少条不同的刻度线，在此基础上加1就是段数了。 若按将木棍分成10等份的刻度线锯开，木棍有9条刻度线。在此木棍上加上将木棍分成12等份的11条刻度线，显然刻度线有重复的，如5/10和6/12都是1/2。同样再加上将木棍分成15等份的刻度线，也是如此。所以，我们应该按容斥原理的方法来解决此问题。用容斥原理的那一个呢,想一想，被计数的事物有那几类,每一类的元素个数是多少, 解答 解一:(10，12，15)=60，设木棍60厘米 60?10=6厘米，60?12=5厘米，60?15=4厘米 10等分的为第一种刻度线，共10,1=9条 12等分的为第二种刻度线，共12,1=11条 15等分的为第三种刻度线，过15,1=14条 第一种与第二种刻度线重合的(6，5)=30，60?30,1=2,1=1条 第一种与第三种刻度线重合的(6，4)=12，60?12,1=5,1=4条 第二种与第三种刻度线重合的(5，4)=20，60?20,1=3,1=2条 三种刻度线重合的没有，(6、5、4)=60 因此，共有刻度线9+11+14,1,4,2=27条，木棍总共被锯成27+1=28段。 解二:总长看成单位1分别分成10、12、15段。1/10与1/12的最小公倍数1/2，1/10与1/15的最小公倍数1/5，1/12与1/15的最小公倍数1/3，1/10，1/12和1/15的最小公倍数为1，有10+12+15-(2+5+3)+1=28 解三: 10、12、15的最小公倍数是60，假设木棍就是长60， 1、那么，分成10等份的每份6，刻度就是 0，6，12，18，24，30，36，42，48，54，60 2、分成12等分的每份就是5， 0，5，10，15，20，25，30，35，40，45，50，55，60 3、分成15等分的每份就是4， 0，4，8，12，16，20，24，28，32，36，40，44，48，52，56，60 4、把相同刻度的合并，就是有刻度如下: 0，4，5，6，8，10，12，15，16，18，20，24，25，28，30，32，35，36，40，42，44，45，48，50，52，54，55，56，60