组合数学ch.pptVIP

证明：对于任意一个整数，它除以100的余数显然只能有如下100种情况， 0，1，2，3，……，99 而现在有任意给定的52个整数，我们需要构造51个盒子，即对这100个余数进行分组，共51组： {0}，{1，99}，{2，98}，{3，97}，……，{49，51}，{50} 根据定理2.1.1，这52个整数，必有两个整数除以100的余数落入上面51组中的同一组中， 若是{0}或{50}则说明它们的和及都能被100整除； 若是剩下的49组的话，因为一组有两个余数，余数相同则它们的差能被100整除，余数不同则它们的和能被100整除。 而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两列与图中的某一列相同，即各自所包含的两个同色单元格的位置相同、颜色相同。即结论成立。 例2.2.1 一个袋子里装了10个苹果，11个橘子，12个香蕉，至少取出多少个水果才能保证已经取出10个相同种类的水果 §2.3 Ramsey定理 任何一个6人聚会，必有3个人相互认识或者相互不认识 例2.3.1 设K6是6个顶点的完全图，用红、蓝两色涂色K6的边，则存在一个红色三角形，或存在一个蓝色三角形。 定理 2.3.1 设p，q是正整数，p，q≥2，则存在最小的正整数R(p,q)，使得当n≥R(p,q)时，用红、蓝两色涂色Kn的边，或者存在一个蓝色的完全p边形Kp，或者存在一个红色的完全q边形Kq。 定理2.3.2 设p, q是正整数，p，q≥2，则R(p, q)= R(q, p) * 第二章 鸽巢原理和Ramsey定理 例2.2.4 证明 假设不存在长为n+1的递增子序列，我们来证明必存在长为n+1的递减子序列。 令mk表示从ak开始的递增子序列的最大长度, 对每个k(k=1,2,…,n2+1)， * 第二章 鸽巢原理和Ramsey定理 n+1个mk取值相等，不妨设为 由假设可知 1≤mk≤n。 考虑 * 第二章 鸽巢原理和Ramsey定理 * 第二章 鸽巢原理和Ramsey定理 例2.1.6证明：任意n2+1 个实数 组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。 证明：由题意，设Li是从ai开始的递减子序列的最大长度，Mi是从ai开始的递增子序列的最大长度，则对于i从1到n2 + 1的每个i的取值，都有（Li, Mi）与之对应。 * 第二章 鸽巢原理和Ramsey定理 （1）若ai aj，则ai与从aj开始的最长递减子序列合并，组成的子序列的长度Li ≥Lj+1 Lj；这与Li = Lj矛盾； 反证法。假设即不存在长度为n+1的递增子序列，也不存在长度为n+1的递减子序列即1≤Li≤n 且 1≤Mi≤n，其中1≤i≤n2 + 1，由集合论的知识知道集合{(Li, Mi)}的元素数为n2，根据定理2.1.1，必然有（Li, Mi） = (Lj, Mj)（i j），当然Li = Lj，而且Mi = Mj。对于序列中的元素ai, aj，分两种情况： * 第二章 鸽巢原理和Ramsey定理 （2）若ai aj，则ai与从aj开始的最长递增子序列合并，组成的子序列的长度Mi ≥Mj+1 Mj，这又与Mi = Mj矛盾。 所以假设1≤Li≤n 且 1≤Mi≤n不成立。原结论成立。 这个例子的结论是1935年由数学家保罗·艾狄胥（Erd?s）和乔治·塞克尔斯（Szekeres）首先给出的，它还有更为有趣的表述：n2+1个人肩并肩地站成一排，则总能选除n+1个人，让他们向前迈出一步，所形成新一排的身高是递增或递减的。 其思想可以概括为“在任何一个足够大的结构中必定包含一个给定大小的规则子结构”。 证明：设K6的顶点为v1,v2,…,v6。对于K6的任何一 种涂色方案，由推论2.2.3.，v1关联的边中必有 条同色边。不妨设这三条边为{v1 ,v2},{v1 ,v3},{v1 ,v4} 若这三边为红色，当v2 ,v3 ,v4之间有一条红边，比如说是{v2 ,v3},则v1v2v3构成一个红三角形；当v2 ,v3 ,v4之间没有红边，则v2 v3 v4构成一个蓝三角形。 若这三边为蓝色时，同理可证。 因此，结论成立。 当使用红、蓝两色对一个完全图的边任意涂色的时候，要使得这个完全图中包含一个蓝色的完全p边形或红色的完全q边形，我们把满足这一条件的最小正整数记作R(p, q)。这些数就是Ramsey数。 证明：采用数学归纳法。 设p为任意正整数，q=2。用红、蓝两色涂色Kp的边，若没有一条红边，则存在一个蓝色的完全p边形；若有一条红边，则构成一个完全红2边形，因此R(p,2)≤p。同理可