组合数学课件_chapter计算机科学与技术学院.pdfVIP

第二章鸽巢原理和Ramsey定理 ◼ 2.1 鸽巢原理的简单形式 ◼ 2.2 鸽巢原理的加强形式 ◼ 2.3 Ramsey定理 2021/1/20 计算机科学与技术学院 1 鸽巢原理的简单形式 组合存在性定理 Ramsey定理（鸽巢原理为其最简形式） 偏序集分解定理（Dilworth定理） 相异代表系存在定理（Hall定理） 鸽巢原理是组合学中最简单、最基本原理 也叫抽屉原理或 雷原理 (Dirichlet(1805-1859)19世纪德国数学家) 。 2021/1/20 计算机科学与技术学院 2 鸽巢原理的简单形式 定理2.1.1 如果把n+1 个物品放入n 个盒子中，那么至少有一个盒子中有 两个或 的物品。 证明：反证法 如果每个盒子中至多有一个物品，那么n 个盒子中至多有n 个物品，而 我们共有n+1 个物品， 。故定理成立。 鸽巢原理只断言存在一个盒子，该盒中有两个或两个以上的物品，但它 并没有 是哪个盒子。所以，这个原理只能用来证明某种安排的存在性， 而对于找出这种安排却毫无帮助。 2021/1/20 计算机科学与技术学院 3 鸽巢原理的简单形式 ➢注意1，应用时要分清物体与盒子以 及物体总数与盒子总数。 ➢注意2，定理只是存在性定理，不能 找出具体的物体。 ➢注意3 ，不能被推广到只存在n个(或 更少)物体的情形。 2021/1/20 计算机科学与技术学院 4 鸽巢原理的简单形式 例2.1.1 13 人中至少有２人是同月出生的。 13 人中至少有２人属相相同。 367 人中至少有２人的生日相同。 设有n 对夫妇，问至少要从这2n 个人中选出多少人，才能保证能 够有一对夫妇被选出？ 2021/1/20 计算机科学与技术学院 5 鸽巢原理的简单形式 例2.1.2 给出m 个数a ,a ,…a ，证明：必存在整数k, j (0kjm)， 1 2 m 使得m|(a +…+a ). k+1 j 明 构造部分和序列 证明： 构造部分和序列 s a , 1 1 s a +a , 2 1 2 …， s a +a +…a ， m 1 2 m 2021/1/20 计算机科学与技术学院 6 鸽巢原理的简单形式 则有如下两种可能： 1）存在整数s （1hm），使得m|s 。此时，取k=0,j=h 即满足题意。 h h