《鸽巢原理》PPT课件.ppt

第二章 鸽巢原理简单形式之一n如果有许多鸽子飞进不足够多的鸽巢内，那么如果有许多鸽子飞进不足够多的鸽巢内，那么至少一个鸽巢内被两个或两个以上的鸽子占据至少一个鸽巢内被两个或两个以上的鸽子占据n鸽巢原理简单形式之一：定理2.1.1 如果如果n+1件物体被放件物体被放入入n个盒子，则至少有一个个盒子，则至少有一个盒子含有两件或更多物体盒子含有两件或更多物体简单应用n在13个人中必有两个人是同一个月份出生n设有n对夫妇，为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人？ n+1简单形式之二、三n如果将n个物体放入n个盒子，并且没有一个盒子为空，那么每个盒子恰好包含一个物体n如果将n个物体放入n个盒子，并且没有一个盒子中放入多于一个的物体，那么每个盒子恰好包含一个物体鸽巢原理的抽象描述鸽巢原理的抽象描述令X和Y为两个有限集合，并有函数f: XYn如果|X||Y|，则f就不是一对一的；n如果|X|＝|Y|，且f是映上的，则f就是一对一的；n如果|X|＝|Y|，且f是一对一的，则f就是映上的复杂应用n给定m个整数a1, a2, ……am，则存在整数k和l，满足0≤k

知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何 这个问题的解题思路，被称为“孙子问题”、“鬼谷算”、“隔墙算”、“韩信点兵”等等n明朝数学家程大位把这一解法编成四句歌诀：“三人同行七十（三人同行七十（70）稀，）稀，五树梅花廿一（五树梅花廿一（21）枝，七子团圆正月半（）枝，七子团圆正月半（15），）， 除百零五（除百零五（105）便）便得知n《孙子算经》的“物不知数”题开创了一次同余式研究的先河，南宋数学家秦九韶在《数书九章》中提出了 “大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序中国古代数学的这一创造在西方数学史著作中被称为“中国剩余定理”存在性证明n令m和n为两个互素的正整数，并令a和b为两整数，且0 ≤ a ≤ m-1，0 ≤ b ≤ n-1，于是存在一个正整数x，使得x除以m的余数为a，并且x除以n的余数为b，即x可以写成x=pm+a同时又可以写成x=qn+b的形式，这里p和q是两个整数问题nm只鸽子，n个鸽巢，则至少有一个鸽巢里有不少于？？只鸽子，能保证鸽子全部飞入鸽巢？ 引理：设k和n都是任意的正整数，若至少有kn+1只鸽子分配在n个鸽巢里，则至少存在一个鸽巢中有至少k+1只鸽子 鸽巢原理的加强形式 定理2.2.1 令q1, q2, ……, qn为正整数，如果将q1+q2+…+qn-n+1个物体放入n个盒子内，那么，或者第一个盒子至少含有q1个物体，或者第二个盒子至少含有q2个物体，……，或者第n个盒子至少含有qn个物体推广 如果q1, q2, ……, qn都等于同一个整数r， 则 如果n(r-1)+1个物体放入n个盒子中，那么至少有一个盒子含有r个或更多的物体平均原理之一、二n如果n个非负整数m1, m2, ……, mn的平均数大于r-1,那么至少有一个整数大于或等于rn如果n个非负整数m1, m2, ……, mn的平均数小于r+1,那么至少有一个整数小于r+1应用之一n一篮子水果有：苹果、香蕉、橘子，为保证篮子中或者至少8个苹果，或者至少6个香蕉，或者至少9个橘子，问放入篮子的水果的最小数目是多少？n一篮子水果有：苹果、香蕉、橘子，为保证篮子中存在某种水果，它的数目至少为8个，问放入篮子的水果的最小数目是多少？n一篮子水果有：苹果、香蕉、橘子，已知篮子中每种水果的平均数目多于8个，那么至少有一种水果的数目大于或等于9个。

