计算机2009组合数学—第二章鸽巢原理和Ramsey定理 (2).ppt

《计算机2009组合数学—第二章鸽巢原理和Ramsey定理 (2).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

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

5、，…，99两个整数的和可以被100整除，则二者的余数的和是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组的话，因为一组有两个余数，余数相

6、同则它们的差能被100整除，余数不同则它们的和能被100整除。2021年7月22日第二章鸽巢原理和Ramsey定理例2.1.4一名象棋大师有11周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累一周中下棋的次数不能多于12盘。证明：她一定在此期间的连续若干天中恰好下棋21盘。2021年7月22日第二章鸽巢原理和Ramsey定理1、题干提供的信息：一共11周2、约束条件：每周最多下12盘棋每天至少下1盘棋3、目标：连续若干天共下棋21盘4、解题途径：构造下棋盘数的部分分析：2021年7月22日第二章鸽巢原理和Ramsey定理证明:令b1，b2，…，b77分别为这11

7、周中他每天下棋的次数，并作部分和a1=b1,a2=b1+b2,…，a77=b1+b2+…+b77.2021年7月22日第二章鸽巢原理和Ramsey定理所以有1≤a1