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

1组合数学西北工业大学从属中学焦和平第1页2一．概论组合数学是一个古老而又年轻数学分支。组合数学中著名问题

地图着色问题

中国邮差问题船夫过河问题任务分配问题第2页3

组合数学主要研究一组离散对象满足一定条件安排，讨论内容大致有四方面：1．存在性：有没有满足条件安排？2．计数：满足条件安排有多少种？3．结构：给出满足条件安排详细结构。4．优化：在众多满足要求安排中，按一定标准挑出最优安排。第3页4二、数学竞赛中主要问题1．组合数学中存在性问题1．1抽屉原理抽屉原理是一件简单明了事实：n+1个物品放入n个抽屉中，则最少有一个抽屉，其中有两个或更多物品。普通地：m个物品放入n个抽屉中，则最少有一个抽屉不少于a个，其中第4页5抽屉原理普通地：m个物品放入n个抽屉中，则最少有一个抽屉不少于a个，其中第5页6抽屉原理变式第6页7例1．单位圆内任意投放六点，求证最少有两点距离小于1。解答：取六点中一点A，

若A为单位圆圆心，

结论显然成立。

若A不是圆心O，则如图将

单位圆划分为六个中心角为60度扇形,若阴影部分内还有六点中另一点,则结论成立.若阴影部分内没有六点中除A点外点,则另五点(物品)在其余四个扇形(抽屉)中,由抽屉原理,必有某个扇形(抽屉)含有最少两个(物品),故结论成立.第7页8例2．平面上任给个点，其中任两点距离均大于，求证：必有223个点彼此之间距离都大于2。

解答:将平面按图分成九个抽屉,i号小方格全体为第i个抽屉.个点分放在九个抽屉中,最少有一个抽屉含有223个点,因为个点中任两点距离均大于,所以此223个点距离均大于,它们中没有两点属于同一小方格,而同号方格又不在同一方格中任两点距离都大于2.

123123123456456456789789789123123123456456456789789789123123123456456456789789789第8页9本题牵扯到A子集以及子集中各数之和两个讨论对象，分别讨论它们有多少种。15元子集A子集共个，不空真子集共个，真子集中各数之和S满足=27979，子集中各数和种数不超出27979，将32766个子集放入27979类和（抽屉）中，最少有一类和中含有两个子集，即有B与C中各数和相等。若，则结论成立；若，则以代替B，C，结论亦成立。第9页10第10页111．2极端原理

利用讨论“极端”对象来实现问题处理解题方法称为用极端原了解题，惯用极端原理基于下述简单事实：

1）由实数组成有限集合，必有一个最大数，也有一个最小数。

2）由自然数组成任何非空集合中，必有一个最小自然数。为了必定或否定组合数学问题存在性，极端原理有着重大作用。考查极端情况，讨论极端对象，无形中给问题讨论增加了一个条件，所以更有利于问题处理；用反证法时，讨论极端情况，使矛盾更轻易暴露。第11页12例5．对平面上不全共线n个点，求证：必存在一条恰好经过两点直线。

解答：对n个点中任两点作连线m，

并取连线外点P（必存在），

考查P到m距离d（P，m），

因为点为有限个，连线m为有限条，

组合（P，m）也只能有有限个，用极端原理设d（P，m）为最小。下面证实，m恰经过n点中2点：过点P作m垂线，设垂足为A.若m上最少有n点中3点，则最少有2点在A同侧，设B，C在A同侧，且AB<AC,则d(B,PC)=d(P,m),矛盾.

第12页13例6．一组砝码含有以下性质：

（1）其中有5个砝码质量各不相同；

（2）对于任何2个砝码，都能够找到另外2个砝码，它们质量之和相等。问这组砝码最少有多少个？解答:设A是其中最重砝码,B是次重砝码,则质量组{A,B}质量之和只能与质量分别与它们相等两个砝码质量之和相等.所以至少有两组这样砝码.又砝码{A,A}质量之和又只能与质量分别与它们相等两个砝码质量之和相等,所以最重砝码至少有4个,次重砝码至少有2个.

同理最轻砝码至少有4个,次轻砝码至少有2个.因为有5个质量各不相同砝码,至少还有另一种质量砝码,所以砝码个数至少有4+4+2+2+1=13个.

其次,质量分别为{1,1,1,1,2,2,3,4,4,5,5,5,5}13个砝码满足题给条件.第13页14例7．n（n>3）名乒乓球选手单打比赛若干场后,任意两名选手已胜过对手恰好都不完全相同,

求证:总能够从中去掉一名选手,使得余下选手中,任意两个选手已胜过对手依然都不完全相同.

证实:若不存在可去选手,则A不是可去选手,去掉A后.最少存在选手B和C,他们胜过对手完全相同,故B和C一定没有胜过;B和C中恰有一人(不妨设为B)与A胜过(不然B和C在未去掉A时胜过对手完全相同),如图:

同时C也不是可去选手,C代替A,

如上述讨论可知,有D和E,其中D和C胜过,

E和C未胜过,去掉C后,D和E胜过对手

相同.D不会是A,B(因A,B与C未胜过),D与B

胜过(因D和C胜过,去掉A后,B,C对手相同).

去掉C后,D和E胜过对手相同.所以E与B也胜过.第14页151.3结构法和不变性原理经过直接构作出解答来实现问题处理称为用结构法解题;对讨论问题分析其改变,找出其中不变量、不变关系或不变性质，抓住变中“不变”以促使问题处理称为用不变性原了解题。对于组合数学存在性问题，惯用结构法给出必定答案，而不变性原理常可给出否定结论。不变性原理中最简单、最实用是奇偶性分析。第15页16例8．有一个凸n边形（n4）全部顶点用红绿蓝三色染色，三种颜色都出现，且任意两相邻顶点不一样色，求证：可用在n边形内不交对角线将多边形分成n-2个三角形，使每个三角形三顶点都不一样色。