对否？n一篮子水果有：苹果、香蕉、橘子，已知篮子中每种水果的平均数目至少为8个，那么至少有一种水果的数目大于或等于8个对否？平均原理之三n如果n个非负整数m1, m2, ……, mn的平均数至少等于r，那么这n个整数m1, m2, ……, mn至少有一个满足mi≥r应用n证明：每个n2+1个实数构成的序列a1,a2,…,an2+1，或者含有长度为n+1的递增序列，或者含有长度为n+1的递减序列（即： n2+1个人排队，总能选出其中n+1个人向前一步，他们构成的新队列自左向右或者身高递增或者身高递减）解题思路n弄清题意n找出关键词：“长度”，“递增”，“递减”n分析已知的量词：“n2+1”， “n”，“ n+1”n联系鸽巢原理，构建“鸽巢”和“鸽子”n给出证明思考nT14nT15Ramsey定理 英国数学家英国数学家、哲学哲学家、经经济学济学家 (February 22, 1903 – January 19, 1930) 简单形式n在6个（或更多的）人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都互相不认识证明：1.穷举法 2.一个巧妙的方法！K6K3, K3nK1nK2nK3nK4nK5Kn:由n个物体配成的全部无序对的集合平面上n个点的全连接图，且任意三点不共线Kn的定义模型转换na, b认识：na, b不认识： 在6个人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都互相不认识平面上6个点，或者有3个点，它们中的每两个都互相红线相连；或者有3个点，它们中的每两个都互相蓝线相连即：K6K3, K3转换后的问题n无论K6的边用红色和蓝色如何去涂，总有一个红K3（原始的6个点中有3个点，它们之间的3条线段均被着成红色）或蓝K3（原始的6个点中有3个点，它们之间的3条线段均被着成蓝色），简而言之，总有一个单色的三角形证明 设K6的顶点集为{v1 , v2 , ··· , v6 }，dr(vi)表示与顶点 vi 关联的红色边的条数，db(vi)表示与 vi 关联的蓝色边的条数．在K6 中，有dr(vi)＋ db(vi)＝５，由鸽巢原理可知，至少有３条边同色．　　现将证明过程用判断树表示如下：证明dr(v1)≥3?db(v1)≥3设(v1v2) (v1v3) (v1v4)为红边△v2v3v4是红△ ?△v2v3v4是蓝△ ?设( v2v3 )是红边△v1v2v3是蓝△△v1v2v3是红△√√YNNNYY设(v1v2) (v1v3) (v1v4)为蓝边设( v2v3 )是蓝边问题n在5个人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都彼此不认识 K5→K3，K3是否成立 ？？ n≥6，是否会有相似的结论？推论nK9 的边用红蓝两色任意着色，则必有一个红色K4或一个蓝色K3 ，或者，必有一个蓝色K4或一个红色K3 引理：存在一个顶点vi至少关联4条蓝边或者6条红边 证明： 不妨设 db(v1) ≥4，可得如下判断树证明结论: 证明db(v1)≥4?dr(v1)≥6设(v1v2) (v1v3) (v1v4)(v1v5)是4条蓝边设(v1v2) ··· (v1v7)是6条红边K4(v2v3v4v5)是红K4 ?设(v2v3)是蓝边△v1v2v3是蓝△设△v2v3v4是红△K4(v1v2v3v4)是红K4√√YYYNNNK6(v2···v7)中有蓝△ ?问题n对于K8，是否存在一种涂色方案，使得必有一个红K4或一个蓝色K3 ？？ K8 → K4 ， K3？？复习nRamsey定理： 在6个（或更多的）人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都互相不认识 K6 的边用红蓝两色任意着色，则必有一个红K3或蓝K3 K9 的边用红蓝两色任意着色，则必有一个红色K4或一个蓝色K3 ，或者，必有一个蓝色K4或一个红色K3 K6K3, K3思考nK18的边用红蓝两色任意着色，则必有一个红K4或一个蓝色K4 证明：设18个顶点为v1 , v2 , ··· , v18 ，那么从v1引出的17条边至少有９条是同色的。

