数学竞赛之组合数学选讲市公开课一等奖百校联赛特等奖课件.pptx

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