软件2010组合数学—第二章鸽巢原理和Ramsey定理(1)

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

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

2、加强形式§2.3Ramsey定理2021年8月12日第二章鸽巢原理和Ramsey定理§2.1鸽巢原理的最简单形式鸽巢原理是组合学中最简单、最基本原理也叫抽屉原理(又称为或重叠原理或狄利克雷原理）。定理2.1.1若把n+1个物体放入n个盒子中，则至少有一个盒子中有2个或更多的物体2021年8月12日第二章鸽巢原理和Ramsey定理证明如果每个盒子中至多有一个物体，那么n个盒子中至多有n个物体，而我们共有n+1个物体，矛盾。故定理成立。鸽巢原理的集合描述形式：设有限集合A有n+1个元素，将A分划成n个不相交子集的并，则至少有一

3、个子集含有两个或两个以上的元素。定理是用群体的整体性表现出个体的某些特性，属于从宏观到微观的理论研究成果注意应用时要分清物品与盒子以及物体数与盒子总数。这个原理只能用来证明某种安排的存在性，而却不能找到具体满足要求的安排一般不能被推广到只存在n个(或更少)物体的情形。2021年8月12日第二章鸽巢原理和Ramsey定理例2.1.1共有12个属相，今有13个人，则必有两人的属相相同几个例子例2.1.2有5双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能保证找到1双袜子？2021年8月12日第二章鸽巢原理和Ramse

4、y定理解应用定理2.1.1，共有5个盒子，每个盒子对应1双袜子。如果选择5+1=6只袜子分别放到它所属那双袜子的盒子中，则必有两只袜子落入同一个盒子中，即为一双袜子。因此我们至少从中选出6只袜子才能保证找到1双袜子。本例实际上是知道n个盒子，而找n+1个物体的问题。2021年8月12日第二章鸽巢原理和Ramsey定理考试填空题：某个制造天平铁盘的工厂，由于设备与技术的原因，只能将生产的盘子的重量控制在m克到(m+0.l)克之间(m是己知常数)，现在需要制成重量相差不超过0.005克的两个铁盘来配制一架天平。则该工厂至少要生

5、产多少个铁盘，才能保证得到一对符合要求的铁盘。2021年8月12日第二章鸽巢原理和Ramsey定理例2.1.3对任意给定的52个整数，证明：其中必存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。2021年8月12日第二章鸽巢原理和Ramsey定理1、已知：52个整数，2、目标：找被100整数的两个数3、解题途径：把52个物体放到51个盒子中，需要构造51个盒子4、根据题干中要求的两个整数必须具备的性质构造盒子5、是否能够被100整除的关键在余数，那么一个整数除以100的余数为0，1，2，…，99两个整

6、数的和可以被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

7、组的话，因为一组有两个余数，余数相同则它们的差能被100整除，余数不同则它们的和能被100整除。2021年8月12日第二章鸽巢原理和Ramsey定理例2.1.4对从1～200的整数中选取101个数，证明：其中必存在两个整数，二者存在整除关系。证明设是被选出的101个整数，对任一，都可以唯一的写成如下形式：其中为整数，为奇数。例如：由于，所以只能取1，3，5，199共100个奇数，而共有101项，根据鸽巢原理，存在使得，不妨设，则，即能被整除。2021年8月12日第二章鸽巢原理和Ramsey定理例2.1.5一名象棋大师有11

8、周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累一周中下棋的次数不能多于12盘。证明：她一定在此期间的连续若干天中恰好下棋21盘。进一步思考：（1）能否把题中的21盘改为更少？（2）把题中的21盘改为22盘又如何？2021年8月12日第二章鸽巢原理和Ramsey定理1、题干提供的信息：一共11