不妨先假定为红色，从而可得下面的判断树证明命题证明dr(v1)≥9？db(v1)≥9设(v1v2) ··· (v1v10)是红边K9(v2 ··· v10)中有蓝K4？K10( v1v2 ···v10)中有红K4K9(v2 ··· v10)中有红K4？K10( v1v2 ···v10)中有蓝K4YN设(v1v2) ··· (v1v10)是蓝边Y√N设△v2v3v4是红△Y√N设△v2v3v4是蓝△Ramsey定理的一般形式n如果m≥2，n≥2是两个整数，则存在一个正整数p，使得KpKm, Kn 给定一个m和n，存在一个正整数p,使得如果Kp的边被涂成红色或蓝色，那么或者有一个红色的Km，或者有一个蓝色的Kn命题命题：如果KpKm, Kn，对q≥p， KqKm, Kn 亦成立！Ramsey数nRamsey数r(m, n)是使得KpKm, Kn成立的最小p 例如：r(3,3)=6，r(3,4)=9，r(4,4)=18问题nr(2,n) = ?? r(2,n) = nØ把Kn 的边或者涂成红色或者涂成蓝色，那么，或者Kn的某条边是红色的（得到一个红K2），或者Kn所有的边都是蓝色的（得到一个蓝Kn ） —— r(2,n) ≤n Ø如果把Kn-1的边都涂成蓝色，则既得不到红K2，也得不到蓝Kn —— r(2,n) > n-1nr(m,2)=?? r(m,2)=mnr(m,n) = r(n,m)已探明的Ramsey数或它的界Ramsey定理的更一般形式n把两种颜色，推广到n种颜色：对m1≥2， m2≥2，……， mk≥2这k个都是整数，存在p，使得KpKm1, Km2, ……Kmk成立即：存在一个整数p，如果Kp的每条边都涂为c1,…,ck等k种颜色之一，那么或者存在一个颜色为c1的Km1，或者,……,或者存在一个颜色为ck的Kmk r(3,3,3) = 17Ramsey定理的更更一般形式n给定整数t ≥ 2，对m1 ≥ t， m2 ≥ t，……， mk ≥ t这k个都是整数，存在p，使得KpKtm1, Ktm2, ……Ktmk成立。

其中， Ktm表示m个元素的集的t个元素的子集的集合 即：存在p个元素的集，如果将集合的每一个t子集涂为c1,…,ck等k种颜色中的一种，那么或者存在m1个元素，这些元素的t子集都被涂为c1色，或者,……,或者存在mk个元素，这些元素的t子集都被涂为ck色nRamsey数：rt(m1,……,mk)命题推广n存在一个集合S，如果将集合的每一个t子集分为c1,…,ck等k类中的一种，那么只要|S| ≥ rt(m1,……,mk) ，就满足：或者存在m1个元素，这些元素的t子集都是c1类，或者,……,或者存在mk个元素，这些元素的t子集都是ck类.Ramsey定理是鸽巢原理的推广n当t=1，即：存在p个元素的集，如果将集合的每一个元素边涂为c1,…,ck等k种颜色中的一种，那么或者存在m1个元素，这些元素的都被涂为c1色，或者,……,或者存在mk个元素，这些元素都被涂为ck色.nr1(m1,……,mk)=?? r1(m1,……,mk)= m1+ m2+…+mk-k+1Ramsey定理的意义n不可能存在完全无序的系统 在某种条件下，无论对一个大系统（结构）如何进行分割，总是能够得到人们预期想要得到的子系统（结构）意义n这里的系统即由相互关联的事物所组成，要研究这种系统可以通过很多种方式进行探讨，但是“图”是表达这种系统的最佳工具，因为图论正是讨论“事物”及其“关系”的一个数学工具。

所以图论理所当然地成为研究Ramsey理论的一个最重要的表达工具Ramsey定理的应用应用应用应用n≥r4(5,m)，。