22简单抽屉原理与最不利原则(二)强化--田芳宇

第一抽屉原理原理1 把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。

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

原理2 把多于mn个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。

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

第二抽屉原理把(mn－1)个物体放入n个抽屉中，其中必有一个抽屉中至多有(m—1)个物体。

[证明](反证法)：若每个抽屉都有不少于m个物体，则总共至少有mn个物体，与题设矛盾，故不可能。

抽屉原理，又叫狄利克雷原则，它是一个重要而又基本的数学原理，应用它可以解决各种有趣的问题，并且常常能够得到令人惊奇的结果，许多看起来相当复杂，甚至无从下手的问题，利用它能很容易得到解决．那么，什么是抽屉原理呢？我们先从一个最简单的例子谈起．将三个苹果放到两只抽屉里，想一想，可能会有什么样的结果呢？要么在一只抽屉里放两个苹果，而另一只抽屉里放一个苹果；要么一只抽屉里放有三个苹果，而另一只抽屉里不放．这两种情况可用一句话概括：一定有一只抽屉里放入了两个或两个以上的苹果．虽然哪只抽屉里放入至少两个苹果我们无法断定，但这是无关紧要的，重要的是有这样一只抽屉放入了两个或两个以上的苹果．如果我们将上面问题做一下变动，例如不是将三个苹果放入两只抽屉里，而是将八个苹果放到七只抽屉里，我们不难发现，这八个苹果无论以怎样的方式放入抽屉，仍然一定会有一只抽屉里至少有两个苹果。

通过上面的分析，我们可以将上面问题中包含的基本原理写成下面的一般形式．抽屉原理（一）：把多于几个的元素按任一确定的方式分成几个集合，那么一定至少有一个集合中，至少含有两个元素．应用抽屉原理来解题，首先要审题，即分清什么作为“元素”，什么作为“抽屉”；其次要根据题目的条件和结论，结合有关的数学知识，来设计抽屉，在应用抽屉原理解题时，正确地设计抽屉是解题的关键．例1 有红、黄、绿三种颜色的小球各四颗混放在一只盒子里，为了保证一次能取到两颗颜色相同的小球，一次至少要取几颗？A、3B、4C、5D、6分析：将三种不同的颜色看作三个抽屉，为了保证一次能取到两颗颜色相同的小球，即要求至少有两颗小球出自同一抽屉，因此一次至少要取4颗小球．例2 某班有30名学生，班里建立一个小书库，同学们可以任意借阅，问小书库中至少要有多少本书，才能保证至少有一个同学一次能至少借到两本书？A、28B、29C、30D、31分析：将30名同学看作30个“抽屉”，而将书看作“苹果”，根据抽屉原理，“苹果”数目要比“抽屉”数目大，才能保证至少有一个抽屉里有两个或两个以上的“苹果”，因此，小书库中至少要有31本书，才能保证至少有一位同学一次能借到两本或两本以上的图书。

抽屉原理及其简单应用第一篇：抽屉原理及其简单应用抽屉原理及其应用摘要: 本文着重从抽屉的构造方法阐述抽屉原理,介绍了抽屉原理及其常见形式，并结合实例探讨了这一原理在高等数学和初等数论中的应用。

关键词: 组合数学；抽屉原理；抽屉构造1．引言抽屉原理也叫鸽笼原理, 它是德国数学家狄利克雷(P.G.T.Dirichlet)首先提出来的, 因此也称作狄利克雷原理.它是数学中一个基本的原理，在数论和组合论中有着广泛的应用。

在数学的学习研究中，我们也可以把它看作是一种重要的非常规解题方法，应用它能解决许多涉及存在性的数学问题。

2．抽屉原理的基本形式与构造2.1基本形式陈景林、阎满富编著的中国铁道出版社出版的《组合数学与图论》一书中对抽屉原理给出了比较具体的定义，概括起来主要有下面几种形式: 原理Ⅰ 把多于n个的元素按任一确定的方式分成n个集合，则一定有一个集合中含有两个或两个以上的元素。

