CH7组合数学.pdf

组合数学 供 09 10 第一学期之用 刘 西 奎 Email liuxikui 山东科技大学 信息科学与工程学院 2010 年 9 月 17 日 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日1 39 1鸽笼原理的简单形式 2鸽笼原理的加强形式 3Ramsey 定理 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日2 39 说明 先前 为了上课方便 本人制作了讲义 并经由同学复印 然而导致了大量 的盗版 直接影响了将来本讲义的出版 不得不考虑到版权的问题 因为制作这 样一份文档实在是花费了大量的时间精力 制作本课件纯粹为了上课方便 请 不要随意传播和上传互联网 本幻灯片使用 beamer 宏包作出 关于 beamer 的讨论 安装 更新 可参考 http bbs ctex org forums index php showtopic 27695 本文的图形主要是用 pgf 宏包作出的 另有个别的 MetaPost 图形 本幻灯片的源文件仅供学习 beamer pgf 参考之用 使用请注明出处 Copyrightc 2008 保留所有权利 LIU XI KUI 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日2 39 说明 先前 为了上课方便 本人制作了讲义 并经由同学复印 然而导致了大量 的盗版 直接影响了将来本讲义的出版 不得不考虑到版权的问题 因为制作这 样一份文档实在是花费了大量的时间精力 制作本课件纯粹为了上课方便 请 不要随意传播和上传互联网 本幻灯片使用 beamer 宏包作出 关于 beamer 的讨论 安装 更新 可参考 http bbs ctex org forums index php showtopic 27695 本文的图形主要是用 pgf 宏包作出的 另有个别的 MetaPost 图形 本幻灯片的源文件仅供学习 beamer pgf 参考之用 使用请注明出处 Copyrightc 2008 保留所有权利 LIU XI KUI 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日2 39 Ramsey 定理 鸽笼原理为其最简形式 偏序集分解定理 Dilworth 定 理 相异代表系存在定理 Hall 定理 是组合学三大存在性定理之一 有广泛 的应用 鸽笼原理是组合学中最简单 最基本原理也叫抽屉原理 狄利克雷原 理 Dirichlet 1805 1859 19 世纪德国数学家 或重叠原理 鸽笼原理是一个极其 初等而又应用较广的数学原理 要解决的是存在性问题 即在具体的组合问题 中 要计算某些特定问题求解的方案数 其前提就是要知道这些方案的存在性 鸽巢原理又称抽屉原理或鞋盒原理 这个原理最早是由 Dirichlet 提出的 鸽巢原理是解决组合论中一些存在性问题的基本而又有力的工具 它是组合数 学中最简单也是最基本的原理之一 从这个原理出发 可以导出许多有趣结果 而这些结果常常是令人惊奇的 Ramsey 理论它对组合数学发展产生过重要的影响 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日3 39 Ramsey 定理 鸽笼原理为其最简形式 偏序集分解定理 Dilworth 定 理 相异代表系存在定理 Hall 定理 是组合学三大存在性定理之一 有广泛 的应用 鸽笼原理是组合学中最简单 最基本原理也叫抽屉原理 狄利克雷原 理 Dirichlet 1805 1859 19 世纪德国数学家 或重叠原理 鸽笼原理是一个极其 初等而又应用较广的数学原理 要解决的是存在性问题 即在具体的组合问题 中 要计算某些特定问题求解的方案数 其前提就是要知道这些方案的存在性 鸽巢原理又称抽屉原理或鞋盒原理 这个原理最早是由 Dirichlet 提出的 鸽巢原理是解决组合论中一些存在性问题的基本而又有力的工具 它是组合数 学中最简单也是最基本的原理之一 从这个原理出发 可以导出许多有趣结果 而这些结果常常是令人惊奇的 Ramsey 理论它对组合数学发展产生过重要的影响 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日3 39 1928 年 年仅 24 岁的英国杰出数学家 Ramsey 发表了著名论文 论形式 逻辑中的一个问题 他在这篇论文中 提出并证明了关于集合论的一个重大研 究成果 现称为 Ramsey 定理 尽管两年后他不幸去世 但是他开拓的这一新领域至今仍十分活跃 而且 近年来在科技领域获得了成功的应用 本讲主要介绍鸽巢原理 Ramsey 数及性质 Ramsey 定理及应用 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日4 39 1928 年 年仅 24 岁的英国杰出数学家 Ramsey 发表了著名论文 论形式 逻辑中的一个问题 他在这篇论文中 提出并证明了关于集合论的一个重大研 究成果 现称为 Ramsey 定理 尽管两年后他不幸去世 但是他开拓的这一新领域至今仍十分活跃 而且 近年来在科技领域获得了成功的应用 本讲主要介绍鸽巢原理 Ramsey 数及性质 Ramsey 定理及应用 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日4 39 1鸽笼原理的简单形式 2鸽笼原理的加强形式 3Ramsey 定理 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日5 39 定理 1 1 如果把 1 个物品放入 个盒子中 那么至少有一个盒子中有两个或更多的 物品 证证证明明明 反证法 如果每个盒子中至多有一个物品 那么 个盒子中至多有 个物品 而我 们共有 1 个物品 矛盾 故定理成立 鸽笼原理只断言存在一个盒子 该盒中有两个或两个以上的物品 但它并 没有指出是哪个盒子 所以 这个原理只能用来证明某种安排的存在性 而对于 找出这种安排却毫无帮助 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日5 39 定理 1 1 如果把 1 个物品放入 个盒子中 那么至少有一个盒子中有两个或更多的 物品 证证证明明明 反证法 如果每个盒子中至多有一个物品 那么 个盒子中至多有 个物品 而我 们共有 1 个物品 矛盾 故定理成立 鸽笼原理只断言存在一个盒子 该盒中有两个或两个以上的物品 但它并 没有指出是哪个盒子 所以 这个原理只能用来证明某种安排的存在性 而对于 找出这种安排却毫无帮助 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日5 39 定理 1 1 如果把 1 个物品放入 个盒子中 那么至少有一个盒子中有两个或更多的 物品 证证证明明明 反证法 如果每个盒子中至多有一个物品 那么 个盒子中至多有 个物品 而我 们共有 1 个物品 矛盾 故定理成立 鸽笼原理只断言存在一个盒子 该盒中有两个或两个以上的物品 但它并 没有指出是哪个盒子 所以 这个原理只能用来证明某种安排的存在性 而对于 找出这种安排却毫无帮助 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日5 39 注注注 1 应用时要分清物体与盒子以及物体总数与盒子总数 2 定理只是存在性定理 不能找出具体的物体 3 不能被推广到只存在 个 或更少 物体的情形 例 1 1 13 人中至少有 2 人是同月出生的 13 人中至少有 2 人属相相同 367 人中至少 有 2 人的生日相同 例 1 2 设有 对夫妇 问至少要从这 2 个人中选出多少人 才能保证能够有一对夫妇 被选出 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日6 39 注注注 1 应用时要分清物体与盒子以及物体总数与盒子总数 2 定理只是存在性定理 不能找出具体的物体 3 不能被推广到只存在 个 或更少 物体的情形 例 1 1 13 人中至少有 2 人是同月出生的 13 人中至少有 2 人属相相同 367 人中至少 有 2 人的生日相同 例 1 2 设有 对夫妇 问至少要从这 2 个人中选出多少人 才能保证能够有一对夫妇 被选出 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日6 39 注注注 1 应用时要分清物体与盒子以及物体总数与盒子总数 2 定理只是存在性定理 不能找出具体的物体 3 不能被推广到只存在 个 或更少 物体的情形 例 1 1 13 人中至少有 2 人是同月出生的 13 人中至少有 2 人属相相同 367 人中至少 有 2 人的生日相同 例 1 2 设有 对夫妇 问至少要从这 2 个人中选出多少人 才能保证能够有一对夫妇 被选出 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日6 39 例 1 3 给出 个整数 1 2 证明 必存在整数 0 则 1 2 1 1 1 mod 0 mod 综合 1 2 即知题设结论成立 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日7 39 例 1 3 给出 个整数 1 2 证明 必存在整数 0 则 1 2 1 1 1 mod 0 mod 综合 1 2 即知题设结论成立 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日7 39 例 1 3 给出 个整数 1 2 证明 必存在整数 0 则 1 2 1 1 1 mod 0 mod 综合 1 2 即知题设结论成立 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日7 39 例 1 4 一个棋手有 11 周时间准备锦标赛 他决定每天至少下一盘棋 一周中下棋的次 数不能多于 12 次 证明 在此期间的连续一些天中他正好下棋 21 次 证证证明明明 1 令 1 2 77分别为这 11 周期间他每天下棋的次数 并作 部分和 1 1 2 1 2 77 1 2 77 根据题意 有 1 1 77 且 1 6 12 1 71 所以有 1 1 2 3 77 12 11 132 1 1 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日8 39 例 1 4 一个棋手有 11 周时间准备锦标赛 他决定每天至少下一盘棋 一周中下棋的次 数不能多于 12 次 证明 在此期间的连续一些天中他正好下棋 21 次 证证证明明明 1 令 1 2 77分别为这 11 周期间他每天下棋的次数 并作 部分和 1 1 2 1 2 77 1 2 77 根据题意 有 1 1 77 且 1 6 12 1 71 所以有 1 1 2 3 77 12 11 132 1 1 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日8 39 2 考虑数列 1 2 77 1 21 2 21 77 21 它们都在 1 与 132 21 153 之间 共有 154 项 3 由鸽笼原理知 其中必有两项相等 由式 1 1 知 1 2 77这 77 项互不相等 从而 1 21 2 21 77 21 这 77 项也互不相等 所以 一定存在 1 77 使得 21 因此 21 1 2 1 1 2 1 2 这说明从第 1 天到第 天这连续 天中 他刚好下了 21 盘棋 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日9 39 2 考虑数列 1 2 77 1 21 2 21 77 21 它们都在 1 与 132 21 153 之间 共有 154 项 3 由鸽笼原理知 其中必有两项相等 由式 1 1 知 1 2 77这 77 项互不相等 从而 1 21 2 21 77 21 这 77 项也互不相等 所以 一定存在 1 77 使得 21 因此 21 1 2 1 1 2 1 2 这说明从第 1 天到第 天这连续 天中 他刚好下了 21 盘棋 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日9 39 2 考虑数列 1 2 77 1 21 2 21 77 21 它们都在 1 与 132 21 153 之间 共有 154 项 3 由鸽笼原理知 其中必有两项相等 由式 1 1 知 1 2 77这 77 项互不相等 从而 1 21 2 21 77 21 这 77 项也互不相等 所以 一定存在 1 14 其中 为周数 为每周最多下棋的次数 为 连续若干天中正好下棋的次数 本题 11 12 21 定理 1 2 从 1 2 2 的正整数中任取 1 个不同的数 证明至少有一个数是另一个 数的倍数 证证证明明明 设 1 2 1是被选出的 1 个整数 对任一 都可以唯 一地写成如下的形式 2 1 2 1 其中 为整数 为奇数 例如 72 23 9 64 26 1 由于 1 2 所以 1 1 只能取 1 3 5 2 1 这 个奇数 而 1 2 1共有 1 项 由鸽笼原理知 存在 1 1 使得 不妨设 14 其中 为周数 为每周最多下棋的次数 为 连续若干天中正好下棋的次数 本题 11 12 21 定理 1 2 从 1 2 2 的正整数中任取 1 个不同的数 证明至少有一个数是另一个 数的倍数 证证证明明明 设 1 2 1是被选出的 1 个整数 对任一 都可以唯 一地写成如下的形式 2 1 2 1 其中 为整数 为奇数 例如 72 23 9 64 26 1 由于 1 2 所以 1 1 只能取 1 3 5 2 1 这 个奇数 而 1 2 1共有 1 项 由鸽笼原理知 存在 1 1 使得 不妨设 14 其中 为周数 为每周最多下棋的次数 为 连续若干天中正好下棋的次数 本题 11 12 21 定理 1 2 从 1 2 2 的正整数中任取 1 个不同的数 证明至少有一个数是另一个 数的倍数 证证证明明明 设 1 2 1是被选出的 1 个整数 对任一 都可以唯 一地写成如下的形式 2 1 2 1 其中 为整数 为奇数 例如 72 23 9 64 26 1 由于 1 2 所以 1 1 只能取 1 3 5 2 1 这 个奇数 而 1 2 1共有 1 项 由鸽笼原理知 存在 1 1 使得 不妨设 14 其中 为周数 为每周最多下棋的次数 为 连续若干天中正好下棋的次数 本题 11 12 21 定理 1 2 从 1 2 2 的正整数中任取 1 个不同的数 证明至少有一个数是另一个 数的倍数 证证证明明明 设 1 2 1是被选出的 1 个整数 对任一 都可以唯 一地写成如下的形式 2 1 2 1 其中 为整数 为奇数 例如 72 23 9 64 26 1 由于 1 2 所以 1 1 只能取 1 3 5 2 1 这 个奇数 而 1 2 1共有 1 项 由鸽笼原理知 存在 1 1 使得 不妨设 2 则有 1 1 2 1 2是 整数 因此得 1 1 2 2 1 1 这与 2 2 1是整数矛盾 把 1 2 2 分成以下 组 1 2 3 4 2 1 2 从组中任取 1 个不同的数 由鸽笼原理可知至少有两个数取自同一组 它们是相邻的数 所以它们是互素的 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日12 39 例 1 7 在 1 个小于等于 2 的不相等的正整数中 一定存在两个数是互素的 分析 任何两个相邻的正整数是互素的 证证证明明明 反证法 假设 与 1 有公因子 2 则有 1 1 2 1 2是 整数 因此得 1 1 2 2 1 1 这与 2 2 1是整数矛盾 把 1 2 2 分成以下 组 1 2 3 4 2 1 2 从组中任取 1 个不同的数 由鸽笼原理可知至少有两个数取自同一组 它们是相邻的数 所以它们是互素的 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日12 39 例 1 7 在 1 个小于等于 2 的不相等的正整数中 一定存在两个数是互素的 分析 任何两个相邻的正整数是互素的 证证证明明明 反证法 假设 与 1 有公因子 2 则有 1 1 2 1 2是 整数 因此得 1 1 2 2 1 1 这与 2 2 1是整数矛盾 把 1 2 2 分成以下 组 1 2 3 4 2 1 2 从组中任取 1 个不同的数 由鸽笼原理可知至少有两个数取自同一组 它们是相邻的数 所以它们是互素的 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日12 39 例 1 8 证明边长为 的正方形内任意 5 点 必有两点的距离不超过 2 2 证证证明明明 将原正方形各对边中点相连 构成 4 个边长为 2 的小正方形 由 基本原理 至少有一个小正方形里点数不少于 2 最后 从几何角度可以看出 同一小正方形内的两点的距离不超过小正方形的对角线之长度 2 2 思思思考考考题题题 1 在边长为 1 的等边三角形内任意放 10 个点 证明一定存在两 个点 其距离不大于 1 3 2 确定正整数 的值 使得在边长为 1 的等边三角形内任意放 个 点 其中必有两点的距离不大于 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日13 39 例 1 8 证明边长为 的正方形内任意 5 点 必有两点的距离不超过 2 2 证证证明明明 将原正方形各对边中点相连 构成 4 个边长为 2 的小正方形 由 基本原理 至少有一个小正方形里点数不少于 2 最后 从几何角度可以看出 同一小正方形内的两点的距离不超过小正方形的对角线之长度 2 2 思思思考考考题题题 1 在边长为 1 的等边三角形内任意放 10 个点 证明一定存在两 个点 其距离不大于 1 3 2 确定正整数 的值 使得在边长为 1 的等边三角形内任意放 个 点 其中必有两点的距离不大于 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日13 39 例 1 8 证明边长为 的正方形内任意 5 点 必有两点的距离不超过 2 2 证证证明明明 将原正方形各对边中点相连 构成 4 个边长为 2 的小正方形 由 基本原理 至少有一个小正方形里点数不少于 2 最后 从几何角度可以看出 同一小正方形内的两点的距离不超过小正方形的对角线之长度 2 2 思思思考考考题题题 1 在边长为 1 的等边三角形内任意放 10 个点 证明一定存在两 个点 其距离不大于 1 3 2 确定正整数 的值 使得在边长为 1 的等边三角形内任意放 个 点 其中必有两点的距离不大于 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日13 39 例 1 9 将 65 个正整数 1 2 65 随意分为 4 组 那么 至少有一组 该组中最少存在 一个数 是同组中某两个数之和或另一个数的两倍 反反反证证证法法法 设任何一组数中的每一个数 它既不等于同组中另为两个数之和 也不等于同组中另一个数的两倍 即任何一组数中任意两个数之差总不在这个 组中 由抽屉原理知 四组中至少有一组 称为 组 其中至少有 17 个数 从 中取 17 个 记为 1 2 17 不妨设 17最大 令 1 17 1 2 16 显然 1 1 65 由假设知 1 所以该 16 数必在另外三组 中 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日14 39 例 1 9 将 65 个正整数 1 2 65 随意分为 4 组 那么 至少有一组 该组中最少存在 一个数 是同组中某两个数之和或另一个数的两倍 反反反证证证法法法 设任何一组数中的每一个数 它既不等于同组中另为两个数之和 也不等于同组中另一个数的两倍 即任何一组数中任意两个数之差总不在这个 组中 由抽屉原理知 四组中至少有一组 称为 组 其中至少有 17 个数 从 中取 17 个 记为 1 2 17 不妨设 17最大 令 1 17 1 2 16 显然 1 1 65 由假设知 1 所以该 16 数必在另外三组 中 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日14 39 例 1 9 将 65 个正整数 1 2 65 随意分为 4 组 那么 至少有一组 该组中最少存在 一个数 是同组中某两个数之和或另一个数的两倍 反反反证证证法法法 设任何一组数中的每一个数 它既不等于同组中另为两个数之和 也不等于同组中另一个数的两倍 即任何一组数中任意两个数之差总不在这个 组中 由抽屉原理知 四组中至少有一组 称为 组 其中至少有 17 个数 从 中取 17 个 记为 1 2 17 不妨设 17最大 令 1 17 1 2 16 显然 1 1 65 由假设知 1 所以该 16 数必在另外三组 中 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日14 39 再由抽屉原理知 三组中至少有一组 设为 组 至少含有 6 个 1 只取其中 6 个 记为 1 2 6 同理可设 6最大 并令 1 6 1 2 5 同样有 1 1 65 且 1 而且由假设知 1 6 17 17 故该 5 个数一定在 或 中 又由抽屉原理 设 组中至少有 3 个 1 取其中 3 个记为 1 2 3 同理可证 1 3 2 2 3 1 1 2 1 65 也不在 三组中 故必在 组中 进一步 可证得 2 1 2 1不在 中 且满足 1 65 这说明从 1 到 65 的这 65 个整数中有一个不在 这 4 组的任何一组中 与题设矛盾 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日15 39 再由抽屉原理知 三组中至少有一组 设为 组 至少含有 6 个 1 只取其中 6 个 记为 1 2 6 同理可设 6最大 并令 1 6 1 2 5 同样有 1 1 65 且 1 而且由假设知 1 6 17 17 故该 5 个数一定在 或 中 又由抽屉原理 设 组中至少有 3 个 1 取其中 3 个记为 1 2 3 同理可证 1 3 2 2 3 1 1 2 1 65 也不在 三组中 故必在 组中 进一步 可证得 2 1 2 1不在 中 且满足 1 65 这说明从 1 到 65 的这 65 个整数中有一个不在 这 4 组的任何一组中 与题设矛盾 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日15 39 再由抽屉原理知 三组中至少有一组 设为 组 至少含有 6 个 1 只取其中 6 个 记为 1 2 6 同理可设 6最大 并令 1 6 1 2 5 同样有 1 1 65 且 1 而且由假设知 1 6 17 17 故该 5 个数一定在 或 中 又由抽屉原理 设 组中至少有 3 个 1 取其中 3 个记为 1 2 3 同理可证 1 3 2 2 3 1 1 2 1 65 也不在 三组中 故必在 组中 进一步 可证得 2 1 2 1不在 中 且满足 1 1 则 1 2 中至少有一个数不小于 推论 2 3 若将 个物品放入 个盒子中 则至少有一个盒子中有不少于 个物品 其中 是不小于 的最小整数 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日17 39 在定理 2 1 中令 1 2 2 则变成了鸽笼原理的简单形式 在定理 2 1 中令 1 2 则得到如下的推论 推论 2 1 若将 1 1 个物品放入 个盒子中 则至少有一个盒子中有 个物品 推论 2 1 也可以叙述成如下推论 2 2 所描述的另一种形式 推论 2 2 设 1 2 是 个整数 而且 1 2 1 则 1 2 中至少有一个数不小于 推论 2 3 若将 个物品放入 个盒子中 则至少有一个盒子中有不少于 个物品 其中 是不小于 的最小整数 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日17 39 在定理 2 1 中令 1 2 2 则变成了鸽笼原理的简单形式 在定理 2 1 中令 1 2 则得到如下的推论 推论 2 1 若将 1 1 个物品放入 个盒子中 则至少有一个盒子中有 个物品 推论 2 1 也可以叙述成如下推论 2 2 所描述的另一种形式 推论 2 2 设 1 2 是 个整数 而且 1 2 1 则 1 2 中至少有一个数不小于 推论 2 3 若将 个物品放入 个盒子中 则至少有一个盒子中有不少于 个物品 其中 是不小于 的最小整数 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日17 39 例 2 1 设有大小两只圆盘 每个都划分成大小相等的 200 个小扇形 在大盘上任选 100 个小扇形漆成黑色 其余的 100 个小扇形漆成白色 而将小盘上的 200 个小扇 形任意漆成黑色或白色 现将大小两只圆盘的中心重合 转动小盘使小盘上的每 个小扇形含在大盘上小扇形之内 证明 有一个位置使小盘上至少有 100 个小 扇形同大盘上相应的小扇形同色 t 1 t 2 1 200 图 2 1 圆盘示意图 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日18 39 t 1 t 2 1 200 图 2 2 圆盘示意图 证证证明明明 如图 2 2 所示 使大小两盘中心重合 固定大盘 转动小盘 则有 200 个不同位置使小盘上的每个小扇形含在大盘上的小扇形中 由于大盘上的 200 个小扇形中有 100 个漆成黑色 100 个漆成白色 所以小盘上的每个小扇形 无论漆成黑色或白色 在 200 个可能的重合位置上恰好有 100 次与大盘上的小 扇形同色 因而小盘上的 200 个小扇形在 200 个重合位置上共同色 100 200 20000 次 平均每个位置同色 20000 20 100 次 由鸽笼原理知 存在着某个位置 使同色的小扇形数大于等于 100 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日19 39 例 2 2 由 1 个不同实数构成的序列 1 2 1 中必存在一个 1 项的递增子序列或 1 项的递减子序列 某个序列 1 2 是递 增的 是指该序列满足 1 2 2 则称为 是递减的 证证证明明明 针对每一个 以 为首项 向后寻找递增子序列 最长子序列的 项数 即长度 记为 1 2 1 则 1 1 若 之后 每一项都比 小 则 1 若 之后有一项 比 大 则 2 若 之 后还有一项 比 大 则 3 若有某个 1 则问题得证 否则 所有 1 由推论 2 1 至少有 1 个 相等 设 1 2 1 1 1 2 2 1 从而构成 1 个实数的递减子序列 事实上 若 时 有 则以 为首项的最长递增子序列比 以 为首项的最长递增子序列至少多一项 即 矛盾 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日20 39 例 2 2 由 1 个不同实数构成的序列 1 2 1 中必存在一个 1 项的递增子序列或 1 项的递减子序列 某个序列 1 2 是递 增的 是指该序列满足 1 2 2 则称为 是递减的 证证证明明明 针对每一个 以 为首项 向后寻找递增子序列 最长子序列的 项数 即长度 记为 1 2 1 则 1 1 若 之后 每一项都比 小 则 1 若 之后有一项 比 大 则 2 若 之 后还有一项 比 大 则 3 若有某个 1 则问题得证 否则 所有 1 由推论 2 1 至少有 1 个 相等 设 1 2 1 1 1 2 2 1 从而构成 1 个实数的递减子序列 事实上 若 时 有 则以 为首项的最长递增子序列比 以 为首项的最长递增子序列至少多一项 即 矛盾 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日20 39 例 2 2 由 1 个不同实数构成的序列 1 2 1 中必存在一个 1 项的递增子序列或 1 项的递减子序列 某个序列 1 2 是递 增的 是指该序列满足 1 2 2 则称为 是递减的 证证证明明明 针对每一个 以 为首项 向后寻找递增子序列 最长子序列的 项数 即长度 记为 1 2 1 则 1 1 若 之后 每一项都比 小 则 1 若 之后有一项 比 大 则 2 若 之 后还有一项 比 大 则 3 若有某个 1 则问题得证 否则 所有 1 由推论 2 1 至少有 1 个 相等 设 1 2 1 1 1 2 2 1 从而构成 1 个实数的递减子序列 事实上 若 时 有 则以 为首项的最长递增子序列比 以 为首项的最长递增子序列至少多一项 即 矛盾 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日20 39 例 2 2 由 1 个不同实数构成的序列 1 2 1 中必存在一个 1 项的递增子序列或 1 项的递减子序列 某个序列 1 2 是递 增的 是指该序列满足 1 2 2 则称为 是递减的 证证证明明明 针对每一个 以 为首项 向后寻找递增子序列 最长子序列的 项数 即长度 记为 1 2 1 则 1 1 若 之后 每一项都比 小 则 1 若 之后有一项 比 大 则 2 若 之 后还有一项 比 大 则 3 若有某个 1 则问题得证 否则 所有 1 由推论 2 1 至少有 1 个 相等 设 1 2 1 1 1 2 2 1 从而构成 1 个实数的递减子序列 事实上 若 时 有 则以 为首项的最长递增子序列比 以 为首项的最长递增子序列至少多一项 即 矛盾 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日20 39 本例已达到最好的可能结果 特例 实际的问题为 不同高度的 2 1 个人随意排成一行 那么 总能从中挑出 1 个人 让其出列后 他们恰好是由低向高排列的 例 2 3 任意 2 1 个实数 1 2 3 2 1 2 2 组成的序列中 必有一个长为 1 的非降子序列 或必有一个长为 1 的非 升子序列 证明本例前 首先看一个具体的例子 3 对于序列 5 3 16 10 15 14 9 11 6 7 从中可以选出如下几个递减子序列 5 3 16 10 9 6 16 15 14 11 7 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日21 39 本例已达到最好的可能结果 特例 实际的问题为 不同高度的 2 1 个人随意排成一行 那么 总能从中挑出 1 个人 让其出列后 他们恰好是由低向高排列的 例 2 3 任意 2 1 个实数 1 2 3 2 1 2 2 组成的序列中 必有一个长为 1 的非降子序列 或必有一个长为 1 的非 升子序列 证明本例前 首先看一个具体的例子 3 对于序列 5 3 16 10 15 14 9 11 6 7 从中可以选出如下几个递减子序列 5 3 16 10 9 6 16 15 14 11 7 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日21 39 本例已达到最好的可能结果 特例 实际的问题为 不同高度的 2 1 个人随意排成一行 那么 总能从中挑出 1 个人 让其出列后 他们恰好是由低向高排列的 例 2 3 任意 2 1 个实数 1 2 3 2 1 2 2 组成的序列中 必有一个长为 1 的非降子序列 或必有一个长为 1 的非 升子序列 证明本例前 首先看一个具体的例子 3 对于序列 5 3 16 10 15 14 9 11 6 7 从中可以选出如下几个递减子序列 5 3 16 10 9 6 16 15 14 11 7 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日21 39 证证证法法法 1 假设长为 2 1 的实数序列 2 2 中没有长度为 1 的非降子 序列 下面证明其必有一长度为 1 的非升子序列 1 令 表示从 开始的最长非降子序列的长度 因为实数序列 2 2 中没有长度为 1 的非降子序列 所以有 1 1 2 2 1 这相当于把 2 1 个物品 1 2 2 1放入 个盒子 1 2 中 由鸽笼原理知 必有一个盒子 里面至少有 1 个物品 即存在 1 2 1及 1 使得 1 2 1 2 3 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日22 39 2 对应于这些下标的实数序列必满足 1 2 1 2 4 它们构成一长为 1 的非增子序列 否则 若有某个 1 使得 1 那么由从 1开始的最 长非降子序列加上 就得到一个从 开始的长度为 1 1 的非降子序 列 由 的定义知 1 1 这与 1 2 1 矛 盾 因此 2 4 式成立 从而定理的结论成立 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日23 39 2 对应于这些下标的实数序列必满足 1 2 1 2 4 它们构成一长为 1 的非增子序列 否则 若有某个 1 使得 1 那么由从 1开始的最 长非降子序列加上 就得到一个从 开始的长度为 1 1 的非降子序 列 由 的定义知 1 1 这与 1 2 1 矛 盾 因此 2 4 式成立 从而定理的结论成立 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日23 39 证证证法法法 2 由题意 假设 是从 开始的递减子序列的最大长度 是从 开始的递增子序列的最大长度 则对于从 1 到 2 1 的每个 的取值 都有 与之对应 反证法 假设 1 且 1 1 2 1 由集合论的知 识很容易知道集合 的数量为 2 根据鸽笼原理 必然有 则 与从 开始的最长递减子序列合并组成的子序列的 长度 这与 矛盾 2 若 则 与从 开始的最长递增子序列合并组成的子序列的 长度 这又与 矛盾 所以假设 1 且 1 不成立 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日24 39 证证证法法法 2 由题意 假设 是从 开始的递减子序列的最大长度 是从 开始的递增子序列的最大长度 则对于从 1 到 2 1 的每个 的取值 都有 与之对应 反证法 假设 1 且 1 1 2 1 由集合论的知 识很容易知道集合 的数量为 2 根据鸽笼原理 必然有 则 与从 开始的最长递减子序列合并组成的子序列的 长度 这与 矛盾 2 若 则 与从 开始的最长递增子序列合并组成的子序列的 长度 这又与 矛盾 所以假设 1 且 1 不成立 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日24 39 例 2 4 已知 402 个集合 每个集合都恰有 20 个元素 其中每两个集合都恰有一个公共 元素 求这 402 个集合的并集所含元素的个数 解解解 设所给的 402 个集合为 1 2 401和 又设 1 2 20 由条件知 1 1 2 401 是 的省写 即每个 1 2 401 中恰好含有 中的某一个元素 1 2 20 记诸 中包含 1 2 20 的个数为 1 2 20 则 1 2 20 401 1 401 1 1 401 20 20 1 由抽屉原理 必有正整数 1 20 使得 21 下面证明此 401 且其余的诸 1 2 20 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日25 39 如果 401 即 0 设为 1 20 由题意知必存在某个 1 401 满足 从而由 1 知 设包含 的 个集合是 1 2 则同样由条件知 1 1 2 所以可设 1 2 并知 1 2 彼此相异 否则若有某两个 1 20 这又与题设 20 矛盾 所以必有 401 从而知 1 2 401 令 1 2 401 402 则 19 且 有 1 2 401 1 1 402 1 1 402 1 1 19 402 7639 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日26 39 如果 401 即 0 设为 1 20 由题意知必存在某个 1 401 满足 从而由 1 知 设包含 的 个集合是 1 2 则同样由条件知 1 1 2 所以可设 1 2 并知 1 2 彼此相异 否则若有某两个 1 20 这又与题设 20 矛盾 所以必有 401 从而知 1 2 401 令 1 2 401 402 则 19 且 有 1 2 401 1 1 402 1 1 402 1 1 19 402 7639 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日26 39 1鸽笼原理的简单形式 2鸽笼原理的加强形式 3Ramsey 定理 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日27 39 Ramsey 定理的核心思想是 任何一个足够大的结构中必定包含一个给定 大小的规则子结构 1928 年英国英国数学家 哲学家 逻辑学家 经济学家 Frank Ramsey 1903 1930 在伦敦数学会上宣读一篇 论形式逻辑中的一个问 题 的论文 奠定了 Ramsey 理论的基础 Ramsey 定理已经发展成为 Ramsey 理论并渗透到诸多研究领域 而且仍然是研究热点问题 Ramsey只活到28岁 生平只发表了两篇经济学论文 但这两篇经济学论文造就了三个诺贝尔经济学 奖 1958 年 6 7 月号美国 数学杂志 上登载着这样一个有趣的问题 任何 一个 6 人聚会 必有 3 个人相互认识或者相互不认识 这个问题实质上就是一 个 Ramsey 问题 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日27 39 例 3 1 6是 6 个顶点的完全图 用红 蓝两色涂色 6的边 则或者存在一个红三角 形 或者存在一个蓝三角形 证证证明明明 1 设 6的顶点为 1 2 6 对于 6的任何一种涂色方案 由鸽笼原理 1关联的边中有 3 条同色边 不妨设这三条边为 1 2 1 3 1 4 2 若这三边为红色 当 2 3 4之间有一条红边 比如说是 2 3 则 1 2 3构成一个红三角形 当 2 3 4之间没有红边 则 2 3 4构成一个蓝 三角形 3 同理可证当这三边为蓝色时命题也为真 1 V 2 V 3 V 4 V 红红 红 图 3 3 三角形构造 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日28 39 例 3 2 用红 蓝两色涂色 9的边 证明存在一个蓝三角形或红色的完全四边形 证证证明明明 设 9的顶点为 1 2 9 对于 9的任何一种涂色方案 必存 在一个顶点连接 4 条蓝边或 6 条红边 假若不然 每个顶点至多连接 3 条蓝边 和 5 条红边 那么蓝边总数至多为 9 3 2 13 而红边总数至多为 9 5 2 22 与 9具有 9 8 2 36 条边矛盾 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日29 39 不妨设 1连接 4 条蓝边或 6 条红边 1 若 1连接 4 条蓝边 不妨设为 1 2 1 3 1 4 1 5 若 2 3 4 5之间存在一条蓝边 比如说是 2 3 则 1 2 3构成一个蓝三 角形 若 2 3 4 5之间不存在蓝边 则这四个顶点构成一个红完全四边形 2 若 1连接 6 条红边 不妨设为 1 2 1 3 1 4 1 5 1 6 1 7 根据例 3 1 2 3 7之间有一个蓝三角形或红三角形 如果存在一个蓝三角形则命题得证 如果存在一个红三角形 则它与 1构成一 个红完全四边形 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日30 39 例 3 3 设 是具有 20 个顶点的完全图 20 对 的边任意涂以红色或蓝色 则在 中一定存在一个蓝色的完全四边形 或者红色的完全四边形 证证证明明明 任取 20一个顶点 它与 19 条边连接 必存在 10 条同色的边 不妨设为红色 这 10 条红色的边连接的 10 个顶点构成 10 由例 3 2 知 10 中或者存在蓝色 3 或者存在红色 4 若存在蓝色的 3 它与 构成蓝色的 4 若存在红色的 4 得证 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日31 39 对上面的几个命题进行归纳 可以得出如下定义 定义 3 1 对于任意给定的两个正整数 和 如果存在最小的正整数 使得当 时 对 任意进行红 蓝两边着色 中均有红色 或蓝色 则 称为 Ramsey 数 Ramsey 数的简单性质 定理 3 1 对任意正整数 有 1 2 2 刘西奎 山东科技大学 组合数学讲义 第 7 讲2010 年 9 月 17 日32 39 定理 3 2 Ramsey 定理的简单形式 设 是正整数 2 则存在最小的正整数 使得当 时 用红 蓝两色涂色 的边 或者存在一个蓝色的完全 边形 或者存在一个 红色的完全 边形 证证证明明明 用归纳法 设 为任意正整数 2 用红 蓝两色涂色 的边 若没有一条红