抽屉原理.docx

抽屉原理
抽屉原理
抽屉原理
抽屉原理
在数学问题中有一类与“存在性”有关的问题，例如：“
13个人中至少有两个人出生
在相同月份”； “某校 400 名学生中，一定存在两名学生，
他们在同一天过生日”； “2003
个人任意分成 200 个小组， 一定存在一组， 其成员数不少于
11”。这类存在性问题中， “存
在”的含义是“至少有一个”。
在解决这类问题时， 只要求指明存在， 一般并不需要指出哪
一个，也不需要确定通过什么方式把这个存在的东西找出来。
这类问题相对来说涉及到的运
算较少，依据的理论也不复杂，我们把这些理论称之为“抽屉原理”。
（一） 抽屉原理的常见形式
定理 1：如果把 n+1 个元素分成 n 个集合，那么不管怎么分，都存在一个集合，其中至少有
两个元素。
证明：（用反证法）若不存在至少有两个元素的集合，则每个集合至多 1 个元素，从而 n 个
集合至多有 n 个元素，此与共有 n+1 个元素矛盾，故命题成立。
在定理 1 的叙述中， 可以把“元素”改为“物件”， 把“集合”改成“抽屉”， 抽屉原
理正是由此得名。
定理 2
：把多于 mn(m 乘以 n) 个的物体放到
n 个抽屉里，则至少有一个抽屉里有
m+1
个或多于 m+1个的物体。
证明：（反证法）若每个抽屉至多放进
m个物体 , 那么 n 个抽屉至多放进
mn 个物体 ,
与题设不符，故不可能
定理 3
：把无穷多件物体放入
n 个抽屉，则至少有一个抽屉里
有无穷个物体。 .
定理 4
：把（ mn－ 1 ）个物体放入
n 个抽屉中，其中必有一个抽屉中至多有（
m— 1）
个物体。
证明：（反证法）若每个抽屉都有不少于 m 个物体，则总共至少有 mn 个物体，与题
设矛盾，
（二）抽屉原理研究的几类问题分析：
（1）整除问题：
例 1 ：对于任意的五个自然数，证明其中必有 3 个数的和能被
证明∵任何数除以 3 所得余数只能是 0， 1， 2，不妨分别构造为
[0] ， [1] ， [2]

3整除.
3 个抽屉：
抽屉原理
抽屉原理
抽屉原理
①若这五个自然数除以 3 后所得余数分别分布在这 3 个抽屉中 ( 即抽屉中分别为
含有余数为 0,1,2 的数 ) ，我们从这三个抽屉中各取 1 个 ( 如 1~5 中取 3,4,5) ，其和 (3
+4+5=12) 必能被 3 整除 .
②若这 5 个余数分布在其中的两个抽屉中，则其中必有一个抽屉，包含有 3 个余
数（抽屉原理），而这三个余数之和或为 0 ，或为 3，或为 6，故所对应的 3 个自然数
之和是 3 的倍数 .
③若这 5 个余数分布在其中的一个抽屉中，很显然，必有 3 个自然数之和能被 3
整除 .
例 1′：对于任意的 11 个整数，证明其中一定有 6 个数，它们的和能被