第二章 鸽巢原理.ppt

简单形式之一 如果有许多鸽子飞进不足够多的鸽巢内，那么至少一个鸽巢内被两个或两个以上的鸽子占据 简单应用 在13个人中必有两个人是同一个月份出生 设有n对夫妇，为保证能够有一对夫妇被选出，至少要从这2n个人中选出多少人？ n+1 简单形式之二、三 如果将n个物体放入n个盒子，并且没有一个盒子为空，那么每个盒子恰好包含一个物体 如果将n个物体放入n个盒子，并且没有一个盒子中放入多于一个的物体，那么每个盒子恰好包含一个物体 鸽巢原理的抽象描述 令X和Y为两个有限集合，并有函数f: X?Y 如果|X|?|Y|，则f就不是一对一的； 如果|X|＝|Y|，且f是映上的，则f就是一对一的； 如果|X|＝|Y|，且f是一对一的，则f就是映上的 复杂应用 给定m个整数a1, a2, ……am，则存在整数k和l，满足0≤kl≤m，使得ak+1+……+al能够被m整除 复杂应用 从整数1, 2, ……,200中，我们选择101个整数，证明：所选的数中必定存在两个数，使得其中一个可以被另一个整除 中国剩余定理 我国古代数学名著《孙子算经》中，记载这样一个问题： “今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何。” 这个问题的解题思路，被称为“孙子问题”、“鬼谷算”、“隔墙算”、“韩信点兵”等等。 明朝数学家程大位把这一解法编成四句歌诀：“三人同行七十（70）稀，五树梅花廿一（21）枝，七子团圆正月半（15）， 除百零五（105）便得知。” 《孙子算经》的“物不知数”题开创了一次同余式研究的先河，南宋数学家秦九韶在《数书九章》中提出了 “大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。中国古代数学的这一创造在西方数学史著作中被称为“中国剩余定理”。 存在性证明 令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是两个整数 问题 m只鸽子，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个非负整数m1, m2, ……, mn的平均数大于r-1,那么至少有一个整数大于或等于r 如果n个非负整数m1, m2, ……, mn的平均数小于r+1,那么至少有一个整数小于r+1 应用之一 一篮子水果有：苹果、香蕉、橘子，为保证篮子中或者至少8个苹果，或者至少6个香蕉，或者至少9个橘子，问放入篮子的水果的最小数目是多少？ 一篮子水果有：苹果、香蕉、橘子，为保证篮子中存在某种水果，它的数目至少为8个，问放入篮子的水果的最小数目是多少？ 一篮子水果有：苹果、香蕉、橘子，已知篮子中每种水果的平均数目多于8个，那么至少有一种水果的数目大于或等于9个。对否？ 一篮子水果有：苹果、香蕉、橘子，已知篮子中每种水果的平均数目至少为8个，那么至少有一种水果的数目大于或等于8个。对否？ 平均原理之三 如果n个非负整数m1, m2, ……, mn的平均数至少等于r，那么这n个整数m1, m2, ……, mn至少有一个满足mi≥r 应用 证明：每个n2+1个实数构成的序列a1,a2,…,an2+1，或者含有长度为n+1的递增序列，或者含有长度为n+1的递减序列 （即： n2+1个人排队，总能选出其中n+1个人向前一步，他们构成的新队列自左向右或者身高递增或者身高递减） 解题思路 弄清题意 找出关键词：“长度”，“递增”，“递减” 分析已知的量词：“n2+1”， “n”，“ n+1” 联系鸽巢原理，构建“鸽巢”和“鸽子” 给出证明 思考 T14 T15 Ramsey定理 简单形式 在6个（或更多的）人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都互相不认识 证明：1.穷举法 2.一个巧妙的方法！ Kn的定义 K1 模型转换 a, b认识： a, b不认识：