《组合数学》 第五章 抽屉原理和Ramsey理论
第五章 抽屉原理和Ramsey理论
抽屉原理又称鸽巢原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用较广的数学原理。其道理并无深奥之处，且正确性也很明显。但若能灵活运用，便可能得到一些意料不到的结果。
抽屉原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。
1930年英国逻辑学家F. P. Ramsey将这个简单原理作了深刻推广，即Ramsey定理，也被称为广义抽屉原理。它是一个重要的组合定理，有许多应用。
5.1 抽屉原理
（一）基本形式
定理5.1.1 （基本形式）将n＋1个物品放入n个抽屉，则至少有一个抽屉中的物品数不少于两个。
证 反证之。将抽屉编号为：1,2, ?,n，设第i个抽屉放有qi个物品，则 q1?q2???qn?n?1 但若定理结论不成立，即qi从而有
?1，即有q1?q2???qn≤n，
n?1?q1?q2???qn?n
矛盾。
例 5.1.1 一年365天，今有366人，那么，其中至少有两人在同一天过生日。
注：与概率的区别：抽屉原理讲的是所给出的结论是必然成立的，即100%成立。而概率反映的是不确定性现象发
1/37
《组合数学》 第五章 抽屉原理和Ramsey理论
生的可能性问题，不讨论100%成立的确定性概率问题。 生日悖论：随机选出n个人，则其中至少有二人同一天出生的概率为
Pn?A?=1?P365365nn
特例：P23?A?=50.73%，P100?A?=99.99997%
例 5.1.2 箱子中放有10双手套，从中随意取出11只，则至少有两只是完整配对的。
（二）推广形式
定理5.1.2 （推广形式）将q1?q2???qn?n?1个物品放入n个抽屉，则下列事件至少有一个成立：即第i个抽屉的物品数不少于qi个。
（证）反证。不然，设第i个抽屉的物品数小于qi（i＝1,2, ?,n）(即该抽屉最多有qi?1个物品)，则有
?qi?n?1＝物品总数≤??qi?1???qi?n
i?1i?1i?1nnn与假设矛盾。
q1?q2???qn?n?1=
?q1（三）特例
?1???q2?1?????qn?1??1
推论1 将n(r－1)＋1个物品放入n个抽屉，则至少有一个抽屉中物品个数不少于r个。
推论2 将m个物品放入n个抽屉，则至少有一个抽屉中物品个数不少于??m?1??m＝?1??n??n?2/37
?其中?x?表示取x?个。?《组合数学》 第五章 抽屉原理和Ramsey理论
的整数部分，?x?表示不小于x的最小整数。
推论3 若n个正整数qi?i?1,2,?n?满足
q1?q2???qnn?r?1
则至少存在一个qi，满足qi?r。
（四）例
例 5.1.3 有 n位代表参加会议，若每位代表至少认识另外一个代表，则会议上至少有两人认识的人数相同。 (证) 设某代表认识的人数为k个，则k??1,2,?,n?1?（视为n－1个抽屉）。而会议上有n个代表，故每位代表认识的人数共为n个数（视为n个物品）。那么，由基本定理，结论成立。
例 5.1.4 任意一群人中，必有两人有相同数目的朋友。 (证) 设有n个人?n?2?，分三种情形讨论： (1) 每人都有朋友，由例5.1.3即知结论成立； (2) 只有一人无朋友，余下的n－1人都有朋友，由(1)知此n－1人中必有两人有相同数目的朋友；
(3) 有两人或两人以上的人无朋友，则朋友数为零的人已经有两个了，同样满足条件。
例 5.1.5 边长为2的正方形内有5个点，其中至少有两点，距离不超过2。
(证) 首先制造抽屉：将原正方形各对边中点相连，构成4个边长为1的小正方形（见图5.1.1(a)），视为抽屉。其次，
3/37
《组合数学》 第五章 抽屉原理和Ramsey理论
由基本原理，至少有一个小正方形里点数不少于2。最后，从几何角度可以看出，同一小正方形内的两点的距离不超过小正方形的对角线之长度2，证毕。
* * *
*
* * * * * * 图5.1.1 抽屉的选择
注意，如果抽屉选择不当，可能于事无益。如图5.1.1(b)，将正方形分为4个直角边长为2的等腰直角三角形是达不到目的的。
习题1、2
5.2 应用
§5.2.1 抽屉原理的应用
例 5.2.1 任意三个整数，必有两个之和为偶数（其差也为偶数）。 (证) 制造两个抽屉：“奇数”和“偶数”，3个数放入两个抽屉，必有一个抽屉中至少有两个数，由整数求和的奇、偶性质即知此二数之和必为偶数。 同理可知，二者之差也为偶数。
任给3个整数，其中必存在两个整数，其和能被2整除。提另法一证明．记这3数为a1,a2,a3，令ri?ai mod 2 4/37
《组合数学》 第五章 抽屉原理和Ramsey理论
则ri=0，1（i=1，2，3）。 以0，1为两个抽屉，3个ai为物品，以ri决定将ai放入哪个抽屉。 由抽屉原理，某个抽屉中至少有两个ai，其除以2的余数相同。那么，此2数即满足要求。 问题：任给n个整数，其中必存在3个整数，其和能被3整除。问n最小应为多少？ 常规思路：n=7（证明思路同上） 但7不是最少数字，最小的n=5。 证明．记这5个数为a1,3 a2,?,令ri?ai mod a5，扩展则ri=0，1，2（i=1，2，?，5）。那么（构造抽屉和物品的方法同上） ① 若有某3个ri相同，则对应的3个ai满足条件。 ② 否则，5个ri中最多有2个ri相同（即每个抽屉中最多放2个物品），此时，每个抽屉不空。那么，从每个抽屉选一整数，该3个数即满足条件。 任给n个整数，其中必存在k个整数，其和能被k整除。问n最小应为多少？ 一般提例如：k=2 时，n=3； 法 k=3 时，n=5（而非7）； k=4 时，n=7（而非13）； ① 一维数轴上有3个整数点（坐标为整数的点），则几何角其中必存在两个点xi和xj，其几何中心度(便于?xi?xj?2也是一个整点。 推广到多维空 间) ② 一维数轴上有5个整数点，则其中必存在3个点5/37