抽屉原理又称鸽巢原理,最经典的例子莫过于下例了:
一个养鸽人养了10只鸽子,但只准备了9个鸽巢,他发现,无论这些鸽子如何归巢,必然至少有一个鸽巢内的鸽子不少于2只。
一般的表述方法如下:
第一原理:
(1)把多于n个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。
(2)把多于mn(m乘以n)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于m+1的物体。
(3)把无穷多件物体放入n个抽屉,则至少有一个抽屉里 有无穷个物体。
第二原理:
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体
抽屉原理 桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,有的抽屉可以放一个,有的可以放两个,有的可以放五个,但最终我们会发现至少我们可以找到一个抽屉里面至少放两个苹果。这一现象就是我们所说的抽屉原理。
抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有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的倍数。
桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面放两个苹果。
这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1或多于n+1个元素放到n个集合中去,其中必定至少有一个集合里有两个元素。”
抽屉原理有时也被称为鸽巢原理(“如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子”)。它是组合数学中一个重要的原理。
证法一:
用反证法。
假设任何三个孩子分到糖的和都小于45。
现设5个孩子分到糖的数量分别是
a,b,c,d,e
设k=a+b+c
易知k又有d+e=76-k
根据鸽巢原理,a,b,c三个数中至少有一个不小于k/3
无妨设a≥k/3
从而
a+d+e≥k/3+ 76-k=76-2k/3 ①
再据前面的假设,应有
a+d+e综合①,②得
76-2k/3解之得
k>46.5
这与前面的k
证法二:
仍然用反证法.
假设任何三个孩子分到糖的和都小于45。
现设5个孩子分到糖的数量分别是
a,b,c,d,e
则从这5个数中任取3个,共有10种情况。
且有:
a+b+ca+b+d……
c+d+e把这10个式子相加,便有
6(a+b+c+d+e)从而a+b+c+d+e这与a+b+c+d+e=76矛盾。证完。
佛祖割肉救鸽子的故事,出自《六度集经》卷一《萨波达王本生》 。
释迦牟尼佛过去世行菩萨道当中,受到忉利天天主的测试。测试释迦牟尼佛是不是真的在行菩萨道,是不是真的有布施心。所以他就化为老鹰追赶一只鸽子,鸽子惊慌飞跑,逃进释迦牟尼佛的怀抱。因为释迦牟尼佛发心行菩萨道,内心充满着对众生的慈悲,没有对众生嗔恨、伤害的念头,那种心念所散发出来的心波,能够感动到动物,使动物一看到他的身相,接触到他的影子,就有一种安慰的、无惧的感觉。所以,这只小鸽子投进了释迦牟尼佛的怀抱,感觉到生命的被救与安稳。这时追赶过来的老鹰就跟释迦牟尼佛说:“这只鸽子是我的猎物,应该还给我,否则我会当下饿死。有了这只鸽子,就有了我的生命,没有这只鸽子,就没有我的生命。你同情这只鸽子,难道你就不同情我吗?”释迦牟尼佛为了救鸽子,也为了同情老鹰,不惜跟老鹰商量,要割下自己的肉来喂鹰。“好,可以呀!这只鸽子肉有多重,你所割下来的肉也必须有多重!”释迦牟尼佛就割下身上的肉跟鸽子的体重相秤量,结果切下一块,重量不如鸽子,再切下一块,还是不够。最后舍命全身秤量,才与鸽子的重量相等。这个时候,忉利天王感动了,他现出天王之身,然后向这一位菩萨匍伏顶礼、赞叹,是真菩萨,必定成佛,同时请菩萨将来成佛的时候,务必也要度他。
这个故事是为了凸显佛祖那种济世为怀,普度众生的精神。
放鸽子,现在这个词主流的意思是说不遵守诺言,带有欺骗的含义。
另一方面,比较少见的是警察或江湖上的黑话含义:利用色相勾引这个嫖客,然后进行其他的违法犯罪活动,它不简简单单地是一个卖淫,而是通过卖淫这种手段,获取更大的利益。这种东西有多种情况,有利用色相勾引以后,进行抢劫的,有进行盗窃的,等等,进行敲诈的。
要说放鸽子的来历,目前至少有3中说法: 1.源于旧上海的彩票,俗称“白鸽票”,一般都有去无回,它也可能是老北京养鸽子的爷们儿的惨痛教训,鸽子放出去就回不来——有专门裹人家鸽子的人在那儿等着呢。 真正的由来是:古时候人们通信都是用鸽子来通信的,有一次两个人约定,到时候给我来信.但其中一人,只给放来鸽子没有写信.另一人就说,你怎么只放鸽子.不履行诺言.放鸽子就这样来了. 2.本意是指一种诱拐别人名贵鸽子的行为。
具体方法是训练出一种专用的“诱鸽”,在别人放飞鸽子时,放出自己的“诱鸽”,混到鸽群中。“诱鸽”会诱骗鸽群迷失方向,把它们引回到偷窃者的鸽笼中。
后来这个词的含义就发生了引申,成为了违约和欺诈行为的代名词。 3.旧中国上海滩一种诈骗伎俩 以女人到雇主要做保姆,或小妾为名然后卷走被骗人的财物,黑道上称为“放鸽子”。
鸽巢原理是抽屉原理.抽屉原理又称鸽巢原理,它是组合数学的一个基本原理,最先是由德国数学家狄利克雷明确地提出来的,因此,也称为狄利克雷原理。鸽巢原理,又名狄利克雷抽屉原理、鸽巢原理。
其中一种简单的表述法为:若有n个笼子和n+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少2只鸽子。
另一种为:若有n个笼子和kn+1只鸽子,所有的鸽子都被关在鸽笼里,那么至少有一个笼子有至少k+1只鸽子。
拉姆齐定理是此原理的推广。
常见形式
第一抽屉原理
原理1: 把多于n个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。
证明(反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n,而不是题设的n+k(k≥1),故不可能。
原理2 :把多于mn(m乘以n)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于m+1的物体。
证明(反证法):若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体,与题设不符,故不可能。
原理3 :把无穷多件物体放入n个抽屉,则至少有一个抽屉里 有无穷个物体。
原理1 、2 、3都是第一抽屉原理的表述。
第二抽屉原理
把(mn-1)个物体放入n个抽屉中,其中必有一个抽屉中至多有(m—1)个物体。
证明(反证法):若每个抽屉都有不少于m个物体,则总共至少有mn个物体,与题设矛盾,故不可能。
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。
蜀ICP备2020033479号-4 Copyright © 2016 学习鸟. 页面生成时间:0.286秒