数学竞赛之组合数学选讲市公开课一等奖百校联赛特等奖课件.pptx
《数学竞赛之组合数学选讲市公开课一等奖百校联赛特等奖课件.pptx》由会员分享,可在线阅读,更多相关《数学竞赛之组合数学选讲市公开课一等奖百校联赛特等奖课件.pptx(61页珍藏版)》请在咨信网上搜索。
1、1组合数学组合数学西北工业大学从属中学焦和平第1页2一概论一概论pp组合数学是一个古老而又年轻数学分支。组合数学是一个古老而又年轻数学分支。组合数学是一个古老而又年轻数学分支。组合数学是一个古老而又年轻数学分支。组合数学中著名问题组合数学中著名问题 地图着色问题地图着色问题地图着色问题地图着色问题中国邮差问题中国邮差问题中国邮差问题中国邮差问题船夫过河问题船夫过河问题船夫过河问题船夫过河问题任务分配问题任务分配问题任务分配问题任务分配问题第2页3 组合数学主要研究一组离散对象满足一组合数学主要研究一组离散对象满足一定条件安排,讨论内容大致有四方面:定条件安排,讨论内容大致有四方面:pp1 1存
2、在性存在性存在性存在性:有没有满足条件安排?:有没有满足条件安排?:有没有满足条件安排?:有没有满足条件安排?pp2 2计数计数计数计数:满足条件安排有多少种?:满足条件安排有多少种?:满足条件安排有多少种?:满足条件安排有多少种?pp3 3结构结构结构结构:给出满足条件安排详细结构。:给出满足条件安排详细结构。:给出满足条件安排详细结构。:给出满足条件安排详细结构。pp4 4优化优化优化优化:在众多满足要求安排中,按一定标准挑:在众多满足要求安排中,按一定标准挑:在众多满足要求安排中,按一定标准挑:在众多满足要求安排中,按一定标准挑出最优安排。出最优安排。出最优安排。出最优安排。第3页4二、
3、数学竞赛中主要问题二、数学竞赛中主要问题p1组合数学中存在性问题组合数学中存在性问题p11抽屉原理抽屉原理 抽屉原理是一件简单明了事实:n+1个物品放入n个抽屉中,则最少有一个抽屉,其中有两个或更多物品。普通地:m个物品放入n个抽屉中,则最少有一个抽屉不少于a个,其中第4页5抽屉原理抽屉原理p普通地:m个物品放入n个抽屉中,则最少有一个抽屉不少于a个,其中第5页6抽屉原理变式抽屉原理变式抽屉原理变式抽屉原理变式第6页7例例例例1 1单位圆内任意投放六点,求证最少有两点距离单位圆内任意投放六点,求证最少有两点距离单位圆内任意投放六点,求证最少有两点距离单位圆内任意投放六点,求证最少有两点距离小于
4、小于小于小于1 1。pp解答:取六点中一点解答:取六点中一点解答:取六点中一点解答:取六点中一点A A A A,若若若若A A A A为单位圆圆心,为单位圆圆心,为单位圆圆心,为单位圆圆心,结论显然成立。结论显然成立。结论显然成立。结论显然成立。若若若若A A不是圆心不是圆心不是圆心不是圆心OO,则如图将,则如图将,则如图将,则如图将单位圆划分为六个中心角为单位圆划分为六个中心角为单位圆划分为六个中心角为单位圆划分为六个中心角为6060度扇形度扇形度扇形度扇形,若阴影部分若阴影部分若阴影部分若阴影部分内还有六点中另一点内还有六点中另一点内还有六点中另一点内还有六点中另一点,则结论成立则结论成立
5、则结论成立则结论成立.若阴影部分内若阴影部分内若阴影部分内若阴影部分内没有六点中除没有六点中除没有六点中除没有六点中除A A点外点点外点点外点点外点,则另五点则另五点则另五点则另五点(物品物品物品物品)在其余四个在其余四个在其余四个在其余四个扇形扇形扇形扇形(抽屉抽屉抽屉抽屉)中中中中,由抽屉原理由抽屉原理由抽屉原理由抽屉原理,必有某个扇形必有某个扇形必有某个扇形必有某个扇形(抽屉抽屉抽屉抽屉)含含含含有最少两个有最少两个有最少两个有最少两个(物品物品物品物品),),故结论成立故结论成立故结论成立故结论成立.第7页8例例例例2 2平面上任给平面上任给平面上任给平面上任给个点,其中任两点距离均大
6、于个点,其中任两点距离均大于个点,其中任两点距离均大于个点,其中任两点距离均大于 ,求证:必有求证:必有求证:必有求证:必有223223个点彼此之间距离都大于个点彼此之间距离都大于个点彼此之间距离都大于个点彼此之间距离都大于2 2。pp解答解答解答解答:将平面按图分成九个将平面按图分成九个将平面按图分成九个将平面按图分成九个抽屉抽屉抽屉抽屉,i,i,i,i号小方格全体为第号小方格全体为第号小方格全体为第号小方格全体为第i i i i个抽屉个抽屉个抽屉个抽屉.个点分放在九个抽个点分放在九个抽个点分放在九个抽个点分放在九个抽屉中屉中屉中屉中,最少有一个抽屉含有最少有一个抽屉含有最少有一个抽屉含有最
7、少有一个抽屉含有223223223223个点个点个点个点,因为因为因为因为个点中任两个点中任两个点中任两个点中任两点距离均大于点距离均大于点距离均大于点距离均大于 ,所以此所以此所以此所以此223223223223个点距离均大于个点距离均大于个点距离均大于个点距离均大于,它们它们它们它们中没有两点属于同一小方中没有两点属于同一小方中没有两点属于同一小方中没有两点属于同一小方格格格格,而同号方格又不在同一而同号方格又不在同一而同号方格又不在同一而同号方格又不在同一方格中任两点距离都大于方格中任两点距离都大于方格中任两点距离都大于方格中任两点距离都大于2.2.2.2.1 1 1 12 2 2 2
8、3 3 3 31 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 34 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 67 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 91 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 34 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 64 4 4 4
9、5 5 5 5 6 6 6 67 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 91 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 34 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 64 4 4 45 5 5 5 6 6 6 67 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 97 7 7 78 8 8 8 9 9 9 9第8页9pp本题牵扯到本题牵扯到本题牵扯到
10、本题牵扯到A A A A子集以及子集中各数之和两个讨论对子集以及子集中各数之和两个讨论对子集以及子集中各数之和两个讨论对子集以及子集中各数之和两个讨论对象,分别讨论它们有多少种。象,分别讨论它们有多少种。象,分别讨论它们有多少种。象,分别讨论它们有多少种。15151515元子集元子集元子集元子集A A A A子集共个子集共个子集共个子集共个 ,不空真子集共,不空真子集共,不空真子集共,不空真子集共 个,真子集中各个,真子集中各个,真子集中各个,真子集中各数之和数之和数之和数之和S S S S满足满足满足满足 =27979=27979=27979=27979,pp子集中各数和种数不超出子集中各数
11、和种数不超出子集中各数和种数不超出子集中各数和种数不超出27979279792797927979,将,将,将,将32766327663276632766个子集个子集个子集个子集放入放入放入放入27979279792797927979类和(抽屉)中,最少有一类和中含有类和(抽屉)中,最少有一类和中含有类和(抽屉)中,最少有一类和中含有类和(抽屉)中,最少有一类和中含有两个子集,即有两个子集,即有两个子集,即有两个子集,即有 B B B B与与与与C C C C中各数和相等。中各数和相等。中各数和相等。中各数和相等。若若若若 ,则结论成立;若,则结论成立;若,则结论成立;若,则结论成立;若 ,则以
12、,则以,则以,则以pp 代替代替代替代替B B B B,C C C C,结论亦成立。,结论亦成立。,结论亦成立。,结论亦成立。第9页10第10页111 1 1 12 2 2 2 极端原理极端原理极端原理极端原理 利用讨论“极端”对象来实现问题处理解题方法称为用极端原了解题,惯用极端原理基于下述简单事实:1)由实数组成有限集合,必有一个最大数,也有一个最小数。2)由自然数组成任何非空集合中,必有一个最小自然数。为了必定或否定组合数学问题存在性,极端原理有着重大作用。考查极端情况,讨论极端对象,无形中给问题讨论增加了一个条件,所以更有利于问题处理;用反证法时,讨论极端情况,使矛盾更轻易暴露。第11
13、页12例例例例5 5 对平面上不全共线对平面上不全共线对平面上不全共线对平面上不全共线n n个点,求证:必存在一条个点,求证:必存在一条个点,求证:必存在一条个点,求证:必存在一条恰好经过两点直线。恰好经过两点直线。恰好经过两点直线。恰好经过两点直线。解答:对解答:对解答:对解答:对n n个点中任两点作连线个点中任两点作连线个点中任两点作连线个点中任两点作连线mm,并取连线外点并取连线外点并取连线外点并取连线外点P P(必存在),(必存在),(必存在),(必存在),考查考查考查考查P P到到到到mm距离距离距离距离d d(P P,mm),),),),因为点为有限个,连线因为点为有限个,连线因为
14、点为有限个,连线因为点为有限个,连线mm为有限条,为有限条,为有限条,为有限条,组合(组合(组合(组合(P P,mm)也只能有有限个,用极端原理设)也只能有有限个,用极端原理设)也只能有有限个,用极端原理设)也只能有有限个,用极端原理设d d(P P,mm)为最小。)为最小。)为最小。)为最小。下面证实,下面证实,下面证实,下面证实,mm恰经过恰经过恰经过恰经过n n点中点中点中点中2 2点:点:点:点:过点过点过点过点P P作作作作mm垂线,设垂足为垂线,设垂足为垂线,设垂足为垂线,设垂足为A.A.若若若若mm上最少有上最少有上最少有上最少有n n点点点点中中中中3 3点,则最少有点,则最少
15、有点,则最少有点,则最少有2 2点在点在点在点在A A同侧,设同侧,设同侧,设同侧,设B B,C C在在在在A A同侧,同侧,同侧,同侧,且且且且ABAC,AB3n3)名乒乓球选手单打比赛若干场后)名乒乓球选手单打比赛若干场后)名乒乓球选手单打比赛若干场后)名乒乓球选手单打比赛若干场后,任意两任意两任意两任意两名选手已胜过对手恰好都不完全相同名选手已胜过对手恰好都不完全相同名选手已胜过对手恰好都不完全相同名选手已胜过对手恰好都不完全相同,求证求证求证求证:总能够从中去掉一名选手总能够从中去掉一名选手总能够从中去掉一名选手总能够从中去掉一名选手,使得余下选手中使得余下选手中使得余下选手中使得余下
16、选手中,任意两任意两任意两任意两个选手已胜过对手依然都不完全相同个选手已胜过对手依然都不完全相同个选手已胜过对手依然都不完全相同个选手已胜过对手依然都不完全相同.pp证实证实证实证实:若不存在可去选手若不存在可去选手若不存在可去选手若不存在可去选手,则则则则A A不是可去选手不是可去选手不是可去选手不是可去选手,去掉去掉去掉去掉A A后后后后.最最最最少存在选手少存在选手少存在选手少存在选手B B和和和和C,C,他们胜过对手完全相同他们胜过对手完全相同他们胜过对手完全相同他们胜过对手完全相同,故故故故B B和和和和C C一定没一定没一定没一定没有胜过有胜过有胜过有胜过;B;B和和和和C C中恰
17、有一人中恰有一人中恰有一人中恰有一人(不妨设为不妨设为不妨设为不妨设为B)B)与与与与A A胜过胜过胜过胜过(不然不然不然不然B B和和和和C C在未去掉在未去掉在未去掉在未去掉A A时胜过对手完全相同时胜过对手完全相同时胜过对手完全相同时胜过对手完全相同),),如图如图如图如图:同时同时同时同时C C也不是可去选手也不是可去选手也不是可去选手也不是可去选手,C,C代替代替代替代替A,A,如上述讨论可知如上述讨论可知如上述讨论可知如上述讨论可知,有有有有D D和和和和E,E,其中其中其中其中D D和和和和C C胜过胜过胜过胜过,E E和和和和C C未胜过未胜过未胜过未胜过,去掉去掉去掉去掉C
18、C后后后后,D,D和和和和E E胜过对手胜过对手胜过对手胜过对手相同相同相同相同.D D D D不会是不会是不会是不会是A,B(A,B(A,B(A,B(因因因因A,BA,BA,BA,B与与与与C C C C未胜过未胜过未胜过未胜过),D),D),D),D与与与与B B B B胜过胜过胜过胜过(因因因因D D D D和和和和C C C C胜过胜过胜过胜过,去掉去掉去掉去掉A A A A后后后后,B,C,B,C,B,C,B,C对手相同对手相同对手相同对手相同).).).).去掉去掉去掉去掉C C C C后后后后,D,D,D,D和和和和E E E E胜过对手相同胜过对手相同胜过对手相同胜过对手相同.
19、所以所以所以所以E E E E与与与与B B B B也胜过也胜过也胜过也胜过.第14页151.3 结构法和不变性原理结构法和不变性原理pp经过直接构作出解答来实现问题处理称为用结构经过直接构作出解答来实现问题处理称为用结构经过直接构作出解答来实现问题处理称为用结构经过直接构作出解答来实现问题处理称为用结构法解题法解题法解题法解题;对讨论问题分析其改变对讨论问题分析其改变对讨论问题分析其改变对讨论问题分析其改变,找出其中不变量、找出其中不变量、找出其中不变量、找出其中不变量、不变关系或不变性质,抓住变中不变关系或不变性质,抓住变中不变关系或不变性质,抓住变中不变关系或不变性质,抓住变中“不变不变
20、不变不变”以促使以促使以促使以促使问题处理称为用不变性原了解题。问题处理称为用不变性原了解题。问题处理称为用不变性原了解题。问题处理称为用不变性原了解题。pp对于组合数学存在性问题,惯用结构法给出必定对于组合数学存在性问题,惯用结构法给出必定对于组合数学存在性问题,惯用结构法给出必定对于组合数学存在性问题,惯用结构法给出必定答案,而不变性原理常可给出否定结论。不变性答案,而不变性原理常可给出否定结论。不变性答案,而不变性原理常可给出否定结论。不变性答案,而不变性原理常可给出否定结论。不变性原理中最简单、最实用是奇偶性分析。原理中最简单、最实用是奇偶性分析。原理中最简单、最实用是奇偶性分析。原理
21、中最简单、最实用是奇偶性分析。第15页16例例例例8 8 8 8 有一个凸有一个凸有一个凸有一个凸n n n n边形(边形(边形(边形(n4n4n4n4)全部顶点用红绿蓝三色)全部顶点用红绿蓝三色)全部顶点用红绿蓝三色)全部顶点用红绿蓝三色染色,三种颜色都出现,且任意两相邻顶点不一样色,染色,三种颜色都出现,且任意两相邻顶点不一样色,染色,三种颜色都出现,且任意两相邻顶点不一样色,染色,三种颜色都出现,且任意两相邻顶点不一样色,求证:可用在求证:可用在求证:可用在求证:可用在n n n n边形内不交对角线将多边形分成边形内不交对角线将多边形分成边形内不交对角线将多边形分成边形内不交对角线将多边
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 竞赛 组合 选讲市 公开 一等奖 联赛 特等奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。