《鸽巢原理ppt课件》由会员分享，可在线阅读，更多相关《鸽巢原理ppt课件（49页珍藏版）》请在金锄头文库上搜索。
1、第二章 鸽巢原理简单方式之一n假设有许多鸽子飞进缺乏够多的鸽巢内，那么假设有许多鸽子飞进缺乏够多的鸽巢内，那么至少一个鸽巢内被两个或两个以上的鸽子占据至少一个鸽巢内被两个或两个以上的鸽子占据n鸽巢原理简单方式之一：n定理2.1.1 假设n+1件物体被放入n个盒子，那么至少有一个盒子含有两件或更多物体简单运用n在13个人中必有两个人是同一个月份出生n设有n对夫妇，为保证可以有一对夫妇被选出，至少要从这2n个人中选出多少人？n n+1简单方式之二、三n假设将n个物体放入n个盒子，并且没有一个盒子为空，那么每个盒子恰好包含一个物体n假设将n个物体放入n个盒子，并且没有一个盒子中放入多于一个的物体，那
2、么每个盒子恰好包含一个物体鸽巢原理的笼统描画鸽巢原理的笼统描画令X和Y为两个有限集合，并有函数f: XY假设|X|Y|，那么f就不是一对一的；假设|X|Y|，且f是映上的，那么f就是一对一的；假设|X|Y|，且f是一对一的，那么f就是映上的复杂运用n给定m个整数a1, a2, am，那么存在整数k和l，满足0klm，使得ak+1+al可以被m整除复杂运用n从整数1, 2, ,200中，我们选择101个整数，证明：所选的数中必定存在两个数，使得其中一个可以被另一个整除中国剩余定理n我国古代数学名著中，记载这样一个问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。 这个
3、问题的解题思绪，被称为“孙子问题、“鬼谷算、“隔墙算、“韩信点兵等等。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
4、=qn+b的方式，这里p和q是两个整数问题nm只鸽子，n个鸽巢，那么至少有一个鸽巢里有不少于？只鸽子，能保证鸽子全部飞入鸽巢？n 引理：设k和n都是恣意的正整数，假设至少有kn+1只鸽子分配在n个鸽巢里，那么至少存在一个鸽巢中有至少k+1只鸽子n n 鸽巢原理的加强方式 定理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个盒子中，那么至少有一个
5、盒子含有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一篮
6、子水果有：苹果、香蕉、橘子，知篮子中每种水果的平均数目至少为8个，那么至少有一种水果的数目大于或等于8个。对否？平均原理之三n假设n个非负整数m1, m2, , mn的平均数至少等于r，那么这n个整数m1, m2, , mn至少有一个满足mir运用n证明：每个n2+1个实数构成的序列a1,a2,an2+1，或者含有长度为n+1的递增序列，或者含有长度为n+1的递减序列n即： n2+1个人排队，总能选出其中n+1个人向前一步，他们构成的新队列自左向右或者身高递增或者身高递减解题思绪n弄清题意n找出关键词：“长度，“递增，“递减n分析知的量词：“n2+1， “n，“ n+1n联络鸽巢原理，构建“鸽
7、巢和“鸽子n给出证明思索nT14nT15Ramsey定理 英国数学家、哲学家、英国数学家、哲学家、经济学家学家 (February 22, 1903 January 19, 1930) 简单方式n在6个或更多的人中，或者有3个人，他们中的每两个人都相互认识；或者有3个人，他们中的每两个人都相互不认识n证明：1.穷举法n 2.一个巧妙的方法！K6K3, K3nK1nK2nK3nK4nK5Kn:由n个物体配成的全部无序对的集合平面上n个点的全衔接图，且恣意三点不共线Kn的定义模型转换na, b认识：na, b不认识： 在6个人中，或者有3个人，他们中的每两个人都相互认识；或者有3个人，他们中的每两
8、个人都相互不认识平面上6个点，或者有3个点，它们中的每两个都相互红线相连；或者有3个点，它们中的每两个都相互蓝线相连即：K6K3, 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)，由鸽巢原理可知，至少有条边同色现将证明过程用判别树表示如下：证明
9、dr(v1)3?db(v1)3设(v1v2) (v1v3) (v1v4)为红边v2v3v4是红 ?v2v3v4是蓝 ?设( v2v3 )是红边v1v2v3是蓝v1v2v3是红YNNNYY设(v1v2) (v1v3) (v1v4)为蓝边设( v2v3 )是蓝边问题n在5个人中，或者有3个人，他们中的每两个人都相互认识；或者有3个人，他们中的每两个人都彼此不认识n K5K3，K3能否成立 ？n n6，能否会有类似的结论？推论nK9 的边用红蓝两色恣意着色，那么必有一个红色K4或一个蓝色K3 ，或者，必有一个蓝色K4或一个红色K3 n 引理：存在一个顶点vi至少关联4条蓝边或者6条红边n 证明：n
10、无妨设 db(v1) 4，可得如下判别树证明结论:n 证明db(v1)4?dr(v1)6设(v1v2) (v1v3) (v1v4)(v1v5)是4条蓝边设(v1v2) (v1v7)是6条红边K4(v2v3v4v5)是红K4 ?设(v2v3)是蓝边v1v2v3是蓝设v2v3v4是红K4(v1v2v3v4)是红K4YYYNNNK6(v2v7)中有蓝 ?问题n对于K8，能否存在一种涂色方案，使得必有一个红K4或一个蓝色K3 ？n K8 K4 ， K3？复习nRamsey定理：n 在6个或更多的人中，或者有3个人，他们中的每两个人都相互认识；或者有3个人，他们中的每两个人都相互不认识n K6 的边用红
11、蓝两色恣意着色，那么必有一个红K3或蓝K3n n K9 的边用红蓝两色恣意着色，那么必有一个红色K4或一个蓝色K3 ，或者，必有一个蓝色K4或一个红色K3 K6K3, K3思索nK18的边用红蓝两色恣意着色，那么必有一个红K4或一个蓝色K4n 证明：设18个顶点为v1 , v2 , , v18 ，那么从v1引出的17条边至少有条是同色的。n 无妨先假定为红色，从而可得下面的判别树证明命题证明dr(v1)9？db(v1)9设(v1v2) (v1v10)是红边K9(v2 v10)中有蓝K4？K10( v1v2 v10)中有红K4K9(v2 v10)中有红K4？K10( v1v2 v10)中有蓝K4
12、YN设(v1v2) (v1v10)是蓝边YN设v2v3v4是红YN设v2v3v4是蓝Ramsey定理的普通方式n假设m2，n2是两个整数，那么存在一个正整数p，使得KpKm, Knn 给定一个m和n，存在一个正整数p,使得假设Kp的边被涂成红色或蓝色，那么或者有一个红色的Km，或者有一个蓝色的Knn命题：假设KpKm, Kn，对qp， KqKm, Kn 亦成立！Ramsey数nRamsey数r(m, n)是使得KpKm, Kn成立的最小pn n 例如：r(3,3)=6，r(3,4)=9，r(4,4)=18问题nr(2,n) = ?n r(2,n) = nn把把Kn 的的边或者涂成或者涂成红色或
13、者涂成色或者涂成蓝色，那么，或者色，那么，或者Kn的某条的某条边是是红色的得到一个色的得到一个红K2，或者，或者Kn一一切的切的边都是都是蓝色的得到一个色的得到一个蓝Kn n r(2,n) n n假假设把把Kn-1的的边都涂成都涂成蓝色，那么既得不到色，那么既得不到红K2，也，也得不到得不到蓝Kn n r(2,n) n-1nr(m,2)=?n r(m,2)=mnr(m,n) = r(n,m)已探明的Ramsey数或它的界Ramsey定理的更普通方式n把两种颜色，推行到n种颜色：n对m12， m22， mk2这k个都是整数，存在p，使得KpKm1, Km2, Kmk成立n即：存在一个整数p，假设
14、Kp的每条边都涂为c1,ck等k种颜色之一，那么或者存在一个颜色为c1的Km1，或者,或者存在一个颜色为ck的Kmkn r(3,3,3) = 17Ramsey定理的更更普通方式n给定整数t 2，对m1 t， m2 t， mk t这k个都是整数，存在p，使得KpKtm1, Ktm2, Ktmk成立。其中， Ktm表示m个元素的集的t个元素的子集的集合n 即：存在p个元素的集，假设将集合的每一个t子集涂为c1,ck等k种颜色中的一种，那么或者存在m1个元素，这些元素的t子集都被涂为c1色，或者,或者存在mk个元素，这些元素的t子集都被涂为ck色nRamsey数：rt(m1,mk)命题推行n存在一个
15、集合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)=?n r1(m1,mk)= m1+ m2+mk-k+1Ramsey定理的意义n不能够存在完全无序的系统 n 在某种条件下，无论对一个大系统构造如何进展分割，总是可以得到人们预期想要得到的子系统构造意义n这里的系统即由相互关联的事物所组成，要研讨这种系统可以经过很多种方式进展讨论，但是“图是表达这种系统的最正确工具，由于图论正是讨论“事物及其“关系的一个数学工具。所以图论理所当然地成为研讨Ramsey实际的一个最重要的表达工具。Ramsey定理的运用运用运用运用nr4(5,m)，