原理Ⅱ 把m个元素任意放到n(m>n)个集合里，则至少有一个集合里至少有k个元素，其中⎧m , 当n能整除m时,⎪⎪nk=⎨⎡m⎤⎪+1 , 当n不能整除m 时.⎢⎥⎪⎩⎣n⎦原理Ⅲ 把无穷个元素按任一确定的方式分成有穷个集合，则至少有一个集合中仍含无穷个元素。

2.2基本构造利用抽屉原理解题过程中首先要注意指明什么是元素，什么是抽屉，元素进入抽屉的规则是什么，以及在同一个盒子中，所有元素具有的性质。

构造抽屉是用抽屉原理解题的关键。

有的题目运用一次抽屉原理就能解决，有的则需反复用多次；有些问题明显能用抽屉原理解决，但对于较复杂的问题则需经过一番剖析转化才能用抽屉原理解决。

3.利用抽屉原理解题的常用方法3.1利用划分数组构造抽屉例1 在前12个自然数中任取七个数，那么, 一定存在两个数, 其中的一个数是另一个数的整数倍。

分析：若能把前12个自然数划分成六个集合, 即构成六个抽屉，使每个抽屉内的数或只有一个, 或任意的两个数, 其中的一个是另一个的整数倍，这样, 就可以由抽屉原理来推出结论。

抽屉原理的学习方法大家知道，两个抽屉要放置三只苹果，那么一定有两只苹果放在同一个抽屉里，更一般地说，只要被放置的苹果数比抽屉数目大，就一定会有两只或更多只的苹果放进同一个抽屉，可不要小看这一简单事实，它包含着一个重要而又十分基本的原则――抽屉原则.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个物体.证明同原则1相仿.若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符，故不可能。

原则1可看作原则2的物例（m=1）例2 正方体各面上涂上红色或蓝色的油漆（每面只涂一种色），证明正方体一定有三个面颜色相同. 证明把两种颜色当作两个抽屉，把正方体六个面当作物体，那么6=2×2+2，根据原则二，至少有三个面涂上相同的颜色。

四年级秋季班第五讲-简单抽屉原理、最不利原则第五讲简单抽屉原理、最不利原则知识框架一、对抽屉原理两个版本的认识原理要点：（1）物品数比抽屉数多1。

只有物品数比抽屉数多时抽屉原理才会成立。

（2）物品是“任意放”到抽屉中。

（3）其中“物品不少于2件”的抽屉是一定存在的，但是不确定是哪一个。

（4）原理的结论是：“至少有一个抽屉中的物品数不少于2件”，也可以这么说，“至少有2件物品在同一个抽屉中”。

原理讲解：抽屉原理1：将n+1个物品任意放到n个抽屉中，那么至少有一个抽屉中的物品不少于2件。

只要有一个抽屉中的物品数不少于2件，抽屉原理1 就是成立的。

当我们可以往抽屉中任意放物品时，最不利的情形就是“平均分”，这样所有抽屉中的物品数都不会太多。

n+1个物品平均地放入n个抽屉，每个抽屉放一个，由于物品数比抽屉数多，就会余出一个物品。

最后，余出的这个物品放入某个抽屉，这个抽屉中就有了2个物品。

此外，其它情形，只要有一个抽屉是空的，那么就一定会有另外的抽屉中有2个或2个以上的物品。

例子：4只鸽子飞回三个鸟笼，有几种方法？每种方法中，都会有一个鸟笼中的鸽子数不少于2。

在有些地方抽屉原理又叫做“鸽笼原理”。

原理要点：（1）物品数比抽屉数多，抽屉原理1的情形包含于这个原理中；（2）解决的是抽屉的存在性；（3）在解题时，遇到“有一个抽屉中的物品数不少于A件”，其中A>2时，应使用抽屉原理2。

（4）原理的结论也可以理解为：“总有不少于m÷n件（或[m÷n]+1件）物品在同一个抽屉中。

”相同的即为“抽屉”。

原理讲解：最不利的情形就是“平均分”，这样每个抽屉中的物品数都不太多都是[m÷n]个。

若m÷n有余数，那么多出来的余数个物品也按照最不利的情形来分配，这样就能保证抽屉中的物品尽量地少。

