《组合数学课件.pptx》由会员分享，可在线阅读，更多相关《组合数学课件.pptx（58页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1一概论一概论 组合数学是一个古老而又年轻的数学分支。组合数学是一个古老而又年轻的数学分支。组合数学中的著名问题 地图着色问题地图着色问题地图着色问题地图着色问题中国邮差问题中国邮差问题中国邮差问题中国邮差问题船夫过河问题船夫过河问题船夫过河问题船夫过河问题任务分配问题任务分配问题任务分配问题任务分配问题第1页/共58页2 组合数学主要研究一组离散对象满足一定条件的安排，讨论的内容大致有四方面：1 1存在性存在性存在性存在性：有没有满足条件的安排？：有没有满足条件的安排？2 2计数计数计数计数：满足条件的安排有多少种？：满足条件的安排有多少种？3 3构造构造构造构造：给出满足条件的安排的具体构
2、造。：给出满足条件的安排的具体构造。4 4优化优化优化优化：在众多满足要求的安排中，按一定的标准挑出最优的安排。：在众多满足要求的安排中，按一定的标准挑出最优的安排。第2页/共58页3二、数学竞赛中的主要问题1组合数学中的存在性问题11抽屉原理 抽屉原理是一件简单明了的事实：n+1个物品放入n个抽屉中，则至少有一个抽屉，其中有两个或更多的物品。一般地：m个物品放入n个抽屉中，则至少有一个抽屉不少于a个，其中第3页/共58页4抽屉原理p一般地：m个物品放入n个抽屉中，则至少有一个抽屉不少于a个，其中第4页/共58页5抽屉原理的变式抽屉原理的变式抽屉原理的变式抽屉原理的变式第5页/共58页6例例1
3、 1单位圆内任意投放六点，求证至少有两点距离不大于单位圆内任意投放六点，求证至少有两点距离不大于1 1。解答：取六点中一点解答：取六点中一点A A A A，若若A A A A为单位圆的圆心，为单位圆的圆心，结论显然成立。结论显然成立。若若A A不是圆心不是圆心OO，则如图将，则如图将单位圆划分为六个中心角为单位圆划分为六个中心角为6060度的扇形度的扇形,若阴影部若阴影部分内尚有六点中另一点分内尚有六点中另一点,则结论成立则结论成立.若阴影部分若阴影部分内没有六点中除内没有六点中除A A点外的点点外的点,则另五点则另五点(物品物品)在其余在其余四个扇形四个扇形(抽屉抽屉)中中,由抽屉原理由抽屉
4、原理,必有某个扇形必有某个扇形(抽屉抽屉)含有至少两个含有至少两个(物品物品),),故结论成立故结论成立.第6页/共58页7例例2 2平面上任给平面上任给20052005个点，其中任两点距离均大个点，其中任两点距离均大于于 ，求证：必有，求证：必有223223个点彼此之间距离都不小个点彼此之间距离都不小于于2 2。解答解答:将平面按图分成九将平面按图分成九个抽屉个抽屉,i,i,i,i号小方格全体为号小方格全体为第第i i i i个抽屉个抽屉.2005.2005.2005.2005个点分放个点分放在九个抽屉中在九个抽屉中,至少有一至少有一个抽屉含有个抽屉含有223223223223个点个点,由于
5、由于2005200520052005个点中任两点距离均个点中任两点距离均大于大于 ,所以此所以此223223223223个点个点距离均大于距离均大于,它们中没有它们中没有两点属于同一小方格两点属于同一小方格,而而同号方格又不在同一方格同号方格又不在同一方格中的任两点距离都不小于中的任两点距离都不小于2.2.2.2.1 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
6、 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 91 1 1 12 2 2 2 3 3 3 31 1 1 12 2 2 2 3 3 3 31
7、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第7页/共58页8 本题牵扯到本题牵扯到A A A A的子集以及子集中各数之和两个讨论对象，分别讨论它们有多少种。的子集以及子集中各数之和两个讨论对象，分别讨论它们有多少种。15151515元子集元子集A A A A的子集共个的子集共个 ，不空真子集共，不空真子集共 个，真子集中各数之个，真子集
8、中各数之和和S S S S满足满足 =27979=27979=27979=27979，子集中各数和的种数不超过子集中各数和的种数不超过27979279792797927979，将，将32766327663276632766个子集放入个子集放入27979279792797927979类和（抽屉）中，类和（抽屉）中，至少有一类和中含有两个子集，即有至少有一类和中含有两个子集，即有 B B B B与与C C C C中各数和相等。若中各数和相等。若 ，则结论成立；若，则结论成立；若 ，则以，则以 代替代替B B B B，C C C C，结论亦成立。，结论亦成立。第8页/共58页9第9页/共58页101
9、 1 1 12 2 2 2 极端原理极端原理极端原理极端原理 利用讨论“极端”对象来实现问题解决的解题方法称为用极端原理解题，常用的极端原理基于下述简单的事实：1）由实数组成的有限集合，必有一个最大数，也有一个最小数。2）由自然数组成的任何非空集合中，必有一个最小的自然数。为了肯定或否定组合数学问题的存在性，极端原理有着重大的作用。考察极端情况，讨论极端对象，无形中给问题的讨论增加了一个条件，所以更有利于问题的解决；用反证法时，讨论极端情况，使矛盾更容易暴露。第10页/共58页11例例5 5 对平面上不全共线的对平面上不全共线的n n个点，求证：必存个点，求证：必存在一条恰好通过两点的直线。在
10、一条恰好通过两点的直线。解答：对解答：对n n个点中的任两点作连线个点中的任两点作连线mm，并取连线外的点并取连线外的点P P（必存在），（必存在），考察考察P P到到mm的距离的距离d d（P P，mm），），由于点为有限个，连线由于点为有限个，连线mm为有限条，为有限条，组合（组合（P P，mm）也只能有有限个，用极端原理设）也只能有有限个，用极端原理设d d（P P，mm）为最小。）为最小。下面证明，下面证明，mm恰通过恰通过n n点中点中2 2点：点：过点过点P P作作mm的垂线，设垂足为的垂线，设垂足为A.A.若若mm上至少有上至少有n n点中的点中的3 3点，则至少有点，则至少有2
11、 2点在点在A A的的同侧，设同侧，设B B，C C在在A A的同侧，且的同侧，且ABAC,AB3n3）名乒乓球选手单打比赛若干场后）名乒乓球选手单打比赛若干场后,任任意两名选手已赛过的对手恰好都不完全相同意两名选手已赛过的对手恰好都不完全相同,求证求证:总可以从中去掉一名选手总可以从中去掉一名选手,使得余下的选手中使得余下的选手中,任意两个选手已赛过的对手仍然都不完全相同任意两个选手已赛过的对手仍然都不完全相同.证明证明:若不存在可去选手若不存在可去选手,则则A A不是可去选手不是可去选手,去掉去掉A A后后.至少存在选手至少存在选手B B和和C,C,他们赛过的对手完全相同他们赛过的对手完全
12、相同,故故B B和和C C一定没有赛过一定没有赛过;B;B和和C C中恰有一人中恰有一人(不妨设为不妨设为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 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未赛过未赛
13、过),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赛过的对手相同赛过的对手相同.所以所以E E E E与与B B B B也赛过也赛过.第13页/共58页141.3 构造法和不变性原理 通过直接构作出解答来实现问题的解决称为用构造法解题通过直接构作出解答来实现问题的解决称为用构造法解题;对讨论问题分析其变化对讨论问题分析其变化,找出其中不变的量、不变找出其中不变的量、不变的关系或不变的性质，抓住变中
14、的的关系或不变的性质，抓住变中的“不变不变”以促使问题的解决称为用不变性原理解题。以促使问题的解决称为用不变性原理解题。对于组合数学的存在性问题，常用构造法给出肯定的答案，而不变性原理常可给出否定的结论。不变性原对于组合数学的存在性问题，常用构造法给出肯定的答案，而不变性原理常可给出否定的结论。不变性原理中最简单、最实用的是奇偶性分析。理中最简单、最实用的是奇偶性分析。第14页/共58页15例例8 8 8 8 有一个凸有一个凸n n n n边形（边形（n4n4n4n4）所有顶点用红绿蓝）所有顶点用红绿蓝三色染色，三种颜色都出现，且任意两相邻顶点三色染色，三种颜色都出现，且任意两相邻顶点不同色，
15、求证：可用在不同色，求证：可用在n n n n边形内不交的对角线将多边形内不交的对角线将多边形分成边形分成n-2n-2n-2n-2个三角形，使每个三角形的三顶点都个三角形，使每个三角形的三顶点都不同色。不同色。解答解答:若某种颜色的点只有一个若某种颜色的点只有一个,则易知结论成立则易知结论成立.若每种颜色的顶点至少有二个若每种颜色的顶点至少有二个,且相且相邻顶点颜色不同邻顶点颜色不同,则必有连续三个顶点则必有连续三个顶点k,k+1,k+2k,k+1,k+2恰为三色恰为三色,将此三角形从凸将此三角形从凸n n边形中割边形中割下下,那么余下的是规模更小的凸多边形那么余下的是规模更小的凸多边形,若仍
16、然每种颜色的顶点至少有二个若仍然每种颜色的顶点至少有二个,可继续割去一个三色三角形可继续割去一个三色三角形,最后可得某种颜色只有一个最后可得某种颜色只有一个,可以如图给出分划可以如图给出分划.第15页/共58页16例例9 9 能否把能否把1 1，1 1，2 2，2 2，3 3，3 3，20052005，20052005这这40104010个数排成一列，使得两个个数排成一列，使得两个1 1之间有一之间有一个数，两个个数，两个2 2之间有二个数，之间有二个数，两个，两个20052005之间有之间有20052005个数个数 .第16页/共58页17证明：充分性：可用构造法作出，如图，正方形可剖分成6
17、个钝角三角形，又任一钝角三角形总可分成两个钝角三角形。必要性：先找出任意钝角三角形剖分中不变的关系。对剖分法的剖分点进行分类：在正方形边界上的剖分点或在某一剖分三角形边上但不是该三角形顶点的内剖分点称为第一类剖分点；不在三角形边上的内剖分点称为第二类剖分点。如图中F，G，H为第一类剖分点，E为第二类剖分点。第17页/共58页18第18页/共58页19（2）任意凸四边形（各种情形）可剖分成钝角三角形（锐角三角形）的充要条件又各是什么？第19页/共58页202组合数学中的计数问题21 加法原理和乘法原理加法原理：设事件A有m种选取方式，事件B有n种选取方式，事件A和事件B没有共同选取方式，则选A或
18、选B有m+n种方式。乘法原理：设事件A有m种选取方式，事件B有n种选取方式，则选取A以后再选B共有mn种方式。第20页/共58页21第21页/共58页22例例12.12.三个数三个数14471447、10051005、12311231有许多相同之处：有许多相同之处：它们都有四位数，最高位都是它们都有四位数，最高位都是1 1，都恰有两个相，都恰有两个相同的数字，一共有多少个这样的数。同的数字，一共有多少个这样的数。第22页/共58页232.2 映射与计数第23页/共58页24例例13.13.在数列在数列1 1，9 9，8181，9200592005中删去最高中删去最高位是位是9 9的项，问余下的
19、数列有多少项？的项，问余下的数列有多少项？第24页/共58页25例例14.14.14.14.圆周上有圆周上有n n n n个点每两个点连一线段，假设个点每两个点连一线段，假设任三条线段在圆内不共点，于是三条两两相交的任三条线段在圆内不共点，于是三条两两相交的线段构成一个三角形，试求这些三角形的个数？线段构成一个三角形，试求这些三角形的个数？第25页/共58页26例例15.15.设凸设凸n n边形的任意边形的任意3 3条对角线不相交于行内一点，求它的对条对角线不相交于行内一点，求它的对角线在行内的交点总数。角线在行内的交点总数。第26页/共58页27例例16.16.今有编号为今有编号为1 1，2
20、 2，1010的钥匙与编号为的钥匙与编号为1 1，2 2，1010的箱子，每把钥匙只能打开与之号数相同的箱子，现将所的箱子，每把钥匙只能打开与之号数相同的箱子，现将所有钥匙都放进这些箱子中，每只箱子放一把，然后锁上，那有钥匙都放进这些箱子中，每只箱子放一把，然后锁上，那么至少有多少种不同的放法，使得至少要撬开两只箱子才能么至少有多少种不同的放法，使得至少要撬开两只箱子才能将箱子全部打开？若恰撬开两只箱子才能将箱子全部打开，将箱子全部打开？若恰撬开两只箱子才能将箱子全部打开，又有多少放法？又有多少放法？第27页/共58页28 证明：我们将不定方程证明：我们将不定方程 的任意一组的任意一组非负整数
21、解非负整数解 对应于一个由对应于一个由n n个圆圈个圆圈“”，k-1k-1个竖线个竖线“|”|”组成的如下排列：组成的如下排列：|，其中第一根竖线，其中第一根竖线“|”|”的左侧恰有的左侧恰有x1x1个圆圈个圆圈“”；第；第i-i-1 1根竖线根竖线“|”|”与第与第i i根竖线根竖线“|”|”之间恰有之间恰有xixi个圆圈个圆圈“”；第第i-1i-1根竖线根竖线“|”|”的右侧恰有的右侧恰有xkxk个圆圈个圆圈“”。显然，不。显然，不定方程的不同的解对应于不同的排列，且每一个这样的对定方程的不同的解对应于不同的排列，且每一个这样的对应于不定方程的一组非负整数解，因此，我们建立的对应应于不定方
22、程的一组非负整数解，因此，我们建立的对应是一个双射。是一个双射。又因为由又因为由n n个圆圈个圆圈“”及及k-1k-1根竖线根竖线“|”|”组成的组成的n+k-1n+k-1个个元素的全排列数为元素的全排列数为 ，所以，不定方程，所以，不定方程 的一组非负整数解组的组数为的一组非负整数解组的组数为 。第28页/共58页2923容斥原理第29页/共58页30例18.18.一个学校只有3 3门课程：数学、物理、化学，已知修这3 3门课程的学生分别有170170、130130、120120人；同时修数学、物理两门课的学生有4545人；同时修数学、化学两门课的学生有2020人；同时修物理、化学两门课的学
23、生有2222人；同时修三门课的学生有3 3人。问这个学校共有多少学生？第30页/共58页31例19.求a，b，c，d，e，f这六个字母的全排列中不允许出现ace和df图像的排列数。第31页/共58页32第32页/共58页33例例21.21.求由求由a a，b b，c c，d d这这4 4个字符构成的个字符构成的n n位数字串中，位数字串中，a a，b b，c c至少出现一次的符号串的数目。至少出现一次的符号串的数目。第33页/共58页34第34页/共58页35同理第35页/共58页36第36页/共58页37练习题1给定2003个集合，每个集合都恰含有44个元素，并且每两个集合都恰有一个公共元素
24、，试求这2003个集合的并集中有多少个元素？2平面内给定200个不同的点，证明：其中距离为单位长的点对数小于2050。3以正n边形的顶点为顶点的梯形共有多少个？第37页/共58页38杂杂 题题第38页/共58页39 例1 1 运动会开了n天（n1）,共发出m个奖牌,第一天发出1个加余下奖牌的,第二天发出2个加余下奖牌的,如此继续下去,最后,第n天发出n个奖牌恰无剩余.问运动会共开了几天?共发出多少个奖牌?第39页/共58页40第40页/共58页41第41页/共58页42例2.几个人在一起几个人在一起,使得其中存在有相同生日的概率至少为二分使得其中存在有相同生日的概率至少为二分之一之一.即即23
25、232323人中人中,至少有一对生日相同的概率超过二分之一至少有一对生日相同的概率超过二分之一 第42页/共58页43例例3.3.甲乙二人玩，在黑板上写数的游戏，规则是二人甲乙二人玩，在黑板上写数的游戏，规则是二人轮流在黑板上写一个不超过轮流在黑板上写一个不超过p p的自然数，但禁止再写出的自然数，但禁止再写出黑板上已有的因数。甲先开始写，轮到谁写而无法写出黑板上已有的因数。甲先开始写，轮到谁写而无法写出时就告负。时就告负。（1 1）当）当p=10p=10时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策略？（2 2）当）当p=1000p=1000时，游戏者中谁有获胜策略？时，游戏者中谁有获胜策
26、略？解答：（解答：（1 1）甲有获胜策略，他可以先写）甲有获胜策略，他可以先写6 6，于是按规，于是按规则不能再写则不能再写1 1，2 2，3 3。其余。其余6 6个数分成个数分成3 3组：（组：（4 4，5 5）（）（7 7，9 9）（）（8 8，1010）无论乙写哪一个，甲就写同组的另一个。）无论乙写哪一个，甲就写同组的另一个。（2 2）考察写数原则相同但取数范围不是由）考察写数原则相同但取数范围不是由1 1到到10001000而是而是由由2 2到到10001000的这个游戏。如果这个游戏先写者有必胜策的这个游戏。如果这个游戏先写者有必胜策略，那么甲对原来的游戏只要照搬就行了。因为甲写下略
27、，那么甲对原来的游戏只要照搬就行了。因为甲写下一个自然数后，乙是不能写一个自然数后，乙是不能写1 1的。如果新游戏先写数的的。如果新游戏先写数的人没有获胜策略，即他只能告负，那么甲在原游戏中可人没有获胜策略，即他只能告负，那么甲在原游戏中可以先写以先写1 1，从而将失败留给了乙。可见，甲总有获胜策，从而将失败留给了乙。可见，甲总有获胜策略。略。第43页/共58页44例4.甲乙两人在画有个方格的正方形场地上做游戏:甲先在场地中央画一个星号,乙则在放有星号的格子周围的8个格子中任选1个方格画一个圆圈.然后甲再在某个与已画有标记的格子挨着的空格中画一个星号,并一直继续下去.如果甲成功地将星号画入场地
28、四角的任何一个角上的方格中,就算他获胜.求证:不论乙怎么做,甲总可以获胜.第44页/共58页45例5.5.在33的正方形表格中填上如图所示的9个数字,将该表进行如下操作:每次操作是对表中相邻两数同时加上一个数(相邻是指有公共边的两小格),问能否经过若干次操作使得（1）表格中各数均为0；（2）表格中四个角的数为1,其余均为0.032670495第45页/共58页46解答:(1)能够得到.事实上经过5次操作即可.032670495010670495010670055010670000010010000000000000第46页/共58页47(2)考虑这种操作的一般形式:abcdefghk为此,设表
29、格中第一行的数从左到右为a,b,c.第二行的数从左到右为d,e,f.第三行的数从左到右为g,h,k.按操作规则,任意相邻的数都加同一个数,因此操作的每一步均不改变S=(a+c+e+g+k)-(b+d+h+f)的值.而表格的初始状态S的值为S=(0+2+7+4+5)-(3+6+9+0)=0要达到的状态S的值为S=(1+1+0+1+1)-(0+0+0+0)=4因此不能实现满足题目要求的操作.abcdefghk第47页/共58页48例6.凸n边形的任意3条对角线不相交于形内一点，求这些对角线将凸n边形分成的区域的个数.第48页/共58页49第49页/共58页50第50页/共58页51第51页/共58
30、页52第52页/共58页53例7.已知平面上有4条直线,其中任何两条都相交,任何三条都不交于一点,于是在每条直线上都交得3个交点,它们从直线上截出两条线段,共得到8条线段.问这8条线段的长度能否分别为 (1)1,2,3,4,5,6,7,8?(2)互不相同的自然数?第53页/共58页54（2）8条线段的长度可以是互不相同的自然数，见图。第54页/共58页55例8.一袋花生共1988颗,一只猴子第一天拿走一颗花生,从第二天起,每天拿走的都是以前各天的总和.如果到某天袋里的花生少于已拿走的总数时,这一天它又从拿走一颗开始,按原定的规律进行新的一轮.如此继续下去,那么这袋花生被猴子拿光时是第几天?第55页/共58页56练习题18个小圆片分别涂有4种颜色：红、蓝、白、黑各两个。甲乙两人轮流把圆片放到正方体的顶点上，在所有的圆片都放完之后，如果正方体上存在一条棱，其两个端点所放的圆片同色，则甲获胜，否则乙获胜。问在这个游戏中睡有必胜策略。2.在黑板上写有3个整数,然后擦去其中一个,并代之以剩下的两数之和与1的差.重复这个步骤若干次后,黑板上的数变成了17,1967,1983,问开始时黑板上所写的数能否是下列数组:(1)2,2,2 (2)3,3,3第56页/共58页57路要自己走 关要自己闯祝同学们取得好成绩祝同学们取得好成绩第57页/共58页58感谢您的观看！第58页/共58页