《组合数学讲义及答案 5章 抽屉原理》由会员分享，可在线阅读，更多相关《组合数学讲义及答案 5章 抽屉原理（38页珍藏版）》请在金锄头文库上搜索。
1、组合数学 第五章 抽屉原理和 Ramsey 理论 1/38 第五章第五章 抽 屉 原 理 和抽 屉 原 理 和 Ramsey 理 论理 论 概述概述：抽屉原理又称鸽巢原理或重叠原理，是组合数学抽屉原理又称鸽巢原理或重叠原理，是组合数学 中两大基本原理之一，是一个极其初等而又应用较广的数中两大基本原理之一，是一个极其初等而又应用较广的数 学原理。其道理并无深奥之处，且正确性也很明显。但若学原理。其道理并无深奥之处，且正确性也很明显。但若 能灵活运用，便可能得到一些意料不到的结果。能灵活运用，便可能得到一些意料不到的结果。 解决的问题解决的问题：存在性问题，即在具体的组合问题中，要存在性问题，即在
2、具体的组合问题中，要 计算某些特定问题求解的方案数，其前提就是要知道这些计算某些特定问题求解的方案数，其前提就是要知道这些 方案的存在性。方案的存在性。 广义抽屉原理广义抽屉原理： 1930 年英国逻辑学家年英国逻辑学家 F. P. Ramsey 将将 这个简单原理作了深刻推广，即这个简单原理作了深刻推广，即 Ramsey 定理，也被称为广定理，也被称为广 义抽屉原理。它是一个重要的组合定理，有许多应用。义抽屉原理。它是一个重要的组合定理，有许多应用。 5.1 抽 屉 原 理抽 屉 原 理 （一）（一）基本形式基本形式 【定理【定理5.1.15.1.1】 （基本形式基本形式）将）将 n1 个物
3、品放入个物品放入 n 个个 抽屉，则至少有一个抽屉中的物品数不少于两个。抽屉，则至少有一个抽屉中的物品数不少于两个。 证证 反证之。将抽屉编号为：反证之。将抽屉编号为：1,2, ,n，设第，设第 i 个抽屉放个抽屉放 有有 i q个物品，则个物品，则 1 21 nqqq n 但若定理结论不成立，即但若定理结论不成立，即1 i q，即有，即有 n qqq 21 n， 从而有从而有 nqqqn n 21 1 矛盾。矛盾。 【例【例 5.1.15.1.1】 一年一年 365 天，今有天，今有 366 人，那么，其中至人，那么，其中至 少有两人在同一天过生少有两人在同一天过生日。日。 与概率的区别与概
4、率的区别：抽屉原抽屉原理讲的是所给出的结论是必然成理讲的是所给出的结论是必然成 立的，即立的，即 100%成立。而概率反映的成立。而概率反映的是不确定性现象发生的是不确定性现象发生的 组合数学 第五章 抽屉原理和 Ramsey 理论 2/38 可能性问题，不讨论可能性问题，不讨论 100%成立的确定性成立的确定性概率问题。概率问题。 生日悖论生日悖论：随机选出随机选出 n 个人，则其中至少有二人同一天个人，则其中至少有二人同一天 出生的概率为出生的概率为 APn nn P3651 365 例如例如 AP2350.73%， AP10099.99997% 几何领域的几何领域的另一著名悖论：另一著名
5、悖论： 【例【例 5.1.25.1.2】 箱子中放有箱子中放有 10 双手套，从中随意取双手套，从中随意取出出 11 只，则至少有两只是完整配对的。只，则至少有两只是完整配对的。 （二）（二）推广形式推广形式 【定理【定理5.1.25.1.2】 （推广形式）将（推广形式）将 1 21 nqqq n 个物品放入个物品放入 n 个抽屉，则下列事个抽屉，则下列事 件至少有一个成立：即第件至少有一个成立：即第 i 个抽屉的物品数不少于个抽屉的物品数不少于 i q个。个。 （证）（证）反证。不然，设第反证。不然，设第 i 个抽屉的物品数小于个抽屉的物品数小于 i q（i 1,2, ,n）(即该抽屉最多有
6、即该抽屉最多有1 i q个物品个物品)，则有，则有 1 1 nq n i i 物品总数物品总数 nqq n i i n i i 11 1 与假设矛盾。与假设矛盾。 1 21 nqqq n 1111 21 n qqq （三）（三）特例特例 【推论推论 1】 将将 n(r1)1 个物品放入个物品放入 n 个抽屉， 则至少个抽屉， 则至少 组合数学 第五章 抽屉原理和 Ramsey 理论 3/38 有一个抽屉中物品个数不少于有一个抽屉中物品个数不少于 r 个。个。 【推论推论 2】 将将 m 个物品放入个物品放入 n 个抽屉，则至少有一个个抽屉，则至少有一个 抽屉中物品个数不少于抽屉中物品个数不少于
7、1 1 n m n m 个。其中个。其中 x表表 示取示取 x 的整数部分，的整数部分， x表示不表示不小于小于 x 的最小整数。的最小整数。 【推论推论 3】 若若 n 个正整数个正整数 niqi, 2 , 1 满足满足 1 21 r n qqq n 则至少存在一个则至少存在一个 i q，满足，满足rqi 。 （四）（四）例例 【例【例 5.1.35.1.3】 有有 n 位代表参加会议， 若每位代表至少认位代表参加会议， 若每位代表至少认 识另外一个代表，则会议上至少有两人认识的人数相同。识另外一个代表，则会议上至少有两人认识的人数相同。 (证证) 设某代表认识的人数为设某代表认识的人数为
8、k 个，则个，则 1, 2 , 1 nk （视为（视为 n1 个抽屉） 。而会议上有个抽屉） 。而会议上有 n 个代表，故每位代表个代表，故每位代表 认识的人数共为认识的人数共为 n 个数（个数（视为视为 n 个物品） 。那么，由基本定个物品） 。那么，由基本定 理，结论成立。理，结论成立。 【例【例 5.1.45.1.4】 任意一群人中，必有两人有相同数目的朋任意一群人中，必有两人有相同数目的朋 友。友。 (证证) 设有设有 n 个人个人 2 n，分三种情形讨论：，分三种情形讨论： (1) 每人都有朋友，由例每人都有朋友，由例 5.1.3 即知结论成立；即知结论成立； (2) 只有一人无朋友
9、，余下的只有一人无朋友，余下的 n1 人都有朋友，由人都有朋友，由(1) 知此知此 n1 人中必有两人有相同数目的朋友；人中必有两人有相同数目的朋友； (3) 有两人或两人以上的人无朋友，则朋友数为零的人有两人或两人以上的人无朋友，则朋友数为零的人 已经有两个了，同样满足条件。已经有两个了，同样满足条件。 组合数学 第五章 抽屉原理和 Ramsey 理论 4/38 【例【例 5.1.55.1.5】 边长为边长为 2 的正方形内有的正方形内有 5 个点，其中至少个点，其中至少 有两点，距离不超过有两点，距离不超过2。 (证证) 首先制造抽屉：将原正方形各对边中点相连，构成首先制造抽屉：将原正方形
10、各对边中点相连，构成 4 个边长为个边长为 1 的小正方形 （见图的小正方形 （见图 5.1.1(a)） ， 视为抽屉。 其次，） ， 视为抽屉。 其次， 由基本原理，至少有一个小正方形里点数不少于由基本原理，至少有一个小正方形里点数不少于 2。最后，。最后， 从几何角度可以看出，同一小正方形内的两点的距离不超从几何角度可以看出，同一小正方形内的两点的距离不超 过小正方形的对角线之长度过小正方形的对角线之长度2，证毕。，证毕。 图图 5.1.1 抽屉的选择抽屉的选择 注意注意：如果抽屉选择不当，可能于事无益。如果抽屉选择不当，可能于事无益。 习题习题 1、2 5.2 应 用应 用 5.2.1
11、抽 屉 原 理 的 应 用抽 屉 原 理 的 应 用 例例 5.2.15.2.1 任意三个整数，必有两个之和为偶数（其差任意三个整数，必有两个之和为偶数（其差 也为偶数） 。也为偶数） 。 (证证) 制造两个抽屉： “奇数”和“偶数” ，制造两个抽屉： “奇数”和“偶数” ，3 个数放入个数放入两两 个抽屉，必有一个抽屉中至少有两个数，由整数求和的奇、个抽屉，必有一个抽屉中至少有两个数，由整数求和的奇、 偶性质即知此二数之和必为偶数。偶性质即知此二数之和必为偶数。 同理可知，二者之差也为偶数。同理可知，二者之差也为偶数。 组合数学 第五章 抽屉原理和 Ramsey 理论 5/38 另 一 提
12、法 另 一 提 法 任给任给 3 个整数，其中必存在两个整数，其和能被个整数，其中必存在两个整数，其和能被 2 整除。整除。 证明记证明记这这 3 数为数为 321 ,aaa，令，令 ii ar mod 2 则则 i r0，1（i1，2，3） 。） 。 以以 0，1 为两个抽屉为两个抽屉，3 个个 i a为物品，以为物品，以 i r决定将决定将 i a放放 入哪个抽屉。入哪个抽屉。 由抽屉原理，某个抽屉中至少有两个由抽屉原理，某个抽屉中至少有两个 i a，其除以，其除以 2 的的 余数相同。那么，此余数相同。那么，此 2 数即满足要求。数即满足要求。 扩扩 展展 问题：任给问题：任给 n 个整
13、数，其中必存在个整数，其中必存在 3 个整数，其和能个整数，其和能 被被 3 整除。问整除。问 n 最小应为多少？最小应为多少？ 常规思路：常规思路：n7（证明思路同上）（证明思路同上） 但但 7 不是最少数字，最小的不是最少数字，最小的 n5。 证明 记这证明 记这 5 个个数为数为 521 ,aaa， 令， 令 ii ar mod 3 则则 i r0，1，2（i1，2，5） 。那么（构造抽屉） 。那么（构造抽屉 和物品的方法同上）和物品的方法同上） 若有某若有某 3 个个 i r相同，则对应的相同，则对应的 3 个个 i a满足条件。满足条件。 否则，否则，5 个个 i r中最多有中最多有
14、 2 个个 i r相同（即每个抽屉中相同（即每个抽屉中 最多放最多放 2 个物品） ，此时，每个抽屉不空。那么，个物品） ，此时，每个抽屉不空。那么， 从每个抽屉选一整数，该从每个抽屉选一整数，该 3 个数即满足条件。个数即满足条件。 一般提一般提 法法 任任给给 n 个整数，其中必存在个整数，其中必存在 k 个整数，其和能被个整数，其和能被 k 整除。问整除。问 n 最小应为多少？最小应为多少？ 例如：例如：k2 时，时，n3； k3 时，时，n5（而非（而非 7） ；） ； k4 时，时，n7（而非（而非 13） ；） ； 几何角几何角 度度(便于便于 推广到推广到 多维空多维空 一维数轴上有一维数轴上有 3 个整数点（坐标为整数的点） ，则个整数点（坐标为整数的点） ，则 其 中 必 存 在 两 个 点其 中 必 存 在 两 个 点 i x和和 j x， 其 几 何 中 心， 其 几 何 中 心 2 ji xx 也是一个整点。也是一个整点。 组合数学 第五章 抽屉原理和 Ramsey 理论 6/38 间间) 一维数一维数轴上有轴上有 5 个整数点，则其中必存在个整数点，则其中必存在 3 个点个点 i x、 j x和和 k x，其几何中心，其几何中心
