下载文档原格式
第5讲抽屉原理初步一、学习目标1.理解抽屉原理的概念，学会从“最倒霉”情况思考问题。
2.利用抽屉原理解释并证明一些结论及生活中的一些问题。
二、知识要点桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面至少放两个苹果。
这一现象就是我们所说的“抽屉原理”。
抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。
” 抽屉原理有时也被称为鸽巢原理。
它是组合数学中一个重要的原理。
三、例题精选【例1】把15个球放进4个箱子里，至少有多少个球要放进同一个箱子里？【巩固1】在街上任意找来50个人，可以确定，这50人中至少有多少个人的属相相同？【例2】库房里有一批篮球、排球、足球，每人任意搬运两个，问在41个搬运者中，至少有几个人搬运的球完全相同？【巩固2】桌子上摆放着香蕉、橘子、芒果、橙子各若干个，50个小朋友可以从中任取两种不同的水果，那么至少有几个小朋友取的水果完全相同？【例3】某班有40个小朋友，张老师拿来了一些糖果，随意分给小朋友们。
那么张老师至少需要多少块糖果，才能保证至少有一个小朋友可以分到3块？【巩固3】体育场聚集着一群人在看演唱会，那么至少有多少人，才能保证观众中有6个人的生日在同一天？【例4】把125本书分给若干个学生，为保证至少有一人可以分到4本书，那么学生最多可以有多少人？【巩固4】100个苹果分给若干只猴子，为保证至少有一只猴子拿到7个苹果，那么猴子最多可以是多少只？【例5】张老师在一次数学课上出了两道题，规定每道题做对得2分，做错得0分，没做扣1分。
张老师说：可以肯定全班同学中至少有8名学生的得分相同。
那么，这个班最少有多少人？【巩固5】一个箱子里2行5列共10个小方格，将每一个小方格涂上红色或蓝色。
小威发现无论如何涂，其中至少总有两列的涂色方式是一样的，试说明原因。
一．第一抽屉原理原理1：把多于n个的物体放到n个抽屉里，则至少有一个抽屉里有2个或2个以上的物体。
证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是n，而不是题设的n+k(k≥1)，这不可能.原理2：把多于mn(m乘以n)个的物体放到n个抽屉里，则至少有一个抽屉里有m+1个或多于m+1个的物体。
证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn 个物体,与题设不符，故不可能。
原理3：把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体。
二．第二抽屉原理把（mn－1）个物体放入n个抽屉中，其中必有一个抽屉中至多有（m—1）个物体。
例1：400人中至少有2个人的生日相同.例2：我们从街上随便找来13人，就可断定他们中至少有两个人属相相同.例3: 从任意5双手套中任取6只，其中至少有2只恰为一双手套。
例4:从任意5双手套中任取6只，其中至少有2只恰为一双手套。
例5：从数1，2，...，10中任取6个数，其中至少有2个数为奇偶性不同。
三．抽屉原理与整除问题整除问题：把所有整数按照除以某个自然数m的余数分为m类，叫做m的剩余类或同余类，用[0]，[1]，[2]，…，[m-1]表示.每一个类含有无穷多个数，例如[1]中含有1，m+1，2m+1，3m+1，….在研究与整除有关的问题时，常用剩余类作为抽屉.根据抽屉原理，可以证明：任意n+1个自然数中，总有两个自然数的差是n的倍数。
(证明：n+1个自然数被n整除余数至少有两个相等（抽屉原理），不妨记为m=a1*n+b n=a2*n+b，则m-n整除n)。
例1 证明：任取8个自然数，必有两个数的差是7的倍数。
四．经典练习：1．木箱里装有红色球3个、黄色球5个、蓝色球7个，若蒙眼去摸，为保证取出的球中有两个球的颜色不相同，则最少要取出多少个球？解析：把3种颜色看作3个抽屉，若要符合题意，则小球的数目必须大于7，故至少取出8个小球才能符合要求。
高中数学竞赛讲义-抽屉原理第一篇：高中数学竞赛讲义-抽屉原理抽屉原理在数学问题中有一类与“存在性”有关的问题，例如：“13个人中至少有两个人出生在相同月份”；“某校400名学生中，一定存在两名学生，他们在同一天过生日”；“2003个人任意分成200个小组，一定存在一组，其成员数不少于11”；“把[0，1]内的全部有理数放到100个集合中，一定存在一个集合，它里面有无限多个有理数”。
这类存在性问题中，“存在”的含义是“至少有一个”。
在解决这类问题时，只要求指明存在，一般并不需要指出哪一个，也不需要确定通过什么方式把这个存在的东西找出来。
这类问题相对来说涉及到的运算较少，依据的理论也不复杂，我们把这些理论称之为“抽屉原理”。
“抽屉原理”最先是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题的，所以又称“迪里赫莱原理”，也有称“鸽巢原理”的。
这个原理可以简单地叙述为“把10个苹果，任意分放在9个抽屉里，则至少有一个抽屉里含有两个或两个以上的苹果”。
这个道理是非常明显的，但应用它却可以解决许多有趣的问题，并且常常得到一些令人惊异的结果。
抽屉原理是国际国内各级各类数学竞赛中的重要内容，本讲就来学习它的有关知识及其应用。
（一）抽屉原理的基本形式定理1、如果把n+1个元素分成n个集合，那么不管怎么分，都存在一个集合，其中至少有两个元素。
证明：（用反证法）若不存在至少有两个元素的集合，则每个集合至多1个元素，从而n个集合至多有n个元素，此与共有n+1个元素矛盾，故命题成立。
在定理1的叙述中，可以把“元素”改为“物件”，把“集合”改成“抽屉”，抽屉原理正是由此得名。
同样，可以把“元素”改成“鸽子”，把“分成n个集合”改成“飞进n个鸽笼中”。
“鸽笼原理”由此得名。
例题讲解1．已知在边长为1的等边三角形内（包括边界）有任意五个点（图1）。
证明：至少有两个点之间的距离不大于2．从1-100的自然数中，任意取出51个数，证明其中一定有两个数，它们中的一个是另一个的整数倍。
第一抽屉原理原理1：把多于n+k个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。
证明（反证法）：如果每个抽屉至多只能放进一个物体,那么物体的总数至多是n×1,而不是题设的n+k（k≥1），故不可能。
原理2 ：把多于mn（m乘以n)+1(n不为0）个的物体放到n个抽屉里，则至少有一个抽屉里有不少于（m+1）的物体。
证明（反证法）：若每个抽屉至多放进m个物体,那么n个抽屉至多放进mn个物体，与题设不符，故不可能。
原理3 ：把无穷多件物体放入n个抽屉，则至少有一个抽屉里有无穷个物体.原理1 、2 、3都是第一抽屉原理的表述。
第二抽屉原理把（mn－1)个物体放入n个抽屉中，其中必有一个抽屉中至多有（m-1）个物体(例如，将3×5-1=14个物体放入5个抽屉中,则必定有一个抽屉中的物体数少于等于3-1=2).运用抽屉原理的核心是分析清楚问题中,哪个是物件,哪个是抽屉。
例如，属相是有12个，那么任意37个人中，有几个人属相相同呢？这时将属相看成12个抽屉，则一个抽屉中有 37/12，即3余1，余数不考虑，而向上考虑取整数，所以这里是3+1=4个人，(但这里需要注意的是,前面的余数1和这里加上的1是不一样的.）比如:由于一年最多有366天，因此在367人中至少有2人出生在同月同日.这相当于把367个东西放入 366个抽屉，至少有2个东西在同一抽屉里。
例1一个布袋中有40块相同的木块,其中编上号码1，2，3，4的各有10块。
问：一次至少要取出多少木块，才能保证其中至少有3块号码相同的木块？分析与解：将1，2，3，4四种号码看成4个抽屉。
要保证有一个抽屉中至少有3件物品，根据抽屉原理2，至少要有4×2＋1=9（件)物品。
所以一次至少要取出9块木块，才能保证其中有3块号码相同的木块.例2在任意的四个自然数中，是否其中必有两个数，它们的差能被3整除?分析与解：因为任何整数除以3，其余数只可能是0，1,2三种情形。
组合数学中的抽屉原理及其应用1. 什么是抽屉原理？组合数学中的抽屉原理，也被称为鸽巢原理，是一种基本的数学原理。
抽屉原理的核心思想是将多个对象放入有限数量的容器中，那么必然会有至少一个容器中拥有多个对象。
这个理论来源于我们日常生活中的一种常识：如果我们有5只袜子要放入4个抽屉中，那么必然会有至少一个抽屉中有两只袜子。
2. 抽屉原理的数学表达抽屉原理可以用数学公式进行表达，即：如果有n+1个对象要放入n个容器中，那么必然会有至少一个容器中有至少两个对象。
这个公式可以形式化表示为：如果 n+1 个物体要放入 n 个容器中，那么至少有一个容器包含≥2 个物体。
3. 抽屉原理的应用举例抽屉原理在组合数学中有着广泛的应用。
下面我们将介绍几个常见的应用场景。
3.1. 生日问题生日问题是抽屉原理的一个典型应用。
假设有一个房间里有k个人，那么至少有两个人的生日是相同的。
这个问题可以用抽屉原理进行解释。
我们可以将每个人的生日看作一个对象，将一年中的天数看作容器。
当k个人的生日超过365天时，根据抽屉原理，至少会有两个人的生日在同一天。
3.2. 图论中的应用在图论中，抽屉原理被广泛应用于证明和解决各种问题。
例如，对于一个具有n个节点的完全图，至少有一个节点的度数大于等于n/2。
这个问题可以用抽屉原理进行解释。
我们可以将每个节点看作一个对象，将每个节点的邻居节点看作容器。
根据抽屉原理，至少有一个节点的度数大于等于平均度数。
3.3. 密码学中的应用抽屉原理在密码学中也有着重要的应用。
例如，在哈希函数中，如果将无限多个输入映射到有限的输出空间中，那么必然会有两个不同的输入映射到同一个输出。
这个问题可以用抽屉原理进行解释。
我们可以将每个输入看作一个对象，将输出空间看作容器。
根据抽屉原理，当输入的数量超过输出空间的大小时，必然会有两个不同的输入映射到同一个输出。
4. 结论抽屉原理是组合数学中的一种基本原理，在各个领域都有广泛的应用。
抽屉原理讲义什么是抽屉原理？在数学领域中，抽屉原理是一种简单而常用的证明方法。
其核心思想是，如果将 n+1 个物品放到 n 个桶中，那么至少有一个桶中必定包含两个及以上的物品。
这个原理在组合数学、计算机科学等诸多领域都有广泛应用。
具体而言，抽屉原理包括两个基本概念：抽屉和物品。
如果将 n 个物品放到 m 个抽屉中，如果 n > m，那么至少有一个抽屉中会有两个或两个以上的物品。
抽屉原理的证明对于抽屉原理的证明，有一种简单而直观的方法。
我们可以将 n+1 个物品任意分成 m 组，其中 m = n。
假设每一组最多只有一个物品，那么总共只能分成 n 组。
由于有 n+1 个物品，所以至少有一组中包含了两个物品。
因此，根据这个假设的前提，我们可以得到一个矛盾，即最多只能将 n+1 个物品分成 n 组，每组最多只有一个物品，但又至少有两个物品在同一组中。
因此，假设不成立，抽屉原理成立。
抽屉原理应用抽屉原理有很多应用，下面我们介绍其中的两个例子。
例子1：生日悖论假设我们有一个房间里有 23 个人，那么至少有两个人生日相同的概率有多大呢？根据抽屉原理，我们将每个人的生日看做一个物品，日期看做一个抽屉，因为一年中只有 365 天，所以只有 365 个抽屉，但有 23 个生日需要放到这些抽屉中。
根据计算可知，概率公式为 P = 1 –(365 * 364 * 363 …… (365-22)) / (365 ^ 23) ≈ 0.5因此，当有 23 个人在同一个房间中时，至少有两个人生日相同的概率几乎是50%。
例子2：计算机算法在计算机算法中，抽屉原理有广泛应用。
其中一个例子是哈希表。
哈希表是一种高效的数据结构，它基于抽屉原理，使用哈希函数将每个数据项映射到不同的桶中。
在哈希表中，桶的数量通常比数据项的数量多，因此会有多个数据项映射到同一个桶中。
例如，如果我们在一个大小为 10 的哈希表中存储 11 个数据项，其中有两个数据项会映射到同一个桶中。
第五章 抽屉原理和Ramsey 理论抽屉原理又称鸽巢原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用较广的数学原理。
其道理并无深奥之处，且正确性也很明显。
但若能灵活运用，便可能得到一些意料不到的结果。
抽屉原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。
1930年英国逻辑学家F. P. Ramsey 将这个简单原理作了深刻推广，即Ramsey 定理，也被称为广义抽屉原理。
它是一个重要的组合定理，有许多应用。
5.1 抽屉原理（一）基本形式定理5.1.1 （基本形式）将n ＋1个物品放入n 个抽屉，则至少有一个抽屉中的物品数不少于两个。
证 反证之。
将抽屉编号为：1,2, …,n ，设第i 个抽屉放有i q 个物品，则 121+=+++n q q q n但若定理结论不成立，即1≤iq ，即有n q q q +++ 21≤n ，从而有 n q q q n n ≤+++=+ 211矛盾。
例 5.1.1 一年365天，今有366人，那么，其中至少有两人在同一天过生日。
注：与概率的区别：抽屉原理讲的是所给出的结论是必然成立的，即100%成立。
而概率反映的是不确定性现象发生的可能性问题，不讨论100%成立的确定性概率问题。
生日悖论：随机选出n 个人，则其中至少有二人同一天出生的概率为()A P n =n n P 3651365-特例：()A P 23=50.73%，()A P 100=99.99997%例 5.1.2 箱子中放有10双手套，从中随意取出11只，则至少有两只是完整配对的。
（二）推广形式定理5.1.2 （推广形式）将121+-+++n q q q n 个物品放入n 个抽屉，则下列事件至少有一个成立：即第i 个抽屉的物品数不少于i q 个。
（证）反证。
不然，设第i 个抽屉的物品数小于i q （i ＝1,2, …,n ）(即该抽屉最多有1-i q 个物品)，则有11+-∑=n q n i i ＝物品总数≤()n q q ni i n i i -=-∑∑==111与假设矛盾。
121+-+++n q q q n =()()()111121+-++-+-n q q q（三）特例 推论1 将n(r －1)＋1个物品放入n 个抽屉，则至少有一个抽屉中物品个数不少于r 个。
推论2 将m 个物品放入n 个抽屉，则至少有一个抽屉中物品个数不少于11+⎥⎦⎥⎢⎣⎢-n m ＝⎥⎥⎤⎢⎢⎡n m 个。
其中⎣⎦x 表示取x的整数部分，⎡⎤x 表示不小于x 的最小整数。
推论3 若n 个正整数()n i q i ,2,1=满足121->+++r n q q q n则至少存在一个i q ，满足r q i ≥。
（四）例例 5.1.3 有 n 位代表参加会议，若每位代表至少认识另外一个代表，则会议上至少有两人认识的人数相同。
(证) 设某代表认识的人数为k 个，则{}1,,2,1-∈n k （视为n －1个抽屉）。
而会议上有n 个代表，故每位代表认识的人数共为n 个数（视为n 个物品）。
那么，由基本定理，结论成立。
例 5.1.4 任意一群人中，必有两人有相同数目的朋友。
(证) 设有n 个人()2≥n ，分三种情形讨论：(1) 每人都有朋友，由例5.1.3即知结论成立；(2) 只有一人无朋友，余下的n －1人都有朋友，由(1)知此n －1人中必有两人有相同数目的朋友；(3) 有两人或两人以上的人无朋友，则朋友数为零的人已经有两个了，同样满足条件。
例 5.1.5 边长为2的正方形内有5个点，其中至少有两点，距离不超过2。
(证) 首先制造抽屉：将原正方形各对边中点相连，构成4个边长为1的小正方形（见图5.1.1(a)），视为抽屉。
其次，由基本原理，至少有一个小正方形里点数不少于2。
最后，从几何角度可以看出，同一小正方形内的两点的距离不超过小正方形的对角线之长度2，证毕。
图5.1.1 抽屉的选择注意，如果抽屉选择不当，可能于事无益。
如图5.1.1(b)，将正方形分为4个直角边长为2的等腰直角三角形是达不到目的的。
习题1、25.2 应用§5.2.1 抽屉原理的应用例 5.2.1 任意三个整数，必有两个之和为偶数（其差也为偶数）。
(证) 制造两个抽屉：“奇数”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数，由整数求和的奇、偶性质即知此二数之和必为偶数。
同理可知，二者之差也为偶数。
例 5.2.2 从1,2,…,2n 中任取n ＋1个数，其中至少有一对数，一个是另一个的倍数。
（证）设所取的n ＋1个数为a 1,a 2, …,a n+1，并（1）表示 ()02≥=i i i r a i αα，i ＝1,2, …,n ＋1且r i 为奇数。
（2）设置抽屉与物品：1~2n 之间只有n 个奇数（抽屉），故由抽屉原理知此n ＋1个r i 中至少有两个是相同的。
设为 r j ＝ r k ＝r ，即r r a j j j j αα22==，r r a k k k k αα22==，显然有：要么k j a a ，要么j k a a 。
（3）说明：这里已是最好的“可能结果”，即针对各种条件，稍加放松，则结论不一定成立。
● 改为取n 个数，只要取n ＋1,n ＋2, …,2n 这n 个数，显然不满足结论。
● 改为在1,2,…,2n+1中选n ＋1个数，则结论也不一定成立。
例如n=5，选6，7，8，9，10，11例 5.2.3 设a 1,a 2, …,a m 为任意m 个正整数，则其中必存在若干个相继的数，其和是m 的倍数。
即至少存在正整数j 和k(1≤j ＜k ≤m)，使得m 能整除∑=kji i a =k j j a a a ++++ 1。
(证) 构造数列 ∑==ij j i a s 1=i a a a +++ 21 ，则s 1<s 2<…<s m令 i i s r ≡ mod m ，则0≤r i ＜m （i ＝1,2,…,m ）若有某 k r ＝0，则k s m ，问题得证。
否则，所有i r ≠0，由抽屉原理知，至少存在j<k ，使j r ＝k r ，即k j s s ≡ modm ，从而有∑+==-kj i i j k a s s m 1。
本题构造“抽屉”与“物品”的技巧在于并不直接针对正整数a i ，而是构造出适合利用抽屉原理的n 个数r i 。
为了构造r i ，间接利用了s i 以达到目的。
其中的抽屉是取关于模m 的剩余类：0,1, …,m －1，并且在应用抽屉原理时分为两步走。
第一步先将r i 分为两大类，即0与非0（或看作两个大抽屉）；第二步，针对非0情形，分为m －1种情况（或看作m －1个小抽屉）。
例 5.2.4 设正整数序列a 1,a 2,…,a 25满足a i+1＋ a i+2＋…＋ a i+5≤6，i ＝0,1,…20。
试证明至少存在正整数j 、k （1≤j ＜k ≤25），使得a j ＋a j+1＋…＋a k ＝19。
(证) 构造序列 ∑==ij j i a s 1=i a a a +++ 21 ，则s 1<s 2<…<s 25≤30。
若有某个s k ＝19，那么，问题得证（j ＝1）。
否则，所有s i ≠19。
令集合A ＝{ s 1，s 2，…，s 25，s 1＋19，s 2＋19，…，s 25＋19} 且有 20≤s 1＋19＜s 2＋19＜…＜s 25＋19≤49。
集合A 中共有50个数，每个数的取值在1到49之间，由抽屉原理，其中必有两数相同。
又知i ≠j 时，s i ≠s j ，从而 s i ＋19≠s j ＋19 。
所以，相等的两项必为 s k ＝ s j ＋19（显然k>j ）， 即∑+==-=kj i i j k a s s 119=k j j a a a +++++ 21 ，证毕。
问题一般化：设正整数序列a 1,a 2,…,a mn 满足a i+1＋ a i+2＋…＋ a i+n ≤p ，i ＝0,1,…,n(m －1)。
若要求存在正整数j<k ，使得a j ＋ a j+1＋…＋ a k ＝q ，试推出m 、n 、p 、q 应满足的关系。
分析：令 s i ＝a 1＋a 2＋…＋a i ， i ＝0,1,…,nm设 A ＝{ s 1，s 2，…, s mn ，s 1＋q ，s 2＋q , …，s mn ＋q } 且有 1≤s 1< s 2< …< s mn ， q< s 1＋q< s 2＋q <…<s mn ＋q ≤mp ＋q要用抽屉原理，A 中元素个数必须大于A 中最大数s mn ＋q ，即mp ＋q<2mn ，或12-≤+mn q mp ，由此得结论：q ≤m(2n －p)－1 。
本例中，m ＝n ＝5，p ＝6，q ＝19 。
若选m ＝n ＝10，p ＝16，则q ≤39 。
变异：一学生用37天共60小时复习功课，第i 天复习a i 小时（a i 为正整数），则无论如何安排，总存在相继若干天，这些天的复习时数之和恰为13 。
此问题实际上隐含着m ＝1，n ＝37，p ＝60，q ＝13 。
这时，问题可以描述为：m 个正整数a 1,a 2,…,a m 满足a 1＋a 2＋…＋a m ＝n ，要存在m k j 1≤<≤，使得a j ＋ a j+1＋…＋ a k ＝q ，必须有q ≤2m －n －1（这只要在一般问题中取m ＝1，n ＝m ，p ＝n 即可）。
例 5.2.5 将65个正整数1,2, …,65随意分为4组，那么，至少有一组，该组中最少存在一个数，是同组中某两数之和或另一数的两倍。
(证) 用反证法。
设任何一组数中的每一个数，它既不等于同组中另外两数之和，也不等于同组中另一数的两倍。
即任何一组数中的的任意两个数之差总不在这个组中。
由抽屉原理，四组中至少有一组（称为A 组），其中至少有17个数。
从中取17个：记为a 1,a 2,…,a 17，不妨设a 17最大。
令()i i a a a -=171， i ＝1,2, …,16显然()6511<≤i a 。
由假设知()A a i ∉1（否则，就有某个a k 和a k 满足a 17=a k +a j ），所以，该16个数必在另外三组B 、C 、D 中。
再由抽屉原理知，B 、C 、D 三组中至少有一组（设为B 组），至少含有6个()1i a 。
只取其中6个，记为b 1,b 2,…,b 6，同理可设b 6最大，并令()i i b b b -=61（i ＝1,2,…,5）。
同样有 ()6511<≤i b 且()B b i∉1。
