国家公务员考试行测:抽屉原理的经典解题思路


  抽屉原理在公务员考试中的数字运算部分时有出现。抽屉原理是用最朴素的思想解决组合数学问题的一个范例,我们可以从日常工作中的实例来体会抽屉原理的应用。抽屉原理的内容简明朴素,易于接受,它在数学问题中有重要的作用。许多有关存在性的证明都可用它来解决。


  先来看抽屉原理的一般叙述:

  抽屉原理(1):讲多于n件的物品任意放到n个抽屉中,那么至少有一个抽屉中的物品的件数不少于2。抽屉原理(1)可以进行推广,把无穷多个元素放入有限个集合里,则一定有一个集合里含有无穷多个元素。

  抽屉原理(2):将多于 件的物品任意放到抽屉中,那么至少有一个抽屉中的物品的件数不少m+1。也可以表述成如下语句:把m个物品任意放入n(n≤m)个抽屉中,则一定有一个抽屉中至多要有k件物品。其中 k=〔m/n 〕 ,这里〔m/n 〕表示不大于m/n的最大整数,即m/n的整数部分。


  掌握了抽屉原理解题的步骤就能思路清晰的对一些存在性问题、最小数目问题做出快速准确的解答。一般来讲,首先得分析题意,分清什么是“物品”,什么是“抽屉”,也就是什么作“物品”,什么可作“抽屉”。 接着制造抽屉。这个是关键的一步,这一步就是如何设计抽屉。根据题目条件和结论,结合有关的数学知识,抓住最基本的数量关系,设计和确定解决问题所需的抽屉及其个数,为使用抽屉铺平道路。 最后运用抽屉原理。观察题设条件,结合第二步,恰当应用各个原则或综合运用几个原则,以求问题之解决。


  下面两个典型例题的解题过程充分展现了抽屉原理的解题过程,希望读者能有所体会。

  例1:证明任取6个自然数,必有两个数的差是5的倍数。


  证明:考虑每个自然数被5除所得的余数。即自然数可以作为物品,被5除所得余数可以作为抽屉。显然可知,任意一个自然数被5除所得的余数有5种情况:0,1,2,3,4。所以构造5个抽屉,每个抽屉中所装的物品就是被5除所得余数分别为0,1,2,3,4的自然数。运用抽屉原理,考虑“最坏”的情况,先从每个抽屉中各取一个“物品”,共5个,则再取一个物品总能在先取的5个中找到和它出自于同一抽屉的“物品”,即它们被5除余数相同,所以它们的差能整除5。

 
  例2: 黑色、白色、黄色的筷子各有8根,混杂地放在一起,黑暗中想从这些筷子中取出颜色不同的2双筷子(每双筷子两根的颜色应一样),问至少要取材多少根才能保证达到要求?

  解:这道题并不是品种单一,不能够容易地找到抽屉和苹果,由于有三种颜色的筷子,而且又混杂在一起,为了确保取出的筷子中有2双不同颜色的筷子,可以分两步进行。第一步先确保取出的筷子中有1双同色的;第二步再从余下的筷子中取出若干根保证第二双筷子同色。 首先,要确保取出的筷子中至少有1双是同色的,我们把黑色、白色、黄色三种颜色看作3个抽屉,把筷子当作苹果,根据抽屉原则,只需取出4根筷子即可。其次,再考虑从余下的20根筷子中取多少根筷子才能确保又有1双同色筷子,我们从最不利的情况出发,假设第一次取出的4根筷子中,有2根黑色,1根白色,1根黄色。这样,余下的20根筷子,有6根黑色的,7根白色的,7根黄色的,因此,只要再取出7根筷子,必有1根是白色或黄色的,能与第一次取出的1根白色筷子或黄色筷子配对,从而保证有2双筷子颜色不同,总之,在最不利的情况下,只要取出4+7=11根筷子,就能保证达到目的。


  以上两个题目都考虑了“最坏”的情况,这是考虑涉及抽屉原理的最值问题的常用思路。最后看一个有趣的数学问题,它体现了抽屉原理在证明存在性问题中的应用。

  “证明在任意6个人的集会上,或者有3个人以前彼此相识,或者有三个人以前彼此不相识。”

  这个问题可以用如下方法简单明了地证出:


  在平面上用6个点A、B、C、D、E、F分别代表参加集会的任意6个人。如果两人以前彼此认识,那么就在代表他们的两点间连成一条红线;否则连一 条蓝线。考虑A点与其余各点间的5条连线AB,AC,...,AF,它们的颜色不超过2种。根据抽屉原理可知其中至少有3条连线同色,不妨设AB,AC, AD同为红色。如果BC,BD,CD3条连线中有一条(不妨设为BC)也为红色,那么三角形ABC即一个红色三角形,A、B、C代表的3个人以前彼此相 识:如果BC、BD、CD3条连线全为蓝色,那么三角形BCD即一个蓝色三角形,B、C、D代表的3个人以前彼此不相识。不论哪种情形发生,都符合问题的结论。