抽屉原理
把八个苹果任意地放进七个抽屉里， 的苹果.
抽屉原则有时也被称为鸽巢原理，它是德国数学家狄利克雷首先明确的提出来并用以证 明一些数论中的问题，因此，也称为狄利克雷原则•它是组合数学中一个重要的原理•把它 推广到一般情形有以下几种表现形式. 形式一：
证明：设把n+1个元素分为n个集合A, A,…，A,用ai, ©,…，an表示这n个集 合里相应的元素个数，需要证明至少存在某个
不论怎样放，至少有一个抽屉放有两个或两个以上
a大于或等于2
（用反证法）假设结论不成立，即对每一个a都有a< 2,则因为a是整数，应有1, 于是有：
ai+ 比+…十 anW 1 + 1 + ・・・+ 1= n< n+1
这与题设矛盾.
所以，至少有一个 2,即必有一个集合中含有两个或两个以上的元素. 形式二： 设把n •
1个元素分为n个集合A, A,…，A,用a1, a2,…，an表示这n个集合
里相应的元素个数，需要证明至少存在某个
ai
F或等于m^ 1 •
（用反证法）假设结论不成立，即对每一个 ai< m,于是有：
a1+ a2+・・・+ an W
< n •
n= n • m n个m
a都有a< 1，则因为a是整数，应有
1
这与题设相矛盾.
所以，至少有存在一个 高斯函数： 对任意的实数x,
a > 1
[x]表示“不大于x的最大整数”.
例如：[3 • 5] = 3, [2 • 9] = 2,
[—2 • 5] =- 3, [7] = 7,……
一般地，我们有：[x] W x< [x] + 1 形式三：
证明：设把n个元素分为k个集合A, 合里相
应的元素个数，需要证明至少存在某个 （用反证法）假设结论不成立，即对每一个
A,…，A，用a1, a2，…，ak表示这k个集 a大于
或等于[n/ k].
a1 + a?+…+ ak < [ n/ k]+[ n/ k]+ …+[ n/ k] k 个[n/k]
=k •[ n/ k] W k •（ n/ k） = n
二 a1+ a2+・・・+ ak a都有 ai< [n/k]，于是有： [n/k] 证明：设把qi + q2+・・・+ qn— n+ 1个元素分为n个集合A, A2,…，A,用ai, a2,…， an表示这n个集合里相应的元素个数，需要证明至少存在某个 （用反证法）假设结论不成立，即对每一个 —1，于是有： i，使得a大于或等于q . ai都有a< qi,因为a为整数，应有a < q ai+ 比+…十 anW qi + q2+・・・+ qn— n < qi + q2 +…+ qn— n+ 1 这与题设矛盾. 所以，假设不成立，故必有一个 i，在第i个集合中元素个数 ai> qi 形式五： 证明：（用反证法）将无穷多个元素分为有限个集合，假设这有限个集合中的元素的个 数都是有限个，则有限个有限数相加，所得的数必是有限数，这就与题设产生矛盾，所以， 假设不成立，故必有一个集合含有无穷多个元素. 例题1： 400人中至少有两个人的生日相同. 分析：生日从1月1日排到12月31日，共有366个不相同的生日，我们把 366个不 同的生日看作 366个抽屉，400人视为400个苹果，由表现形式 1可知，至少有两人在同一 个抽屉里，所以这 400人中有 两人的生日相同. 解：将一年中的 366天视为366个抽屉，400个人看作400个苹果，由抽屉原理的表 现形式1可以 得知：至少有两人的生日相同. 例题2:边长为1的正方形中，任意放入9个点，求证这9个点中任取3个点组成的三角形 中，至少有一个的面积不超过 1/8 . 9 解：将边长为1的正方形等分成边长为 丄的四个小正方形，视这四个正方形为抽屉， 2 个点任意放入这四个正方形中，据形式 2，必有三点落入同一个正方形内.现特别取出这个 正方形来加以讨论. 把落在这个正方形中的三点记为 图可知： D E、F.通过这三点中的任意一点（如 E）作平行线，如 △ DEF = W 1 1 SA DEG^ S\\ EFG 2 2 1 ；1 (1 h) 2 2 2 D( F =h 1 h 4 8 4 例题3：任取5个整数，必然能够从中选出三个，使它们的和能够被 _ 1 —8 3整除. 证明：任意给一个整数，它被 3除，余数可能为0, 1, 2,我们把被3除余数为0, 1 , 2的整数各归入类 ro, r1, r2•至少有一类包含所给5个数中的至少两个•因此可能出现两 种情况： 综上所述，原命题正确. 例题4:九条直线中的每一条直线都将正方形分成面积比为 线中至少有三条经过同一点. 2 ：3的梯形，证明：这九条直 证明：如图，设 PQ是一条这样的直线，作这两个梯形的中位线 B MN N C •••这两个梯形的高相等， •••它们的面积之比等于中位线长的比，即 | MH ：| NH. •••点H有确定的位置. (它在正方形一对对边中点的连线上，并且 | MH| ：丨NH = 2 : 3). 由几何上的对称性，这种点共有四个，即，图中的 H J、I、K已知的九条适合条件 的分割直线中的每一条必须经过 H J、I、K这四点中的一点.把H J、丨、K看成四个抽屉, 九条直线当成 9个苹果，即可得出必定有 3条分割线经过同一点. 例题5:某校派出学生204人上山植树15301株，其中最少一人植树 50株，最多一人植树 100株，则至少有 5人植树的株数相同. 证明：按植树的多少，从 人植树的株数在同一个抽屉里. 50到100株可以构造51个抽屉，则个问题就转化为至少有 5 (用反证法)假设无5人或5人以上植树的株数在同一个抽屉里， 那只有5人以下植树的 株数在同一个抽屉里，而参加植树的人数为 204人，所以，每个抽屉最多有 4人，故植树 的总株数最多有： 4(50 + 51 +…+ 100) =4x (50 100) 51 2 =15300 V15301 得出矛盾. 因此，至少有5人植树的株数相同. 练习: 1.边长为1的等边三角形内有 5个点，那么这5个点中一定有距离小于 0.5的 两点. 2 .边长为1的等边三角形内，若有 n2+ 1个点，则至少存在 2点距离小于n . 3. 求证：任意四个整数中，至少有两个整数的差能够被 3整除. 4. 某校高一某班有 50名新生，试说明其中一定有二人的熟人一样多. 5. 某个年级有202人参加考试，满分为 100分，且得分都为整数，总得分为 10101分，则 至少有3人得分相同. 因篇幅问题不能全部显示，请点此查看更多更全内容