《鸽巢原理》PPT课件

《《鸽巢原理》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章鸽巢原理简单形式之一如果有许多鸽子飞进不足够多的鸽巢内，那么至少一个鸽巢内被两个或两个以上的鸽子占据鸽巢原理简单形式之一：定理2.1.1如果n+1件物体被放入n个盒子，则至少有一个盒子含有两件或更多物体简单应用在13个人中必有两个人是同一个月份出生设有n对夫妇，为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人？n+1简单形式之二、三如果将n个物体放入n个盒子，并且没有一个盒子为空，那么每个盒子恰好包含一个物体如果将n个物体放入n个盒子，并且没有一个盒子中放入多于一个的物体，那么每个盒子恰好包含一个物体鸽巢原理的抽象描

2、述令X和Y为两个有限集合，并有函数f:XY如果

3、X

4、

5、Y

6、，则f就不是一对一的；如果

7、X

8、＝

9、Y

10、，且f是映上的，则f就是一对一的；如果

11、X

12、＝

13、Y

14、，且f是一对一的，则f就是映上的复杂应用给定m个整数a1,a2,……am，则存在整数k和l，满足0≤k

15、剩二，问物几何。”这个问题的解题思路，被称为“孙子问题”、“鬼谷算”、“隔墙算”、“韩信点兵”等等。明朝数学家程大位把这一解法编成四句歌诀：“三人同行七十（70）稀，五树梅花廿一（21）枝，七子团圆正月半（15），除百零五（105）便得知。”《孙子算经》的“物不知数”题开创了一次同余式研究的先河，南宋数学家秦九韶在《数书九章》中提出了“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。中国古代数学的这一创造在西方数学史著作中被称为“中国剩余定理”。存在性证明令m和n为两个互素的正整数，并令a和b为两整数，且0≤a≤m-

16、1，0≤b≤n-1，于是存在一个正整数x，使得x除以m的余数为a，并且x除以n的余数为b，即x可以写成x=pm+a同时又可以写成x=qn+b的形式，这里p和q是两个整数问题m只鸽子，n个鸽巢，则至少有一个鸽巢里有不少于？？只鸽子，能保证鸽子全部飞入鸽巢？引理：设k和n都是任意的正整数，若至少有kn+1只鸽子分配在n个鸽巢里，则至少存在一个鸽巢中有至少k+1只鸽子鸽巢原理的加强形式定理2.2.1令q1,q2,……,qn为正整数，如果将q1+q2+…+qn-n+1个物体放入n个盒子内，那么，或者第一个盒子至少含有q1个物体，或者第二个盒

17、子至少含有q2个物体，……，或者第n个盒子至少含有qn个物体推广如果q1,q2,……,qn都等于同一个整数r，则如果n(r-1)+1个物体放入n个盒子中，那么至少有一个盒子含有r个或更多的物体平均原理之一、二如果n个非负整数m1,m2,……,mn的平均数大于r-1,那么至少有一个整数大于或等于r如果n个非负整数m1,m2,……,mn的平均数小于r+1,那么至少有一个整数小于r+1应用之一一篮子水果有：苹果、香蕉、橘子，为保证篮子中或者至少8个苹果，或者至少6个香蕉，或者至少9个橘子，问放入篮子的水果的最小数目是多少？一篮子水果有：苹

18、果、香蕉、橘子，为保证篮子中存在某种水果，它的数目至少为8个，问放入篮子的水果的最小数目是多少？一篮子水果有：苹果、香蕉、橘子，已知篮子中每种水果的平均数目多于8个，那么至少有一种水果的数目大于或等于9个。对否？一篮子水果有：苹果、香蕉、橘子，已知篮子中每种水果的平均数目至少为8个，那么至少有一种水果的数目大于或等于8个。对否？平均原理之三如果n个非负整数m1,m2,……,mn的平均数至少等于r，那么这n个整数m1,m2,……,mn至少有一个满足mi≥r应用证明：每个n2+1个实数构成的序列a1,a2,…,an2+1，或者含有长度为

19、n+1的递增序列，或者含有长度为n+1的递减序列（即：n2+1个人排队，总能选出其中n+1个人向前一步，他们构成的新队列自左向右或者身高递增或者身高递减）解题思路弄清题意找出关键词：“长度”，“递增”，“递减”分析已知的量词：“n2+1”，“n”，“n+1”联系鸽巢原理，构建“鸽巢”和“鸽子”给出证明思考T14T15Ramsey定理英国数学家、哲学家、经济学家(February22,1903–January19,1930)简单形式在6个（或更多的）人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都互相不

20、认识证明：1.穷举法2.一个巧妙的方法！K6K3,K3K1K2K3K4K5Kn:由n个物体配成的全部无序对的集合平面上n个点的全连接图，且任意三点不共线Kn的定义模型转换a,b认识：a,b不认识：在6个人中，或者有3个人，他们中的每