中铁建设集团门户网站登陆,微信关注公众号,iis 网站无法访问,ppt免费制作网站“抽屉原理”最先是由19世纪的德国数学家迪里赫莱#xff08;Dirichlet#xff09;运用于解决数学问题的#xff0c;所以又称“迪里赫莱原理”#xff0c;也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果#xff0c;任意分放在9个抽屉里#xff0c;则至少有…“抽屉原理”最先是由19世纪的德国数学家迪里赫莱Dirichlet运用于解决数学问题的所以又称“迪里赫莱原理”也有称“鸽巢原理”的。这个原理可以简单地叙述为“把10个苹果任意分放在9个抽屉里则至少有一个抽屉里含有两个或两个以上的苹果”。这个道理是非常明显的但应用它却可以解决许多有趣的问题并且常常得到一些令人惊异的结果。抽屉原理是国际国内各级各类信息学竞赛中的重要内容本讲就来学习它的有关知识及其应用。 一、知识点 定理1、如果把n1个元素分成n个集合那么不管怎么分都存在一个集合其中至少有两个元素。 证明用反证法若不存在至少有两个元素的集合则每个集合至多1个元素从而n个集合至多有n个元素此与共有n1个元素矛盾故命题成立。 在定理1的叙述中可以把“元素”改为“物件”把“集合”改成“抽屉”抽屉原理正是由此得名。 同样可以把“元素”改成“鸽子”把“分成n个集合”改成“飞进n个鸽笼中”。“鸽笼原理”由此得名。 二、讲解范例 【例1】一个小组共有13名同学其中至少有2名同学同一个月过生日。为什么 【分析】每年里共有12个月任何一个人的生日一定在其中的某一个月。如果把这12个月看成12个“抽屉”把13名同学的生日看成13只“苹果”把13只苹果放进12个抽屉里一定有一个抽屉里至少放2个苹果也就是说至少有2名同学在同一个月过生日。 【例 2】任意4个自然数其中至少有两个数的差是3的倍数。这是为什么 【分析与解】首先我们要弄清这样一条规律如果两个自然数除以3的余数相同那么这两个自然数的差是3的倍数。而任何一个自然数被3除的余数或者是0或者是1或者是2根据这三种情况可以把自然数分成3类这3种类型就是我们要制造的3个“抽屉”。我们把4个数看作“苹果”根据抽屉原理必定有一个抽屉里至少有2个数。换句话说4个自然数分成3类至少有两个是同一类。既然是同一类那么这两个数被3除的余数就一定相同。所以任意4个自然数至少有2个自然数的差是3的倍数。 【例3】有规格尺寸相同的5种颜色的袜子各15只混装在箱内试问不论如何取从箱中至少取出多少只就能保证有3双袜子袜子无左、右之分 【分析与解】试想一下从箱中取出6只、9只袜子能配成3双袜子吗回答是否定的。按5种颜色制作5个抽屉根据抽屉原理1只要取出6只袜子就总有一只抽屉里装2只这2只就可配成一双。拿走这一双尚剩4只如果再补进2只又成6只再根据抽屉原理1又可配成一双拿走。如果再补进2只又可取得第3双。所以至少要取62210只袜子就一定会配成3双。 【例4】一个布袋中有35个同样大小的木球其中白、黄、红三种颜色球各有10个另外还有3个蓝色球、2个绿色球试问一次至少取出多少个球才能保证取出的球中至少有4个是同一颜色的球 【分析与解】从最“不利”的取出情况入手。 最不利的情况是首先取出的5个球中有3个是蓝色球、2个绿色球。 接下来把白、黄、红三色看作三个抽屉由于这三种颜色球相等均超过4个所以根据抽屉原理2只要取出的球数多于4-1×39个即至少应取出10个球就可以保证取出的球至少有4个是同一抽屉同一颜色里的球。 故总共至少应取出10515个球才能符合要求。 思考把题中要求改为4个不同色或者是两两同色情形又如何 当我们遇到“判别具有某种事物的性质有没有至少有几个”这样的问题时想到它——抽屉原理这是你的一条“决胜”之路。 【例5】.现有64只乒乓球18个乒乓球盒每个盒子里最多可以放6只乒乓球至少有 个乒乓球盒子里的乒乓球数目相同 【分析与解】18个乒乓球盒每个盒子里至多可以放6只乒乓球。为使相同乒乓球个数的盒子尽可能少可以这样放先把盒子分成6份每份有18÷63只分别在每一份的3个盒子中放入1只、2只、3只、4只、5只、6只乒乓球即3个盒子中放了1只乒乓球3个盒中放了2只乒乓球……3个盒子中放了6只乒乓球。这样18个盒子中共放了乒乓球 123456×363只。 把以上6种不同的放法当做抽屉这样剩下64-631只乒乓球不管放入哪一个抽屉里的任何一个盒子里除已放满6只乒乓球的抽屉外都将使该盒子中的乒乓球数增加1只这时与比该抽屉每盒乒乓数多1的抽屉中的3个盒子里的乒乓球数相等。例如剩下的1只乒乓球放进原来有2只乒乓球的一个盒子里该盒乒乓球就成了3只再加上原来装有3只乒乓球的3个盒子这样就有4个盒子里装有3个乒乓球。所以至少有4个乒乓球盒里的乒乓球数目相同。 提示语 抽屉原理还可以反过来理解假如把n1个苹果放到n个抽屉里放2个或2个以上苹果的抽屉一个也没有与“必有一个抽屉放2个或2个以上的苹果”相反那么每个抽屉最多只放1个苹果n个抽屉最多有n个苹果与“n1个苹果”的条件矛盾。 运用抽屉原理的关键是“制造抽屉”。通常可采用把n个“苹果”进行合理分类的方法来制造抽屉。比如若干个同学可按出生的月份不同分为12类自然数可按被3除所得余数分为3类等等。 转载于:https://www.cnblogs.com/rmy020718/p/9443279.html
