2012软件组合数学第二章鸽巢原理简单形式

1、第二章 鸽巢原理和Ramsey定理组合存在性定理Ramsey定理（鸽巢原理为其最简形式）偏序集分解定理（Dilworth定理）相异代表系存在定理（Hall定理）1928年英国数学家、哲学家兼经济学家Frank， Ramsey(1903-1930) 在伦敦数学会上宣读一篇 “ 论形式逻辑中的一个问题”的论文，奠定了 Ramsey理论的基础。核心思想是：“任何一个足够大的结构中必定包含一个给定大小的规则子结构”2022年8月30日第二章 鸽巢原理和Ramsey定理第二章 鸽巢原理和Ramsey定理2.1 鸽巢原理的简单形式2.2 鸽巢原理的加强形式2.3 Ramsey定理2022年8月30日第二章

2、 鸽巢原理和Ramsey定理2.1 鸽巢原理的简单形式鸽巢原理是组合学中最简单、最基本原理也叫抽屉原理(又称为重叠原理或狄利克雷(Dirichlet)原理）。定理2.1.1若把n+1个物体放入n个盒子中，则至少有一个盒子中有2个或更多的物体2022年8月30日第二章 鸽巢原理和Ramsey定理证明 如果每个盒子中至多有一个物体，那么n个盒子中至多有n个物体，而我们共有n+1个物体，矛盾。故定理成立。 鸽巢原理的集合描述形式： 设有限集合A有n+1个元素，将A分划成n个不相交子集的并，则至少有一个子集含有两个或两个以上的元素。 定理是用群体的整体性表现出个体的某些特性，属于从宏观到微观的理论研究

3、成果注意 应用时要分清物品与盒子以及物体数与盒子总数。 这个原理只能用来证明某种安排的存在性，而却不能找到具体满足要求的安排 不能被推广到只存在n个(或更少)物体的情形。2022年8月30日第二章 鸽巢原理和Ramsey定理例2.1.1 证明：13个人中必有两人的属相相同。 几个例子例2.1.2 有5双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能保证找到1双袜子？ 2022年8月30日第二章 鸽巢原理和Ramsey定理解 应用定理2.1.1，共有5个盒子，每个盒子对应1双袜子。如果选择5+1=6只袜子分别放到它所属那双袜子的盒子中，则必有两只袜子落入同一个盒子中，即为一双袜子。因此

4、我们至少从中选出6只袜子才能保证找到1双袜子。 本例实际上是知道n个盒子，而找n+1个物体的问题。 2022年8月30日第二章 鸽巢原理和Ramsey定理例2.1.3对任意给定的52个整数，证明：其中必存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 2022年8月30日第二章 鸽巢原理和Ramsey定理1、已知：52个整数，2、目标：找被100整除的两个数3、解题途径：把52个物体放到51个盒子中，需要构造51个盒子4、根据题干中要求的两个整数必须具备的性质构造盒子5、是否能够被100整除的关键在余数，那么一个整数除以100的余数为0，1，2，99 两个整数的和可以被1

5、00整除，则二者的余数的和是100 两个整数的差可以被100整除，则二者的余数相同分析：证明：对于任意一个整数，它除以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整除。2022年8月30日第二章 鸽巢

6、原理和Ramsey定理例2.1.4 一名象棋大师有11周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累一周中下棋的次数不能多于12盘。证明：她一定在此期间的连续若干天中恰好下棋21盘。 2022年8月30日第二章 鸽巢原理和Ramsey定理1、题干提供的信息：一共11周2、约束条件： 每周最多下12盘棋 每天至少下1盘棋 3、目标：连续若干天共下棋21盘4、解题途径：构造下棋盘数的部分和分析：2022年8月30日第二章 鸽巢原理和Ramsey定理证明:令b1，b2，b77分别为这11周中他每天下棋的次数，并作部分和a1=b1,a2=b1+b2,，a77=b1+b2+b77.2022年

7、8月30日第二章 鸽巢原理和Ramsey定理所以有1a1a2a3a771211=132 (2.1.1)考虑数列a1,a2,，a77，a1+21,a2+21,，a77+21,它们都在1与132+21=153之间，共有154项，由定理2.1.1知，其中必有两项相等根据题意，有bi1(1i77),且bi+bi+1+bi+612(1i71),2022年8月30日第二章 鸽巢原理和Ramsey定理由（2.1.1）式知a1,a2,，a77这77项互不相等，从而a1+21,a2+21,，a77+21这77项也互不相等，所以一定存在1i aj，则ai与从aj开始的最长递减子序列合并，组成的子序列的长度Li=L

8、j+1 Lj；这与Li = Lj矛盾；反证法。假设既不存在长度为n+1的递增子序列，也不存在长度为n+1的递减子序列即1Lin 且 1Min，其中1in2 + 1，由集合论的知识知道集合(Li, Mi)的元素数为n2，根据定理2.1.1，必然有（Li, Mi） = (Lj, Mj)（i j），当然Li = Lj，而且Mi = Mj。对于序列中的元素ai, aj，分两种情况： 2022年8月30日第二章 鸽巢原理和Ramsey定理（2）若ai Mj，这又与Mi = Mj矛盾。所以假设1Lin 且 1Min不成立。原结论成立。这个例子的结论是1935年由数学家保罗艾狄胥（Erds）和乔治塞克尔斯（

9、Szekeres）首先给出的，它还有更为有趣的表述：n2+1个人肩并肩地站成一排，则总能选出n+1个人，让他们向前迈出一步，所形成新一排的身高是递增或递减的。2022年8月30日第二章 鸽巢原理和Ramsey定理定理2.1.1 鸽巢原理简单形式若把n+1个物体放入n个盒子中，则至少有一个盒子中有2个或更多的物体思考？把多少个物体放到 n 个盒子中，能保证至少存在一个盒子中包含 r 个以上物体？2022年8月30日第二章 鸽巢原理和Ramsey定理2022年8月30日第二章 鸽巢原理和Ramsey定理定理2.2.1的推论推论2.2.1若 n(r1) + 1个物品放入n个盒子。则至少有一个盒子里含

10、有r个或者更多的物品。证明 在定理2.2.1中取q1=q2=qn=r即可。2022年8月30日第二章 鸽巢原理和Ramsey定理2.2 鸽巢原理的加强形式定理2.2.1 (鸽巢原理的加强形式)2鸽巢原理的加强形式定理2.2.1 的证明证明:(反证法) 对于i1，2，n，假设第i个盒子里至多含有qi-1个物品，则n个盒子里物品数的总和不超过 q1+q2+qn n 个与已知条件(q1+q2+qn n+1)矛盾。2022年8月30日第二章 鸽巢原理和Ramsey定理 与简单形式的关系 上节的鸽巢原理的简单形式是这一原理的特殊情况，即q1 = q2 = = qn= 2，有 q1 + q2 + +qnn + 1 = n + 12022年8月30日第二章 鸽巢原理和Ramsey定理 推论2.2.2 若设有n个正整数m1 , m2 , , mn满足下面的不等式 (m1 + +mn)/n r1, 则 m1, mn中至少有一个数 r证明 由上面的不等式得 m1 + +mn (r1)n+1， 由推论2.2.1， 存在mi，使得mir。 另外一个平均原理：设有n个正整数m1 , m2 , , mn满足下面的不