“400人中至少有两稍僚敉视个人的生日相同”这个事实显而易见,但这个事实却蕴含着数学里的一个简单原理——抽屉原理,该原理应用非常广泛,它能让许多看似复杂的问题变得通俗易懂。例如下面这个蟮烫忿垴生活中的问题:“某校派出学生204人上山植树15301株,其中最少一人植树50株,最多一人植树100株,请问是否至少有5人植树的株数相同?”
在解决这个问题之前,我们先来了解一下什么是抽屉原理。抽屉原理也被称为鸽巢原理,它是组合数学中一个重要的原理,它有很多种形式,我们在此只介绍两种常见易懂的形式。
【原理1】把多于n+k个的物体放到n个抽屉里,则至少有一个抽屉里的东西不少于两件。
【原理2】把多于mn(m乘以n)(n不为0)个的物体放到n个抽屉里,则至少有一个抽屉里有不少于(m+1)的物体。
下面我尝试用上述原理解决刚才的问题:
【解析】结论:至少有5人植树的株数相同,证明如下
按植树的多少,从50到100株可以构造51个抽屉,这个问题就转化为至少有5人植树的株数在同一个抽屉里。
下面采用反证法,假设5人或5人以上植树的株数在同一个抽屉里,那只有5人以下植树的株数在同一个抽屉里,而参加植树的人数为204人,所以,每个抽屉最多有4人,故植树的总株数最多有:
这与“植树15301株”矛盾
所以至少有5人植树的株数相同。
我们再来看一个有趣的问题,1947年,匈牙利全国数学竞赛有一道这样的试题:“证明:任何六个人中,一定可以找到三个互相认识的人,或者三个互不认识的人。”
【解析】用A、B、C、D、E、F代表六个人,从中随便找一个,例如A吧,把其余五个人放到“与A认识”和“与A不认识”两个“抽屉”里去,根据抽屉原理,至少有一个抽屉里有三个人。不妨假定在“与A认识”的抽屉里有三个人,他们是B、C、D。
如果B、C、D三人互不认识,那么我们就找到了三个互不认识的人;如果B、C、D三人中有两个互相认识,例如B与C认识,那么,A、B、C就是三个互相认识的人。不管哪种情况,本题的结论都是成立的。
抽屉原理简单易懂但应用广泛,它不仅在数学中有用,在现实生活中也到处在起作用,如招生录取、就业安排、资源分配、职称评定等等,都不难看到抽屉原理的作用。不光抽屉原理,数学中有很多类似的应用广泛的原理。
作者:韩静波