抽屉原理

描述:

\quad桌上有十个苹果,要把这十个苹果放到九个抽屉里,无论怎样放,我们会发现至少会有一个抽屉里面至少放两个苹果。这一现象就是我们所说的“抽屉原理”。 抽屉原理的一般含义为:“如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素,假如有n+1n+1个元素放到n个集合中去,其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。它是组合数学中一个重要的原理。

第一抽屉原理:

原理11: 把多于nn(n+k)(n+k)的物体放到nn个抽屉里,则至少有一个抽屉里的东西不少于两件。

证明(反证法):如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n×1n×1个,而不是题设的n+k(k1)n+k(k≥1),故不可能。

原理22:把多于mnmn(mnm*n)+1+1nn不为00)个的物体放到nn个抽屉里,则至少有一个抽屉里有不少于(m+1m+1)的物体。

证明(反证法):若每个抽屉至多放进mm个物体,那么nn个抽屉至多放进mnmn个物体,与题设不符,故不可能。

原理33 :把无穷多件物体放入nn个抽屉,则至少有一个抽屉里 有无穷个物体。
原理1231 、2 、3都是第一抽屉原理的表述。这三条都比较好理解

第二抽屉原理:

把多于nkn*k个物体放入nn个抽屉中,其中必有一个抽屉中物体有(k+1)(k+1)个或(k+1)(k+1)个以上

应用:

ex1:

某校五年级有3232名学生是在五月份出生,那么其中至少有两名学生的生日是在同一天,为什么?
解法一:五月份有3131天,看作是3131个抽屉,3232名学生看做3232个苹果,因为苹果数量多于抽屉数量,根据抽屉原理1,至少有一个抽屉有两个或两个以上的苹果,所以至少有两名学生的生日在同一天。
解法二:使用矛盾法。假设结论不成立,那么55月的3131天中,每天过生日的都少于两人,即每天最多11人过生日,那么131=311*31=31,即55月份过生日的人数最多3131人,这与题目中五月有3232人过生日产生矛盾,故,至少有两名学生在同一天过生日。

ex2:

在正方形内任意放55点,其中必有两点的距离不大于正方形对角线的一半,为什么?
抽屉原理
将正方形分成44个大小相同的小正方形(看成抽屉),对于正方形内任意放的55点(看成苹果),根据抽屉原理可知道,至少有两个点在一个小正方形内,这两点的距离最远时,是两点分别在小正方形的对角顶点上,所以这两点的距离等于或小于小正方形对角线长。因此,必有两点距离不大于正方形对角线的一半。

ex3:

有一只口袋中有红色与黄色球各44只,现有4个小朋友,每人可以从口袋中随意去22个小球。证明:必须有两个小朋友,他们取出的两个球的颜色完全一样。

本题,可以将两个球的颜色搭配看成是抽屉,则有 红黄,红红,黄黄,那么44个小朋友看成是44个物品

ex4:

某班图书馆有诗歌、童话、画册三类课外读物,规定每位同学最多可以借阅两种不同类型的书。问,至少有几位同学来借图书,即可断定必有两位同学借阅的书的类型相同?

每位同学最多借阅两种不同的书,那么书的种类搭配可是有 C23+3=6C32+3=6C_2^3+3=6C_3^2+3=6种,将其看成是66个抽屉,根据抽屉原理至少77位同学借书,才能保证必定有两位同学借阅的书类型相同。

ex5:

有一个331010列共310(3*10)个方格的长方形,把每个小方格图上红色或黄色,每列有多少种涂法?无论怎样涂,至少有两列的涂色方法相同,为什么?

每列有33格,每格有22种选择,那么每列就是23=823=823=823=8种涂法。
88种涂法就是88个抽屉,1010列就是1010个苹果,那么至少两列涂色方法相同(物品数量>抽屉)

ex6:

从一列数1591393971、5、9、13、。。。、93、97中,任取1414个数,证明:其中必有两个数的和等于102102

9714+1=25\frac{(97-1)}{4}+1=25个数
先考虑如何作抽屉,2525个数可以分1313组(1313个抽屉):{1},{5,97},{9,93},.{49,53}\{1\},\{5,97\},\{9,93\},…….\{49,53\}2525个数中任取1414个数,也就是从1313组中任取1414个数,必有两个数在同一组中,同一组中的两个数的和必为102.102.

ex7:

袋子里有红、黄、黑、白珠子足够多,闭上眼睛要想摸出颜色相同的6粒珠子,至少要摸出几粒珠子,才能保证达到目的?

分析:摸的珠子应多于44种颜色的55(k+1=6k=5)(k+1=6 k=5)
解一:把44种颜色看成44个抽屉,袋子里的珠子看作苹果,根据抽屉原理二,取出的珠子数多于454*5粒,就必有6666粒以上的珠子颜色相同。所以至少摸出2121粒珠子,才能保证有66粒珠子颜色相同。

解二:根据极端原理,从最不利的情况考虑,假设每种颜色的珠子都摸了55颗,一共摸了45=204*5=20颗,那么只要再摸11颗,不管是什么颜色,都必有66颗珠子颜色相同。所以至少摸出2121粒珠子,才能保证66粒珠子颜色相同。