抽屉原理.ppt

抽屉原理 ——鸽笼原理
“如果有五个鸽子笼,养鸽人养了6只鸽子,那么当鸽子飞回笼中后,至少有一个笼子中装有2只鸽子。”这个简单的事实就是著名的鸽笼原理,最早是由德国数学家狄利克雷提出的,在我们国家更多地称为抽屉原理。
抽屉原理的更一般的叙述是:
有n+1件或n+1件以上的物品要放到n个抽屉中,那么至少有一个抽屉里有两个或两个以上物品。
抽屉原理虽然简单,但应用却很广泛,它可以解答很多有趣的问题,其中有些问题还具有相当的难度。下面我们来研究有关的一些问题。
问题1 证明:从1,2,3,…,11,12中任意抽取7个数,其中至少有两个数之差为6。
解:现将这12个数按下面的方式分成6组(1,7);(2,8);(3,9);(4,10);(5,11);(6,12)。任取7个数,根据抽屉原理,至少有两个数来自同一个抽屉,这也就是说,至少有两个数之差为6。
问题2 某校初中二年级共有210名学生,请说明:至少有18名同学出生的月份是相同的。
解:由于一年有12个月,则可以将其看成12个抽屉,又因为210=12×17+6,因此根据抽屉原理可知,至少有18名同学出生的月份数是相同的。
在运用抽屉原理时,多给定的元素具有任意性,也就是说,对元素的处理是任意的;所论证的问题,也只要求存在即可,不必一定是确定的。运用抽屉原理进行论证的命题,往往含有“至少含有”、“一定有”、“不少于”、“存在”、“必然有”等词语。
利用抽屉原理的关键在于构造抽屉,从而把论证的命题的范围缩小,是问题变得简单明确,易于把握。一般来说,总是从问题自身的特点出发,先弄清所需要进行分类的特征,并指出规律,从而构造“抽屉”
利用抽屉原理解决问题的一般步骤是:
第一步:根据元素的特征,构造抽屉(是运用抽屉原理解决问题的关键);
第二步:把元素放入所构造的抽屉中;
第三步:运用抽屉原理,对所论证的问题做出解答。
问题3某校初中部有30个班,每班平均52人。已知这些学生的90%都是在1978~1980年这三年出生的,问他们中有同年同月同日出生的吗?
解:全校共有学生:52×30=1560人
1978~1980年间出生的有:1560×90%=1404人。
而这三年有:365×3+1=1096天。
由鸽笼原理知道,至少有两个同学是同年同月同日出生的。
问题4 任取5个整数,必然能够从中选出三个,使它们的和能够被3整除.
解:任意给一个整数,它被3除,余数可能为0,1,2,我们把被3除余数为0,1,2的整数各归入类r0, r1, r2。
:
1°某一类至少包含三个数;
2°某两类各含两个数,第三类包含一个数.
若是第一种情况,就在至少包含三个数的那一类中任取三数,其和一定能被3整除;
若是第二种情况,在三类中各取一个数,其和也能被3整除.
综上所述,原命题正确.
问题5 从1到100这100个自然数中,任意抽取51个数,其中一定存在两个数,这两个数的一个是另一个的整数倍。(提示:任何一个正整数都可以表示成一个奇数与2n的乘积的形式,而且这种表示方法是唯一的。)
解:由于任何一个正整数都可以表示成一个奇数与2n的乘积的形式,而且这种表示方法是唯一的。因此我们可以按下面的方法来构造50个抽屉:
{ 1,1×