资源描述：
《组合数学-鸽巢原理讲义.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2021年7月17日第二章鸽巢原理和Ramsey定理第二章鸽巢原理和Ramsey定理§2.1鸽巢原理的最简单形式§2.2鸽巢原理的加强形式§2.3Ramsey定理2021年7月17日第二章鸽巢原理和Ramsey定理§2.1鸽巢原理的最简单形式鸽巢原理（抽屉原理），它指的是一个简单的事实：如果鸽子的数目比巢穴的数目多，那么至少要有一个鸽巢被两只或多只鸽子占据（若有n个鸽子巢，n+1只鸽子，则至少有一个巢内有至少有两只鸽子).2021年7月17日第二章鸽巢原理和Ramsey定理定理2.1.1若把n+1个物体放入n个盒子中，
2、则至少有一个盒子中有2个或更多的物体.证明:如果每个盒子中至多有一个物体，那么n个盒子中至多有n个物体，而我们共有n+1个物体，矛盾.故定理成立.2021年7月17日第二章鸽巢原理和Ramsey定理例2.1.1共有12个属相，今有13个人，则必有两人的属相相同.几个例子2021年7月17日第二章鸽巢原理和Ramsey定理例2.1.2有5双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能保证找到1双袜子？解根据定理2.1.1，共有n=5个盒子，每个盒子对应1双袜子.如果选择5+1=6只袜子，则必有两只袜子落入同一
3、个盒子中，即为一双袜子.因此我们至少从中选出6只袜子才能保证找到1双袜子.2021年7月17日第二章鸽巢原理和Ramsey定理例2.1.3对任意给定的52个整数，证明：其中必存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除.分析：①已知：52个数；②目标：找两个数，其和或差能被100整除；③方法：把52个物体放到51个盒子中，需要构造51个盒子；证明：对于任意一个整数，它除以100的余数显然有如下100种情况：0，1，2，3，……，99现在有任意给定的52个整数，需要构造51个盒子，即对这100个余
4、数进行分组，共51组：{0}，{1，99}，{2，98}，{3，97}，…，{49，51}，{50}.2021年7月17日第二章鸽巢原理和Ramsey定理例2.1.4一名象棋大师有11周时间准备一场锦标赛，他决定每天至少下一盘棋，为了不能太累一周中下棋的次数不能多于12盘.证明：他一定在此期间的连续若干天中恰好下棋21盘.分析：①已知：一共11周；每周最多下12盘棋；每天至少下1盘棋；②目标：连续若干天共下棋21盘；③方法：构造和的序列.2021年7月17日第二章鸽巢原理和Ramsey定理证明:令b1，b2，…，b77
5、分别为这11周中他每天下棋的次数，并作部分和a1=b1,a2=b1+b2,…，a77=b1+b2+…+b77.其中bi≥1(1≤i≤77)，且bi+bi+1+…+bi+6≤12(1≤i≤71)，则有1≤a1＜a2＜a3＜…＜a77≤12×11=132.(2.1.1)2021年7月17日第二章鸽巢原理和Ramsey定理考虑数列：a1,a2,…,a77,a1+21,a2+21,…,a77+21它们都在1与132+21=153之间，共有154项.由鸽巢原理知，其中必有两项相等.由(2.1.1)式知a1,a2,…,a77互不相
6、等，从而a1+21,a2+21,…,a77+21也互不相等，所以一定存在1≤i＜j≤77，使得aj=ai+21.21=aj-ai=(b1+b2+…+bi+bi+1+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+…+bj.2021年7月17日第二章鸽巢原理和Ramsey定理例2.1.5将一个矩形分成4行19列的网格，每个单元格涂1种颜色，有3种颜色可以选择，证明：无论怎样涂色，其中必有一个由单元格构成的矩形的4个角上的格子被涂上同一种颜色.分析：①已知：4行19列的网格，3种颜色；②目标：矩形的4个角涂同一种
7、颜色；证明：每一列有4行，但只有3种颜色，则必有两个单元格的颜色相同，其不同位置的组合有C(4,2)=6种，则一列中两个同色单元格的位置组合共有18种，而现在有19列，则无论怎样涂色，必有两列与图中的某一列相同，即各自所包含的两个同色单元格的位置相同、颜色相同.2021年7月17日第二章鸽巢原理和Ramsey定理题2.19在边长为2的正三角形中任取5个点，证明至少有两个点之间的距离不超过1.2021年7月17日第二章鸽巢原理和Ramsey定理2021年7月17日第二章鸽巢原理和Ramsey定理例2.1.6证明：任意n2
8、+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列.分析：①已知：由n2+1个实数组成的序列；②目标：递增或递减子序列的长度n+1.2021年7月17日第二章鸽巢原理和Ramsey定理证明：由题意，设Li是从ai开始的递减子序列的最大长度，Mi是从ai开始的递增子序列的最大长度，则对于i从
