第三章鸽巢原理加强形式与ramsey定理.pdfVIP

第三章鸽巢原理加强形式 与Ramsey定理 北航计算机学院：李建欣 Tel （G506） E-mail：lijx@ /lijx 几个问题  水果放置问题  一篮水果装有苹果、香蕉和橘子。为了保证或至少8 个苹果，或至少6个香蕉或至少9个橘子，则放入最少 件数是多少？  扇子重合度是多少？  大小扇子200个格子，外圈选100色涂蓝,内圈随 机涂两种颜色，旋转出现重合格子数？  完全图（Ramsey数）  对于6个点构成完全图，两种颜色去涂，是否存 在同色三角形？  三种颜色去涂若干点，多少个点能够保证一定存 在同色三角形？ 主要内容  鸽巢原理加强形式及应用例子  Ramsey定理 鸽巢原理：加强形式  定理3.2.1 令q , q , ,q 为正整数.若将 1 2 n q +q ++q –n+1 1 2 n 个物体被放进n个盒子内，那么，或者第一个盒子 至少含有个q 物体，或者第二个盒子至少含有个q 1 2 物体，，或者第n个盒子至少含有个q 物体。 n  证明: 若第i个盒子都少于q ，那么物体总数少于 i 或等于  (q – 1)+(q – 1)++(q – 1)=q +q ++q –n 1 2 n 1 2 n 其他形式  如果n个物体放入k个盒子，至少有一个盒 子包含至少[n/k]个物体。 注：[n/k]表示n/k的上界整数。 特别情形  初等数学叙述。  平均原理 m m m 1 2 n  r 1 n 至少存在一个m 大于或等于r. i 应用例子1  例1. 一篮水果装有苹果、香蕉和橘子。为 了保证或者至少8个苹果，或者至少6个香 蕉或者至少9个橘子，则放入篮子中的水果 的最少件数是多少？  鸽巢原理加强形式简单应用。 苹果 香蕉 橘子 8 或  6 或  9 8＋6＋9－3＋1＝21 件 应用例子2  两个大小不一被分成200个相等扇形的碟子， 在大碟子中任选100个扇形涂成红色，其余 的涂成蓝色。小碟子中，每一个扇形随机 地涂成红色或者蓝色,数目无限制。将小碟 子与大碟子中心重合，  证明：能够通过适合旋转，存在两个碟子 相同颜色重合的扇形数存在至少是100个的 情形。 分析： 大碟子不动，转动小 碟子，转完一圈， 2 3 回到原位，每个扇形 1 4