您好,欢迎访问三七文档
哈尔滨工程大学课件沈晶制作组合数学—鸽巢原理哈尔滨工程大学课件沈晶制作有n+1只鸽子飞进n个巢中,那么至少有一个鸽巢中有两只或两只以上的鸽子。反过来,要想保证至少有一个鸽巢中有两只或两只以上的鸽子,至少要有n+1只鸽子又称为抽屉原理鞋盒原理鸽巢原理(简单形式)哈尔滨工程大学课件沈晶制作应用举例例1:若把n+1个物体放入n个盒子中,则至少有一个盒子中有2个或更多的物体.证明:如果每个盒子中至多有一个物体,那么n个盒子中至多有n个物体,而我们共有n+1个物体,矛盾.故定理成立.哈尔滨工程大学课件沈晶制作例2:在边长为1的等边三角形内任取5个点,试证其中至少有两点,期间距离小于1/2。证明:把边长为1的三角形分成四个边长为1/2的三角形,则这5点中必有两点落在同一个小三角形中小三角形中任意两点间的距离都小于1/2应用举例哈尔滨工程大学课件沈晶制作应用举例例3:有5双不同的袜子混在一个抽屉里,我们至少从中选出多少只袜子才能保证找到1双袜子?解共有n=5个盒子,每个盒子对应1双袜子.如果选择5+1=6只袜子,则必有两只袜子落入同一个盒子中,即为一双袜子.因此我们至少从中选出6只袜子才能保证找到1双袜子.哈尔滨工程大学课件沈晶制作鸽巢原理(加强形式)设m1,m2,…,mn都是正整数,有m1+m2+…+mn–n+1只鸽子飞进n个巢中,则:或者第1个鸽巢,至少有m1只鸽子或者第2个鸽巢,至少有m2只鸽子……或者第n个鸽巢,至少有mn只鸽子哈尔滨工程大学课件沈晶制作应用举例例4:一个筐中有苹果、香蕉和橙子3种水果,为保证筐中或者至少有8个苹果,或者至少有6个香蕉,或者至少有9个橙子,则放入筐中的水果数目至少为多少?解:211857哈尔滨工程大学课件沈晶制作例5:一抽屉中有20件衬衫,其中4件蓝色,7件灰色,9件红色。试问若从中随意取多少件可保证有4件为同色?若从中随意取多少件可保证有6件为同色?解:应用举例101333151554哈尔滨工程大学课件沈晶制作应用举例例6:61个同学中,至少有6人的生日在同一个月份。证明:60/12=5哈尔滨工程大学课件沈晶制作鸽巢原理鸽巢原理Ramsey定理哈尔滨工程大学课件沈晶制作Ramsey定理Ramsey定理既是鸽巢原理的应用,也是鸽巢原理的加强形式的推广。Ramsey定理始见于Ramsey于1930年发表的论文《OnaProblemofFormalLogic》,最开始用于解决一阶谓词逻辑判定问题。FrankPlumptonRamsey(弗兰克·拉姆齐)是英国著名数学家、哲学家、逻辑学家、经济学家,1903.2.22出生,1930.1.19因病英年早逝。Ramsey哈尔滨工程大学课件沈晶制作Ramsey问题6个人中至少有3个人或者相互认识,或者相互不认识。用红、蓝两色涂K6的边,则必然要么出现一个红色K3,要么出现一个蓝色K3,简记为K6K3,K3。(注:Kp表示p阶完全图)。哈尔滨工程大学课件沈晶制作Ramsey问题的证明考虑任意一点,它接触到5条边根据鸽巢原理(相当于5只鸽子飞进红蓝2个巢),这5条边或者至少有3条边是红色,或者至少有3条边是蓝色。如果这5条边中有3条边是蓝色(红色同理),令这3条蓝边分别将p点与a、b、c三点相连。pabc考虑将a、b、c两两相连的边。如果这些边都是红边,那么abc就确定了一个红色K3,如果它们中的一条边是蓝色的(如bc),那么pbc就确定一个蓝色K3。哈尔滨工程大学课件沈晶制作已经寻找到的一些Ramsey数哈尔滨工程大学课件沈晶制作Ramsey数的性质命题1定理2对任意的正整数a≥2,b≥2,有推论aaraarabrbar)2,()1,(),(),()1,(),1(),(barbarbar12),(ababar哈尔滨工程大学课件沈晶制作谢谢!
本文标题:鸽巢原理
链接地址:https://www.777doc.com/doc-3262373 .html