也就是说这余数个物品也平均地往抽屉中放，这样有的抽屉会再放入一个物品，而有的就分不到，那么至少会有一个抽屉中的物品数不少于[m÷n]+1个。

小学奥数教案——抽屉原理（解析版）第一篇：小学奥数教案——抽屉原理(解析版)教案抽屉原理一本讲学习目标初步抽屉原理的方法和心得。

二概念解析把3个苹果任意放到两个抽屉里，可以有哪些放置的方法呢？一个抽屉放一个，另一个抽屉放两个；或3个苹果放在某一个抽屉里.尽管放苹果的方式有所不同，但是总有一个共同的规律：至少有一个抽屉里有两个或两个以上的苹果.如果把5个苹果任意放到4个抽屉里，放置的方法更多了，但仍有这样的结果.由此我们可以想到，只要苹果的个数多于抽屉的个数，就一定能保证至少有一个抽屉里有两个或两个以上的苹果.道理很简单：如果每个抽屉里的苹果都不到两个（也就是至多有1个），那么所有抽屉里的苹果数的和就比总数少了.由此得到：抽屉原理：把多于n个的苹果放进n个抽屉里，那么至少有一个抽屉里有两个或两个以上的苹果。

如果把苹果换成了鸽子，把抽屉换成了笼子，同样有类似的结论，所以有时也把抽屉原理叫做鸽笼原理.不要小看这个“原理”，利用它可以解决一些表面看来似乎很难的数学问题。

比如，我们从街上随便找来13人，就可以断定他们中至少有两个人属相（指鼠、牛、虎、兔、…等十二种生肖）相同.怎样证明这个结论是正确的呢？只要利用抽屉原理就很容易把道理讲清楚.事实上，由于人数（13）比属相数（12）多，因此至少有两个人属相相同（在这里，把13人看成13个“苹果”，把12种属相看成12个“抽屉”）。

应用抽屉原理要注意识别“抽屉”和“苹果”，苹果的数目一定要大于抽屉的个数。

三例题讲解例1 有5个小朋友，每人都从装有许多黑白围棋子的布袋中任意摸出3枚棋子.请你证明，这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。

分析与解答首先要确定3枚棋子的颜色可以有多少种不同的情况，可以有：3黑，2黑1白，1黑2白，3白共4种配组情况，看作4个抽屉.把每人的3枚棋作为一组当作一个苹果，因此共有5个苹果.把每人所拿3枚棋子按其颜色配组情况放入相应的抽屉.由于有5个苹果，比抽屉个数多，所以根据抽屉原理，至少有两个苹果在同一个抽屉里，也就是他们所拿棋子的颜色配组是一样的。

抽屉原理和最不利原则一、抽屉原理抽屉原理（也被称为鸽笼原理）是数学中一种基本原理，它是由鸽笼和抽屉的类比而得名。

根据抽屉原理，如果n+1个物体被放置到n个容器之中，那么至少有一个容器内含有两个或者更多的物体。

换句话说，抽屉原理表明，当物体数量超过容器数量时，至少有一个容器将会装有多个物体。

这个原理可以应用于各种场景，例如，如果有11个学生坐在一排座位上，而只有10个座位，那么至少有一个学生将会没有座位坐。

抽屉原理在数学和计算机科学中有广泛的应用。

例如，在计算机科学中，抽屉原理可以用来证明哈希函数的碰撞概率、证明图的着色问题等等。

最不利原则是指在做决策时，应该假设每一项决策都是以对自己最不利的方式进行的。

也就是说，在进行决策时，应该考虑最不利的情况，并希望能够在最不利的情况下找到最好的解决方案。

最不利原则在决策分析和优化问题中具有重要作用。

通过考虑最不利的情况，可以防止决策者产生过于乐观或者主观的判断，从而更好地制定决策方案。

最不利原则可以应用于各种领域，例如商业决策、政治决策和战略决策等。

在商业决策中，经营者应该考虑到市场环境变化和竞争对手的行动，以保持企业的竞争力。

在政治决策中，政府领导者应该考虑到各种社会和经济因素，以制定合理的政策。

在战略决策中，军事指挥官应该考虑到敌方的最强势和最危险的行动，以便做出战略部署。

