数学中的抽屉原理 |
|
|
来源:不详 更新时间:2012-7-17 12:10:36 |
|
|
先看简单的事实:把3本书放到两个抽屉里,只有两种情况:一个一本一个二本,或一个三本一个没有。无论哪种情况,都至少有一个抽屉里有两本或两本以上的书。更一般地说,只要被放置的书数比抽屉数目大,就一定会有两本或两本以上的书放进同一抽屉。
(一)抽屉原理的常见式
【原理一】:如果把n个东西放进n(m>n)只抽屉里,则至少有一只抽屉要放进两个或两个以上的东西。
【例1】求证:在任意选取的n+1个整数中,至少存在两个整数,它们的差能被n整除。
证明:对于n+1个整数,被除所得的余数为0,1,…,n-1共n类,按余数的不同分成的n类中,至少有两个在同一类里,即这两个数被n除时所得的余数相同,那么它们的差就一定能被n整除。
【例2】幼儿园有三种塑料玩具(白兔、熊猫、长颈鹿)各若干个,每个小朋友任意选择两件。证明:不管怎样挑选,在七个小朋友中总有两个人选的玩具相同。
证明:从三种玩具中挑选两件,搭配方式共有下列六种:(兔、兔)、(兔、熊猫)、(兔、长颈鹿)、(熊猫、熊猫)、(熊猫、长颈鹿)、(长颈鹿、长颈鹿),每一种可以看作一个抽屉,七人的7种选法中,只有6种不同的搭配,由抽屉原理,七人中至少有两人挑选玩具时搭配方式相同。
【原理二】:如果把多于m×n件东西,任意放进n个抽屉,那么至少有一个抽屉里有不少于m+1件东西。
【例3】在口袋里有红色、蓝色和黄色的小球若干个,21个人轮流从袋中取球,每人每次取3个球。求证:这21个人中至少有3个人取出的颜色相同。
证明:取出的三个球颜色是同一色的(即全红、全蓝或全黄)有三种不同的情况,是两色的(如两红一蓝等)有6种情况,是三色的(即红、蓝、黄三色小球各一个)只有一种情况,故共可分成10类。由抽屉原理二知道,把21个人所取出的球按颜色可归为这10类中,则必有一类至少有(个)。
所以,21个人中至少有3人取出的球的颜色相同。
运用抽屉原理只是肯定了“存在”、“总有”、“至少有”,却不能确切地指出哪个抽屉里存在多少。
(二)怎样应用抽屉原理
应用抽屉原理解题,一般有三个步骤:
(1)列出分类对象;
(2)找出分类规则(即构造抽屉)并证明每一类中的东西符合题意;
(3)根据题意应用抽屉原理证明结论成立。
【例4】给定997个整数1,3,5,…,1993,求证:从中任取500个不同的数,其中必有两个整数的和为1994。
证明:把这997个整数中两数相加和为1994的每两个数分为一组,剩余的数为一组,可分为499组,为:
{1,1993},{3,1991},…,{995,999},{997}
根据原理一,从这499组中任取500个数,必有两个数取自同一组中,那么这两个数之和为1994,问题得证。
【例5】有21个自然数,且,求证:所有的差数中至少有四个相等。
证明:以所有可能的差1,2,3,…,69作为抽屉扣住“差”,构成下列差数作为分类对象。
对于可作出20个差数(即),对于可作出19个差数(即)…直至可作出一个差数,即(),因此共有1+2+3+…+19+20=210个差数。根据原理二,由[]+1=4,即至少有4个差相等,于是命题得证。
【例6】求证:从任意n个自然数中可以找到若干个数,使它们的和是n的倍数。
证明:以自然数被n除所得的余数0,1,2,…,n-1分类制造抽屉,扣住“和”构造下列和数:
…
若中有一个是n的倍数,问题得证。(略)
可以看到,如直接给出了分类对象,只要恰当制造抽屉就可以了;如果没有直接给出分类对象,就要根据题意先构造出分类对[1] [2] [3] 下一页
|
上一个数学: 让消费者数学无能的11招 下一个数学: 夏日防走光 用数学知识打败偷窥狂 |
|
|
|
|