容斥原理与抽屉原理

《容斥原理与抽屉原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、抽屉原理常见形式第一抽屉原理原理1：把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。抽屉原理证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k≥1)，故不可能。　　原理2：把多于mn(m乘以n)个的物体放到n个抽屉里，则至少有一个抽屉里有不少于m+1的物体。　　证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。　　原理3：把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体。　　原理1、2、3都是第一抽屉原

2、理的表述。第二抽屉原理　　把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体。　　证明（反证法）：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。基本介绍　　应用抽屉原理解题　　抽屉原理的内容简明朴素，易于接受，它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。　　例1：同年出生的400人中至少有2个人的生日相同。　　解：将一年中的365天视为365个抽屉，400个人看作400个物体，由抽屉原理1可以得知：至少有2人的生日相同.400/365=1…35,1+1=

3、2　又如：我们从街上随便找来13人，就可断定他们中至少有两个人属相相同。　　“从任意5双手套中任取6只，其中至少有2只恰为一双手套。”　　“从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同。”　　例2：幼儿园买来了不少白兔、熊猫、长颈鹿塑料玩具，每个小朋友任意选择两件，那么不管怎样挑选，在任意七个小朋友中总有两个彼此选的玩具都相同，试说明道理.　　解：从三种玩具中挑选两件，搭配方式只能是下面六种：（兔、兔），（兔、熊猫），（兔、长颈鹿），（熊猫、熊猫），（熊猫、长颈鹿），（长颈鹿、长颈鹿）。把每种搭配方式看作一

4、个抽屉，把7个小朋友看作物体，那么根据原理1，至少有两个物体要放进同一个抽屉里，也就是说，至少两人挑选玩具采用同一搭配方式，选的玩具相同.　　上面数例论证的似乎都是“存在”、“总有”、“至少有”的问题，不错，这正是抽屉原则的主要作用.（需要说明的是，运用抽屉原则只是肯定了“存在”、“总有”、“至少有”，却不能确切地指出哪个抽屉里存在多少.　　抽屉原理虽然简单，但应用却很广泛，它可以解答很多有趣的问题，其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。　　制造抽屉是运用原则的一大关键　　例1从2、4、6、…、30这15个

5、偶数中，任取9个数，证明其中一定有两个数之和是34。　　分析与解答我们用题目中的15个偶数制造8个抽屉：　　此抽屉特点：凡是抽屉中有两个数的，都具有一个共同的特点：这两个数的和是34。现从题目中的15个偶数中任取9个数，由抽屉原理（因为抽屉只有8个），必有两个数可以在同一个抽屉中（符合上述特点）.由制造的抽屉的特点，这两个数的和是34。　　例2：从1、2、3、4、…、19、20这20个自然数中，至少任选几个数，就可以保证其中一定包括两个数，它们的差是12。　　分析与解答在这20个自然数中，差是12的有以下8对：{20，8}，{1

6、9，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个数，必有两个数，其中一个数是另一个数的倍数。　　分析与解答根据题目所要求证的问题，

7、应考虑按照同一抽屉中，任意两数都具有倍数关系的原则制造抽屉.把这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位校友，彼此认识的握手问候.请你证明无论什么

8、情况，在这n个校友中至少有两人握手的次数一样多。　　分析与解答共有n位校友，每个人握手的次数最少是0次，即这个人与其他校友都没有握过手；最多有n-1次，即这个人与每位到会校友都握了手.然而，如果有一个校友握手的次数是0次，那么握手次数最多的不能多于n-2次；如果