组合数学幻灯片.ppt

* * * 【例15】 ：设n是大于1的奇数，则下列数的集合： {2-1,22-1,23-1,...,2n-1-1,2n-1}中至少存在一数被n除尽。 证： {2-1,22-1,23-1,...,2n-1-1,2n-1}整除n可得n个余数， 除以n的余数共有0,1,2,…,n-1个。 如果{2-1,22-1,23-1,...,2n-1-1,2n-1}除以n所得余数互不相等,则结论成立。 否则： 2 鸽巢原理：加强形式 * * * 设a,b?n,a?b, 2a-1(modn)=2b-1(modn)=r 2a-1=hn+r,2b-1=mn+r 设ab, 2a-2b=(h-m)n 2b(2a-b-1)=(h-m)n 2a-b-1即为所求： 2 鸽巢原理：加强形式 * * * 【例16】 ：能否在一个n?n的棋盘的每个方格填上1,2或3，使得棋盘上各行各列以及对角线上的数字之和都不相等。 解：棋盘上各行各列以及对角线上的数字之和共有2n+2个数。 从1,2或3中取n个数， 答案是否定的。 从1,2或3中取n个数，最大和值是3n,最小和值是n,共有2n+1个数值。 2 鸽巢原理：加强形式 * * 【例17】 一个抽屉里由20件衬衫，其中4件蓝色，7件 灰色，9件红色.从中随意取出至少多少件，才能保证 有4件是同色的？保证5，6，7，8，9件同色呢？ 解:　1、3×3＋1＝10保证4件同色。 2、4＋4×2＋1＝13保证5件同色。 3、4＋5×2＋1＝15保证6件同色。 4、4＋6×2＋1＝17保证7件同色。 5、4＋7＋7＋1＝19保证8件同色。 6、4＋7＋8＋1＝20保证9件同色。 2 鸽巢原理：加强形式 * * 2 鸽巢原理：加强形式 定理1.2.3 假设类型i的物品有xi件，i=1,2,…,n,且 从中任意取出至少ar件才能保证至少有r件同类型的物品，则 * * * 【引例】（Ramsey问题） 试证6个人在一起，其中至少存在3个人或互相认识，或互相不认识。 va vb vc vd ve vf 不认识的两个人对应 的顶点联线着蓝色。 6个人设为A,B,C,D,E,F,分别用6个顶点va,vb,vc,vd,ve,vf表示，过此6个顶点作完全图，互相认识的两个人，对应顶点的连线着红色。 3 Ramsey问题与Ramsey数 * * * 问题等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或者存在一个蓝色边三角形。 va vb vc vd ve vf 3 Ramsey问题与Ramsey数 * * * Va点和其他5个顶点相连有5条边，每条边或着以红色，或着以蓝色。依据鸽巢原理，其中至少有3条边同色，不妨假定有3条边着以红色， va vb vc vd ve vf 3条边的另外3个端点设为ve,vd,vb。 这3个端点间的联线或同色或不同色， 若同色。则已存在一个同色三角形，如果不同色，则至少有一条边是红色，从而有同色三角形 3 Ramsey问题与Ramsey数 * * 类似可得 命题2： 对6个顶点的完全图任意进行红、蓝两边着色,都至少存在两个同色的三角形. 命题3： 对10个顶点的完全图K10任意进行红、蓝两边着色,都或者存在一个红色K4，或者存在一个蓝色K3 命题4： 对9个顶点的完全图K9任意进行红、蓝两边着色,都或者存在一个红色K4,或者存在一个蓝色K3. 命题 5： K18的边红,蓝２着色,存在红K4或蓝K4 ． 由上述推导得如下命题 命题1： 对6个顶点的完全图任意进行红、蓝两边着色，都存在一个红色的三角形或蓝色的三角形. 3 Ramsey问题与Ramsey数 * * 3 Ramsey问题与Ramsey数 定义 1.3.1 对于任意给定的两个正整数a和b，如果存在最小的正整数r(a,b)使得当N≥r(a,b)时，对KN任意进行红、蓝两边着色，KN中均有红色Ka，或蓝色Kb，则r(a,b)称为Ramsey数. 对上面的几个命题进行归纳，可以得出如下定义： 定理 1.3.1 对任意正整数a，b，有 （1）r(a,b) =r(b,a) （2）r(a,2)=a * * 3 Ramsey问题与Ramsey数 证明 令N＝r(a-1,b) + r(a,b-1),对KN进行任意红、蓝两边着色. 设x是KN的一个顶点,在KN中与x相关联的边共有r(a-1,b) + r(a,b-1)条,这些边要么为红色,要么为蓝色. 由鸽