最不利原则帮助我们克服幻觉和假设，从而更加客观地进行决策。

通过考虑最不利的情况，我们能够更好地准备好应对各种风险和挑战，并找到最佳的解决方案。

总结：抽屉原理和最不利原则都是数学领域中的重要原则，它们在不同的背景下有着不同的应用。

抽屉原理通过简单的类比，帮助我们理解当物体数量超过容器数量时，必然会有一些容器装有多个物体的情况。

最不利原则则在决策分析和优化问题中起着重要的作用，通过考虑最不利的情况，可以制定出最佳的决策方案。

这两个原则都帮助我们在面对不同的问题和情境时，能够更加准确地进行分析和决策。

第1讲抽屉原理和最不利原理生活中常见这样的例子:把5只苹果放入4个果盘，那么一定有某个果盘中至少放有2只苹果，13名同学中至少有2人出生于同一个月……像这样，如果把n+k(k≥1)件物品放入n个抽屉，那么至少有一个抽屉中有2件或2件以上的物品，这就是抽屉原理1;进一步，如果把m×n+k(k≥1)件物品放入n个抽屉，那么至少有一个抽屉中有m+1件物品，这就是抽屉原理2。

实际上，这里的抽屉就是指这些物品可以分成几类，运用抽屉原理解决问题的关键就在于正确分类。

最不利原则主要说明的是一种从极端情况(最坏情况)入手，分析问题的一种思考方法。

例1今年燕山小学招收的一年级新生有230名，年龄在6岁至7岁之间，能否保证有20名或20名以上的小朋友在同一个月出生?为什么?试一试1在一条长100米的小路一旁植树101棵，证明:不管怎样种，总有两棵树的距离不超过1米。

例2有19个同学参加了三个课外活动小组，它们分别是数学组、美术组、电脑组，每人可参加一个组、两个组或三个组活动。

问:这些同学中至少有几个同学参加了相同的组?有22个同学参加了三个课外活动课程，它们分别是足球课、网球课、排球课，每人可参加一个课程、两个课程或三个课程活动。

问:这些同学中至少有几个同学参加了相同的课程?例3把125本书分给五(2)班学生，如果其中至少有1人分到至少4本书，那么，这个班最多有多少人?试一试3把98本书分给五(3)班学生，如果其中至少有1人分到至少3本书，那么，这个班最多有多少人?例4一副扑克牌，共54张，问至少从中摸出多少张牌才能保证:(1)至少有5张牌的花色相同;(2)四种花色的牌都有;(3)至少有3张牌是红桃。

一幅扑克牌有54张，最少要抽取几张牌，方能保证其中至少有2张牌有相同的点数?课内练习1.某班有学生54人，他们的年龄都相同，那么，至少有多少人在同一周出生?至少有多少人在同一月出生?2.木箱里装有红色球3个、黄色球5个、蓝色球7个，若蒙眼去摸，为保证取出的球中有两个球的颜色相同，则最少要取出多少个球?3.11名学生到老师家借书，老师家书房中有A,B,C,D四类书，每名学生最多可借两本不同类的书，最少借一本。

抽屉原理一．什么是抽屉原理抽屉原理有时也被称为鸽笼原理，它由德国数学家狄利克雷首先明确提出来并用来证明一些数论中的问题，因此，也被称为狄利克雷原则．抽屉原理是组合数学中一个重要而又基本的数学原理，利用它可以解决很多有趣的问题，并且常常能够起到令人惊奇的作用．许多看起来相当复杂，甚至无从下手的问题，在利用抽屉原则后，能很快使问题得到解决．抽屉原理可以分为两种情况：简单的抽屉原理；复杂的抽屉原理。

先看一个问题：现在有11个苹果，10个抽屉。

要将苹果全部放到抽屉中并且每个抽屉不能为空，应怎样放？如果允许有空抽屉呢？如果有12个苹果呢？通过上面的问题我们可以知道，当苹果比抽屉多的时候，一定能保证至少有一个抽屉里有2个或2个以上的苹果。

因此简单的抽屉原理可概述为：将多于N个的物品任意放到N个抽屉里，那么至少有一个抽屉里的物品不少于2个。