解答:若某种颜色点只有一个,则易知结论成立.若每种颜色顶点最少有二个,且相邻顶点颜色不一样,则必有连续三个顶点k,k+1,k+2恰为三色,将此三角形从凸n边形中割下,

那么余下是规模更小凸多边形,

若依然每种颜色顶点最少有二个,

可继续割去一个三色三角形,…,

最终可得某种颜色只有一个,

能够如图给出分划.

第16页17例9．能否把1，1，2，2，3，3，…，，这4010个数排成一列，使得两个1之间有一个数，两个2之间有二个数，…，两个之间有个数.第17页18证实：充分性：可用结构法作出，如图，正方形可剖分成6个钝角三角形，又任一钝角三角形总可分成两个钝角三角形。必要性：先找出任意钝角三角形剖分中不变关系。对剖分法剖分点进行分类：在正方形边界上剖分点或在某一剖分三角形边上但不是该

三角形顶点内剖分点称为第一类

剖分点；不在三角形边上内剖分点

称为第二类剖分点。如图中F，G，H

为第一类剖分点，E为第二类剖分点。第18页19第19页20（2）任意凸四边形（各种情形）可剖分成钝角三角形（锐角三角形）充要条件又各是什么？第20页212．组合数学中计数问题2．1加法原理和乘法原理加法原理：设事件A有m种选取方式，事件B有n种选取方式，事件A和事件B没有共同选取方式，则选A或选B有m+n种方式。乘法原理：设事件A有m种选取方式，事件B有n种选取方式，则选取A以后再选B共有mn种方式。

第21页22第22页23例12.三个数1447、1005、1231有许多相同之处：它们都有四位数，最高位都是1，都恰有两个相同数字，一共有多少个这么数。第23页242.2映射与计数第24页25例13.在数列1，9，81，…，9中删去最高位是9项，问余下数列有多少项？

第25页26例14.圆周上有n个点每两个点连一线段，假设任三条线段在圆内不共点，于是三条两两相交线段组成一个三角形，试求这些三角形个数？

第26页27例15.设凸n边形任意3条对角线不相交于行内一点，求它对角线在行内交点总数。第27页28例16.今有编号为1，2，…，10钥匙与编号为1，2，…，10箱子，每把钥匙只能打开与之号数相同箱子，现将全部钥匙都放进这些箱子中，每只箱子放一把，然后锁上，那么最少有多少种不一样放法，使得最少要撬开两只箱子才能将箱子全部打开？若恰撬开两只箱子才能将箱子全部打开，又有多少放法？

第28页29

证实：我们将不定方程任意一组非负整数解对应于一个由n个圆圈“О”，k-1个竖线“|”组成以下排列：О…О|О…О|…|О…О，其中第一根竖线“|”左侧恰有x1个圆圈“О”；第i-1根竖线“|”与第i根竖线“|”之间恰有xi个圆圈“О”；第i-1根竖线“|”右侧恰有xk个圆圈“О”。显然，不定方程不一样解对应于不一样排列，且每一个这么对应于不定方程一组非负整数解，所以，我们建立对应是一个双射。又因为由n个圆圈“О”及k-1根竖线“|”组成n+k-1个元素全排列数为，所以，不定方程一组非负整数解组组数为。第29页302．3容斥原理第30页31例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.求由a，b，c，d这4个字符组成n位数字串中，a，b，c最少出现一次符号串数目。第34页35第35页36同理第36页37第37页38练习题1．给定个集合，每个集合都恰含有44个元素，而且每两个集合都恰有一个公共元素，试求这个集合并集中有多少个元素？2．平面内给定200个不一样点，证实：其中距离为单位长点对数小于2050。3．以正n边形顶点为顶点梯形共有多少个？第38页39杂题第39页40

例1

运动会开了n天（n>1）,共发出m个奖牌,第一天发出1个加余下奖牌,第二天发出2个加余下奖牌,如此继续下去,最终,第n天发出n个奖牌恰无剩下.问运动会共开了几天?共发出多少个奖牌?第40页41第41页42第42页43例2.几个人在一起,使得其中存在有相同生日概率最少为二分之一.即23人中,最少有一对生日相同概率超出二分之一

第43页44例3.甲乙二人玩，在黑板上写数游戏，规则是二人轮番在黑板上写一个不超出p自然数，但禁止再写出黑板上已经有因数。甲先开始写，轮到谁写而无法写出时就告负。

（1）当p=10时，游戏者中谁有获胜策略？

（2）当p=1000时，游戏者中谁有获胜策略？

解答：（1）甲有获胜策略，他能够先写6，于是按规则不能再写1，2，3。其余6个数分成3组：（4，5）（7，9）（8，10）不论乙写哪一个，甲就写同组另一个。

（2）考查写数标准相同但取数范围不是由1到1000而是由2到1000这个游戏。假如这个游戏先写者有必胜策略，那么甲对原来游戏只要照搬就行了。因为甲写下一个自然数后，乙是不能写1。假如新游戏先写数人没有获胜策略，即他只能告负，那么甲在原游戏中能够先写1，从而将失败留给了乙。可见，甲总有获胜策略。第44页45例4.

甲乙两人在画有个方格正方形场地上做游戏:甲先在场地中央画一个星号,乙则在放有星号格子周围8个格子中任选1个方格画一个圆圈.然后甲再在某个与已画有标识格子挨着空格中画一个星号,并一直继续下去.假如甲成功地将星号画入场地四角任何一个角上方格中,就算他获胜.求证:不论乙怎么做,甲总能够获胜.第45页46例5.在3×3正方形表格中填上如图所表示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