第二章鸽巢原理习题课.ppt
- 文档编号:18700177
- 上传时间:2023-09-30
- 格式:PPT
- 页数:30
- 大小:420KB
第二章鸽巢原理习题课.ppt
《第二章鸽巢原理习题课.ppt》由会员分享,可在线阅读,更多相关《第二章鸽巢原理习题课.ppt(30页珍藏版)》请在冰点文库上搜索。
组合数学课件,制作授课:
王继顺2013.9.3,第2章小结
(1),本章小结,本章讨论了鸽笼原理及其推广,Ramsey数及其性质,Ramsey定理以及一些有趣的应用。
鸽笼原理是重要的组合基本原理之一。
重点是:
(1)鸽笼原理的正确使用。
这是需要一定的技巧的,关键在于认清“鸽子”(放进盒子的物体)并制造“鸽笼”。
而制造“鸽笼”的依据是:
“待证命题成立,蕴涵有两只鸽子在同一鸽笼”。
(2)鸽笼原理的加强形式有多种说法,其中关于算术平均的说法应用尤广,它告诉我们,当m/nr时,若把m个物体放入n个盒子,那么至少有一个盒子有r+1个物体。
运用它解题的关键仍然是正确的设置“盒子”。
第2章小结(3),本章小结,(3)Ramsey定理,Ramsey数Ramsey定理的性质可以概述为“任何一个足够大的结构中必定包含有一个给定大小的规则子结构”。
在解有关Ramsey定理及其应用的问题时,最重要的是正确理解定理意义,特别是r=2时定理的几种形象的说法。
在解题时,则要正确地设计一个集合,该集合分成哪几个部分,正确的确定a1,a2,am以及r分别体现在哪些已知量或已知事实中。
如果从更高的角度看问题,有关鸽笼原理和Ramsey定理的应用问题的解法都是模型化归方法。
即把实际问题化归到“鸽子,鸽笼”的模式,化归到“一个集合的r子集分类”的模式的方法。
1.鸽巢原理,1.1鸽巢原理的简单形式若有n+1只鸽子飞到n个鸽巢里面,则至少有一个鸽巢里至少有两只鸽子。
1.2鸽巢原理的加强形式,注:
n+1为结论成立的最小数。
将q1q2qnn1个物品放入n个抽屉中,则至少存在某个抽屉i(1in),使得这个抽屉里至少有qi个物品。
注:
q1q2qnn1为结论成立的最小数,记为N(q1,q2,qn;1)。
显然,当q1=q2=qn=2时,加强形式即为简单形式。
即N(q1,q2,qn;1)=q1+q2+qn-n+1.,鸽巢原理与Ramsey定理习题课,推论1n(r-1)1只鸽子飞入n个巢里,则至少有一个鸽巢里至少有r只鸽子。
当qi=r时,得:
推论3:
设m1,m2,mn均为正整数,且满足,则m1,m2,mn中至少有一个数不小于r。
推论2:
m只鸽子飞入n个巢里,则至少有一个鸽巢里至少有只鸽子,其中是不小于的最小整数。
2鸽巢的构造及其应用,虽然鸽巢原理十分简单明了,但不是所有的问题都一眼就可以看出什么是鸽子,什么是鸽巢。
在应用它的时候却涉及很多技巧,这是利用鸽巢原理解题的魅力所在。
常用的构造鸽巢的方法有:
利用整数分组、余数分类,划分集合,分割区间、分割图形,利用染色等。
下面给出几类常用的构造鸽巢的方法。
2.1利用整数分组构造“鸽巢”,例1试证明从1,2,kn中选n+1个数,总存在2个数,它们之间最多相差k-1。
证明:
把1,2,kn分为n部分1,2,3,,k,k+1,k+2,2k,(n-1)k+1,(n-1)k+2,kn,即做n个鸽巢,从中任选n+1个数,由鸽巢原理,必有2个数选在同一个鸽巢中,所以它们的差最大为k-1。
路易波萨是匈牙利数学家,在他11岁时匈牙利大数学家厄杜斯给他出了个问题:
“如果你手头上有n+1个整数,这些整数是小于或等于2n的,那么你一定会有一对数是互素的。
你知道这是什么原因吗?
”波萨仅思考了半分钟就巧妙地回答了这个问题。
例2在一条笔直的马路上种树,从起点起,每隔1米种一棵数。
如果把三块“爱护树木”的小牌分别挂在三棵树上,那么不管怎么挂,至少有两棵挂牌的树它们之间的距离是偶数(以米为单位)。
解从起点开始给每课树编号,树上的号码依次为1,2,3,n,把这些号码分为奇数和偶数两类,当作两个鸽巢,,把三块牌分别挂在三棵树上,那么不管,怎么挂,这三棵挂牌的树至少有两棵树的号码同为奇数或偶数,而这两棵树的差必为偶数,,所以至少有两棵挂牌的树它们之间的距离是偶数(以米为单位)。
2.2利用划分图形构造“鸽巢”,例1边长为1的正方形中,任意放入9个点,求证这9个点中任取3个点组成的三角形中,至少有一个的面积不超过.,解:
将边长为1的正方形等分成边长为1/2的四个小正方形,视这四个正方形为鸽巢,9个点任意放入这四个正方形中,由鸽巢原理必有三点落入同一个正方形内.现特别取出这个正方形来加以讨论.,图1,把落在这个正方形中的三点记为D、E、F.如图1,通过这三点中的任意一点(如E)作正方形边平行线,SDEFSDEGSEFG,所以,结论成立。
如果8个点无一个在圆心上,可将圆分成7个相等的扇形,由鸽巢原理,这8个点至少有两个在同一个扇形内,则这两点之间的距离小于半径。
例2在圆内(包刮圆周)有8个点,则其中必有两个点,它们之间的距离小于圆的半径。
证明分两种情况考虑。
2.如果8个点有一个点在圆心,可将圆分成6个相等的扇形,如图,,取扇形OA1A2不包含OA2,扇形OA2A3不包含OA3,扇形OA6A1不包含OA1,由鸽巢原理,余下的7个点,至少有两个在同一个扇形内,则这两点之间的距离小于半径。
由于圆上相邻两点Ai,Aj间的弦长恰好为圆的半径,所以,弦长:
在边长为1的正方形内任取5个点,则其中至少有两点,它们之间的距离不超过,2.证明:
(1)在一边长为1的三角形中任取10个点,则其中至少有两点,它们之间的距离不超过1/3.
(2)确定mn,使得在一边长为1的三角形中任取mn个点,则其中至少有两点,它们之间的距离不超过1/n.,类似这样的问题还有不少。
2.3利用余数分类构造“鸽巢”,例试证明任意给定52个整数,它们之中必有2个数,其和或差是100的倍数(即被100整除)。
证明:
任意一个整数a除以100产生的余数为0,1,2,99共100种。
用a1,a2,a52表示这52个整数,ai除以100产生的余数记为ri(i=1,2,52)。
由鸽巢原理,这52个整数分别除以100产生的52个余数r1,r2,r52中必有两个余数落在同一组中,,我们现在用0,1,2,,99这100个余数来构造鸽巢,将它们分为51组,构造出51个鸽巢:
0,1,99,2,98,49,51,50,即存在两个数,它们的和或差能被100整除。
若这两个余数落在0或50中,则它们的和及,差都能被100整除。
若这两个余数落在剩下的49组中的一组,当余数相同,时,它们的差被100整除,当余数不同时,它们的和被100整除,,类似这样的例子也有不少。
这个问题的一般提法任意给定n+2个整数,它们之中必有2个数,其和或差是2n的倍数。
1.任取n+1个正整数,求证在这n+1个数中必有两个数它们之差被n整除.,2.任意给出2011个正整数证明必存在正整数,证明构造部分和序列,则有如下两种可能:
(i)存在整数h(1h2011),使得.此时,取k=0,l=h即满足题意.,(ii)对任一整数i,均有.令,,由鸽巢原理知,存在整数,使得.,不妨设lk,则,综合(i)和(ii),即知题设结论成立.,2.4利用分割区间来构造“鸽巢“,例一个孩子每天至少看一个小时电视,共看7周,每周看电视从不超过11小时,证明:
在此期间存在连续若干天这个孩子恰好看电视20个小时。
(设这个孩子每看电视时间为整数个小时),证明设这个孩子7周内每天看电视的时间分别为a1,a2,a49小时,现在构造出数列an的前n项和的数列s1=a1,s2=a1+a2,s49=a1+a2+a49,则有:
1s1s2s3s49117=77,而序列s1+20,s2+20,,s49+20也是一个严格的递增序列,,且有21s1+20s2+20s49+2077+20=97,,考虑数列,它共有98项,且都在1至97中取值,根据鸽巢原理,必定存在两项相等。
由于前49项和后49项又分别是严格递增的,因此必然存在一个i和j,使得si=sj+20(ij),即si-sj=20,从而这个孩子从j+1天起到第i天的时间里恰好看电视20个小时。
类似这样的例子还有不少。
1.一个乒乓球手有37天时间准备一场比赛,他决定每天至少打1场球,37天至多打60场球,证明:
在此期间存在连续若干天他恰好打了21场球。
2.一个学生解数学题100天,每天至少解一道题,每10天至多解17道题,证明:
在此期间存在连续若干天他恰好解了29道题.那么是否存在连续若干天他恰好解了30道题。
3.在(0,1区间上任取5个点,则必有两个点它们的距离小于1/4。
4.n+1个实数xi满足0xi1(i=1,2,n+1),求证这n+1个实数中必存在两个数xi,xj,使得,由于1ai200,所以ri(1i101)只能取1,3,5,199这100个奇数,而r1,r2,r101共有101项,由鸽巢原理知,存在1ij101,使得,ri=rj,,不妨设sisj,则,即aj能被ai整除.,2.5利用化分集合来构造“鸽巢”,例试证明在1到200个自然数中任取101个数,一定存在两个数,其中的一个数是另一个数的整数倍。
证明:
设a1,a2,a101是被选出的101个整数,对任一ai,都可以唯一地写成如下的形式:
其中,si为整数,ri为奇数.,整数,推论3的应用.,例1把1至10这十数字随机的排成一个圆圈,证明必有一个三相邻数字之和大于等于17,证明把1至10这十个数字随机排成一个圆圈,从中任取三个相邻数字的方法有10种,设这10种三个相邻数字之和分别为m1,m2,m10,则有,m1+m2+m10=3(1+2+10)=,由推论3,必存在mi(0i10),使得mi17,即问题得证,例2设有大小两个圆盘,每个都划分成大小相等的200个小扇形,在大盘上任选100个小扇形漆成黑色,其余的100个小扇形漆成白色,而将小盘上的200个小扇形任意漆成黑色或白色.现将大小两只圆盘的中心重合,转动小盘使小盘上的每个扇形含在大盘上的小扇形之内.证明:
有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色.,证明:
由条件,固定大盘转动小盘共有200个不同的位置,设mi表示在第i个位置时,大、小扇形同色的个数(i=1,2,200),,只要证明,对小盘上的每一个扇形,由着色的条件,旋转一周(200个位置),与大扇形同色的个数为100个,所以200个小扇形在旋转一周同色的个数共有100200=20000个.,结论成立.,即可.,3.鸽巢原理在国内外数学竞赛中的应用,中学数学竞赛中,鸽巢原理常常作为一种处理问题的工具,多用于组合问题,在一些代数与几何问题中亦有应用。
鸽巢原理及其简单形式多用于解答存在性问题,应用鸽巢原理解题时,关键是构造适合的鸽巢。
下面给出一些利用鸽巢原理解决的数学竞赛题。
例1(北京市数学竞赛复赛试题)将910瓶红、蓝墨水,排成130行,每行7瓶。
证明:
不论怎样排列,红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种:
1至少三行完全相同;2至少有两组(四行),每组的两行完全相同。
证明:
910瓶红、蓝墨水,排成130行,每行7瓶。
每行中的7个位置中的每个位置都有红、蓝两种可能,因而总计共有27=128种不同的行式(当且仅当两行墨水瓶颜色及次序完全相同时称为“行式”相同)。
依鸽巢原理可知,在130行中必有两行(记为A,B)“行式”相同。
在除A、B外的其余128行中若有一行P与A(B)“行式”相同,则P,A,B满足“至少有三行完全相同”,结论成立;在除A,B外的其余128行中若没有与A(B)行式相同者,则128行至多有127种不同的行式,依鸽巢原则,必有两行(不妨记为C、D)行式相同,这样便找到了(A,B)、(C,D)两组(四行),每组两行完全相同,结论成立。
例2(1995年全国高中数学联赛试题)将平面上每个点以红、蓝两色之一着色,证明:
存在这样的两个相似三角形,它们的相似比为1995,并且每一个三角形的三个顶点同色。
证明:
如图,作两个半径分别为1和1995的同心圆,在内圆上任取9个点,必有5点同色,记为A1,A2,A3,A4,A5。
如图所示,连半径0Ai交大圆于Bi(i=1,2,3,4,5),对B1,B2,B3,B4,B5,必有3点同色,记为Bi,Bj,Bk,则BiBjBk与AiAjAk为三顶点同色的相似三角形,相似比等于1995,所以结论成立.,例3(美国普特南数学竞赛题),在坐标平面上任取五个整点(该点的横纵坐标都取整数),证明其中一定存在两个整点,它们的连线中点仍是整点。
证明欲使坐标平面两点(x1,y1)、(x2,y2)的中点坐标是整数,必须而且只须x1与x2,y1与y2的奇偶性相同。
坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种:
(奇数、奇数),(偶数,偶数),(奇数,偶数),(偶数,奇数)以此构造四个“鸽巢”,则在坐标平面上任取五个整点,那么至少有两个整点,属于同一个“鸽巢”,因此它们连线的中点就必是整点。
我们可以把整点的概念推广:
如果(x1,x2,xn)是n维(元)有序数组,且x1,x2,xn中的每一个数都是整数,则称(x1,x2,xn)是一个n维整点(整点又称格点)。
如果对所有的n维整点按每一个xi的奇偶性来分类,由于每一个位置上有奇、偶两种可能性,因此共可分为222=2n个类(鸽巢)。
这是对n维整点的一种分类方法。
当n=3时,23=8,此时可以构造命题:
“任意给定空间中九个整点,求证它们之中必有两点存在,使连接这两点的直线段的内部含有整点”。
这就是1971年的美国普特南数学竞赛题。
例4(美国普特南数学竞赛题)任意6个人中必有3个人互相认识,或互相不认识。
这就是著名的Ramsey问题。
这个问题可转化为:
对6阶完成图K6的边任着红、蓝两色,必存在同色三角形。
证明设A0,A1,A5为K6的6个顶点,从A0引出的5条边中,必有3条同色,不妨设A0A1,A0A2,A0A3为红色。
若A1A2A3有一条红边,则这条边的两个端点连同A0构成红色三角形。
若A1A2A3没有红边,则这个三角形为蓝红色三角形。
结论成立。
我们用6个点表示6个人,当两个人互相认识时,两个点之间连一条红边,当两个人互相不认识时,两个点之间连一条蓝边,于是,注:
6为结论成立的最小数.,例5(第6届国际中学生数学奥林匹克试题),17名科学家中每名科学家都和其他科学家通信,在他们通信时,只讨论三个问题,而且任意两名科学家通信时只讨论同一个问题,证明:
其中至少有三名科学家,他们相互通信时讨论的是同一个问题。
证明:
视17个科学家为17个点,每两个点之间连一条线表示这两个科学家在讨论同一个问题,若讨论第一个问题则在相应两点连红线,若讨论第2个问题则在相应两点连条黄线,若讨论第3个问题则在相应两点连条蓝线。
三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。
即转化为证明:
对17阶完成图K17的边任着红、蓝、黄三色,必存在同色三角形。
考虑科学家A,他要与另外的16位科学家每人通信讨论一个问题,相应于从A出发引出16条线段,将它们染成3种颜色,由鸽巢原理必有6条同色,不妨记为AB1,AB2,AB3,AB4,AB5,AB6同红色,若Bi(i=1,2,6)之间有红线,则出现红色三角线,命题已成立;否则B1,B2,B3,B4,B5,B6之间的连线只染有黄、蓝两色,由例4存在同色三角形,证毕。
前面数例我们看到,鸽巢原理的应用多么奇妙,其关键在于恰当地制造鸽巢,就像我们前面所介绍的,利用余数分类,划分集合,分割区间,分割图形,利用染色等,都是制造“鸽巢”的方法。
运用鸽巢原理解题往往能起到事半功倍的效果,鸽巢原理的道理极其简单,但需要巧妙地精心地应用它,不仅可以解决国内数学竞赛中的问题,而且可以解决国际中学生数学竞赛的问题.,4.鸽巢原理的推广Ramsey定理(介绍),鸽巢原理是组合学中的一个最基本的原理,应用它可以解决许多涉及存在性的组合问题。
但对于一些更加复杂的有关存在性的组合问题,鸽巢原理显得无能为力。
1928年,24岁的英国数学家、哲学家兼经济学家F.P.Ramsey在伦敦的数学会宣读了一篇题为“论形式逻辑中的一个问题”的论文,文中证明的一个组合数学定理后来被称为Ramsey定理。
Ramsey定理可视为鸽巢原理的推广,它的简单形式就是我们前面提到的著名的Ramsey问题。
人们普遍认为Ramsey定理是组合学中最重要、最精美的定理之一。
2.3Ramsey定理3,练习,6个人中一定有3个人相互认识或相互不认识。
证明:
先考虑6个人中的任意一个人,不妨把这个人称作p。
则其他的5个人可以分为下面的两个集合F和S。
其中F=与p相识的人的集合,S=与p不相识的人的集合由鸽笼原理知,这两个集合中至少有一个集合包含有3个人。
(1)若F包含有3个人,则这3个人或者彼此不相识,或者有两个人彼此相识。
如果F中有3个人彼此不相识,则结论成立。
如果F中有2人相识,则由于这两个人都与p相识,因此有3人彼此相识,故定理结论成立。
(2)类似的,如果S包含3个人,则这3个人或者彼此相识,或者有两个人彼此不相识。
如果这3个人彼此相识,则结论成立。
如果有两个人彼此不相识,则由于这两个人都与p也不相识,因此有3个人彼此不相识,故定理结论成立。
Ramsey定理(一般形式)是一集合且设是任意给定的正整数,且,则必存在最小的正整数,使得当时,将的所有t元子集任意分放到n个盒子里,那么,要么有中的个元素,它的所有t元子集全在第1个盒子里;要么有中的个元素,它的所有t元子集全在第2个盒子里;要么有中的个元素,它的所有t元子集全在第个n盒子里.,当t=1时,Ramsey定理为鸽巢原理的加强形式,此时,称为Ramsey数.,著名的Ramsey问题,可叙述为:
将6个元素的的所有2元子集放入两个盒子,则必存在3个元素,它的所有2元子集全在第1个盒子里,或者存在3个元素,它的所有2元子集全在第2个盒子里.,这里N(3,3;2)=6.,谢谢大家!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 章鸽巢 原理 习题
![提示](https://static.bingdoc.com/images/bang_tan.gif)