再来看这样的问题：如果11个苹果放到5个抽屉当中，可以怎么放？通过列举可以看出，不管怎样放置，至少有一个抽屉里有3个或3个以上的苹果。

因为有下列算式存在：11521÷=⋅⋅⋅因此我们可以将复杂的抽屉原理概述为：将多于mn个的物品任意放到n个抽屉里，那么至少有一个抽屉里的物品不少于m+1个。

在解决抽屉原理问题时，要注意识别“抽屉”和“苹果”。

二．下面我们看一些具体的问题。

例1.有5个小朋友，没人都从装有许多黑白围棋的布袋中任意摸出3枚棋子。

请你证明，这5个人中至少有两个小朋友摸出的棋子的颜色的配组是一样的。

例2.中午食堂有5中不同的菜和4种不同的主食，每人只能买一种菜或一种主食，请你证明某班在食堂买饭的21名学生中，一定至少有两名学生所买的菜和主食是一样的。

例3.11名学生到老师家借书，老师是书房中有Ａ、Ｂ、Ｃ、Ｄ四类书，每名学生最多可借两本不同类的书，最少借一本。

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

例4.体育用品仓库里有许多足球、排球和篮球，某班50名同学来仓库拿球，规定每个人至少拿１个球，至多拿２个球，问至少有几名同学所拿的球种类是一致的？例5.某班有37名小学生,他们都订阅了《小朋友》、《儿童时代》、《少年报》中的一种或几种,那么其中至少有几名学生订的报刊种类完全相同.例6.篮子里有苹果、梨、桃和桔子，现有81个小朋友，如果每个小朋友都从中任意拿两个水果，那么至少有多少个小朋友拿的水果是相同的？例7.从1、2、3、4……、12这12个自然数中，至少任选几个，就可以保证其中一定包括两个数，他们的差是7？例8.在1，4，7，10，…，100中任选20个数，其中至少有不同的两对数，其和等于104。

抽屉原理讲义什么是抽屉原理？在数学领域中，抽屉原理是一种简单而常用的证明方法。

其核心思想是，如果将 n+1 个物品放到 n 个桶中，那么至少有一个桶中必定包含两个及以上的物品。

这个原理在组合数学、计算机科学等诸多领域都有广泛应用。

具体而言，抽屉原理包括两个基本概念：抽屉和物品。

如果将 n 个物品放到 m 个抽屉中，如果 n > m，那么至少有一个抽屉中会有两个或两个以上的物品。

抽屉原理的证明对于抽屉原理的证明，有一种简单而直观的方法。

我们可以将 n+1 个物品任意分成 m 组，其中 m = n。

假设每一组最多只有一个物品，那么总共只能分成 n 组。

由于有 n+1 个物品，所以至少有一组中包含了两个物品。

因此，根据这个假设的前提，我们可以得到一个矛盾，即最多只能将 n+1 个物品分成 n 组，每组最多只有一个物品，但又至少有两个物品在同一组中。

因此，假设不成立，抽屉原理成立。

抽屉原理应用抽屉原理有很多应用，下面我们介绍其中的两个例子。

例子1：生日悖论假设我们有一个房间里有 23 个人，那么至少有两个人生日相同的概率有多大呢？根据抽屉原理，我们将每个人的生日看做一个物品，日期看做一个抽屉，因为一年中只有 365 天，所以只有 365 个抽屉，但有 23 个生日需要放到这些抽屉中。

根据计算可知，概率公式为 P = 1 –(365 * 364 * 363 …… (365-22)) / (365 ^ 23) ≈ 0.5因此，当有 23 个人在同一个房间中时，至少有两个人生日相同的概率几乎是50%。

例子2：计算机算法在计算机算法中，抽屉原理有广泛应用。

其中一个例子是哈希表。

哈希表是一种高效的数据结构，它基于抽屉原理，使用哈希函数将每个数据项映射到不同的桶中。

在哈希表中，桶的数量通常比数据项的数量多，因此会有多个数据项映射到同一个桶中。

例如，如果我们在一个大小为 10 的哈希表中存储 11 个数据项，其中有两个数据项会映射到同一个桶中。