高数比高中数学简单-2018江苏高中数学竞赛时间
精品文档
课程简介:全国高中数学联赛是中国高中数学学科的最高等级的数学竞赛,其
地位远高于各省自行
组织的数学竞赛。在这项竞赛中取得优异成绩的全国约90名学生有资格参加由中国
数学会主办的
“中国数学奥林匹克(CMO)暨全国中学生数学冬令营”。优胜者可以自动获得各重点大
学的保送资
格。各省赛区一等奖前6名可参加中国数学奥林匹克,获得进入国家集训队的机会。中小学教
育网
重磅推出“全国高中数学联赛”辅导课程,无论是有意向参加竞赛的初学者,还是已入围二试的竞<
br>赛选手,都有适合的课程提供。本套课程由中国数学奥林匹克高级教练熊斌、人大附中数学教师李
秋生等名师主讲,轻松突破你的数学极限!
课程招生简章:http:
选课中心地址:
http:?courseeduid=170037#_170037_
第二章 组合专题
一、重要的概念与定理
1、完全图:每两个顶点之间均有边相连的简单图称为完全图,有
个顶点的完全图
(阶完全图)
记为
2、顶点的度:图
精品文档
.
中与顶点
相关联的边数(环按2条边计算)称为顶点
精品文档
的度(或次数),记为
.
分别表示图
与<
/p>
点,度为偶数的顶点称为偶顶点.
3、树:没有圈的连通图称为树,用
精品文档
的顶点的最小度与最大度.度为奇数的顶点称为
奇顶
表示,其中度
为1的顶点称为树叶(或悬挂点).
4、
精品文档
.
部图:若图
阶树常表示为
精品文档
的顶点集
可以分解为
个两两不相交的非空子集的并,即
精品文档
并且同一子集
任何两个顶点没有边相连
,则称这样的图为
内
部图,记
作
5、完全
精品文档
. 2部图又叫做偶图,记为
.
部图:在一个
,
精品文档
部图
中
,若对任意
则称图
精品文档
均有边连接
和
为完全
,
精品文档
部图,记为
.
6、欧拉迹:包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹.
欧拉图:包含欧拉迹的图为欧拉图. 欧拉图必是连通图.
哈密顿链(圈):经过图上各顶点一次
并且仅仅一次的链(圈)称为哈密顿链(圈).包含哈密
顿圈的图称为哈密顿图.
7、平面图:若一个图
与
精品文档
同构的图
,使
可画在平面上,即可作一个
精品文档
的顶点与边在同一平面内,且任意两边仅在端点相交,则图
称为平面图.
一个平
面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边
的外面的面称为
外部面,其余的称为内部面.
8、竞赛图:有向完全简单图称为竞赛图.有个顶
点的竞赛图记作
9、有向路:在有向图
序列
精品文档
.
,其中
,一个由不同的弧组成的中
精品文档
的起点为
,终点为
,称这个序列为从
的有向路(简称路),
长,
精品
文档
到
为路的起
为这个路的
点,
精品文档
为路的终点.若
,则称这个路为回路.
精品文档
定理1 设
精品文档
阶图,则
中
是
精品文档
个顶点的度之和为边数的2倍.
定理2 对于任意图
定理3(Turan定理) 有
,奇顶点的个数一定是偶数.
个顶点且不含三角形的
定理4 图
精品文档
的最大边数为
.
为偶图,当且仅当
图
定理5 若树
精品文档
中不含长度为奇数的圈.
的顶点数
,则
中至少有两个树叶.
定理6
若数
精品文档
个顶点,则
有
定理7 设
精品文档
的边数
.
是有
⑴ 图
精品文档
个顶点、
条边的图,则下列命题等价:
是树; ⑵ 图
精品文档
无圈,且
; ⑶
图
连通,且
定理8
精品文档
.
阶连通图中以树的边数最少,且
阶连通图必有一个子图是树.
精品文档
定理9(一笔画定理)
有限图
以一笔画成)的充要条件是
数为0或2. 当且仅当奇顶点个数为0时,连通图
是一条链或圈(可
是连通的,且奇顶点的个
是
一个圈.
定理10 在偶图
精品文档
,则
,若中
一定无哈密顿圈.若
精品文档
的差大于1,则
一定无哈密顿链.
与
定理11
设
精品文档
是
阶简单图,且对每一对顶点
有,
则图
定理12 设
精品文档
有哈密顿链.
是
阶简单图,且对每一对不相邻的顶点
则图
定理13
设
精品文档
有
有哈密顿圈.
是
,
精品文档
阶简单图,若每个顶点的度
,则图
有哈密顿圈.
定理14
若图
精品文档
有哈密顿圈,从
中去掉若干个点
及与它们关联的边得到图
精品文档
,则图
的连通分支不超过
个.
定理15(欧拉公式)
精品文档
若一个连通的平面图
个顶点、
条边、
有
定理16 一个连通的平面简单图有
精品文档
个面,则
.
个顶点、
精品文档
条边,则
,对于连通的偶图,则有
.
精品文档
定理17 一个图是平面图当且仅当它不包含同胚于
的子图.
定理18
设
或
阶竞赛图
且
精品文档
的顶点为
,则
.
,
精品文档
定理19 竞赛图中出度最大的点称为“优点”,“优点”到其余各点都有长度不超过2的链.
定理20 竞赛图
的哈密顿路.
中存在一条长为
定理21
竞赛图
条件是有两个顶点
精品文档
.
中有一个回路是三角形的充要
满足
精品文档
定理22(Ramsey定理) 任意2色完全图
在同色三角形.
中必存
精品文档
二、例题选讲
例1 、某天晚上21
个人之间通了电话,有人发现这21人共通话102次,且每两人至多通话一次.
他还发现,存在
2个人与第3个人通了话,……,
第
个人,第1个人与第2个人通了话,第
个人与第
精品文档
个人通了话,第
个人又与第1个人通了话,他不肯透露
的具体值,只说
精品文档
是奇数.求证: 21个人中必存在3人,他们两两通了
话.
例2、45个校友聚会,在这些人中,任意两个熟人数目相同的校友互不认识.问在参加校友聚会的
所有
人中,熟人最多的人的数目最多是多少?
精品文档
精品文档
1.平面上的
n
(
≥
4)个点中,任何4个点都是凸四边形的顶点。证明这
n<
br>个点是一个凸
n
边
形的顶点。
精品文档
2.平面上有两条线段
AB
和
CD
使得
ABDC是平行四边形。我想把
AB
在平面上(连续地)移动直
到
A
与<
br>C
重合,
B
与
D
重合。证明:不管这两条线段多长,也不管它
们相距多远,我总可以使得在
平移的过程中
AB
扫过的总面积小于1。
3.证明:平面上任意
n
(正整数)个点能被满足下列条件的有限个圆盘(圆盘
包含边界)覆盖:
它们直径之和小于
n
,而且任何两个圆盘之间的距离(指这两个圆盘
上各取一点的最小距离)都大
于1。
精品文档
4.在平面直角坐标系中,求所有满足下列条件的过原点的直线
l
:对于任意实数
a,b
以及
d >
0,
都存在
整数
m,n
和
l
上的点
P
使得(
a
+
m,b
+
n
)和
P
的距离小于
d
。
精品文档
5.证明:任给正整数
n
,总存在正整数
K
使得下面的结论成立:如果平面
上
K
个点中没有三点共
线,那么这些点中必定存在
n
个点是一个凸<
br>n
边形的顶点。
精品文档
6.一个矩形
R
被切成了若干个(内部不相交的而且拼起来恰好是整个
R
的
)小矩形,这些小矩
形的边都与
R
的边平行或垂直,而且每个小矩形至少有一条边长为
整数。证明:
R
也至少有一条边
长为整数。
精品文档
7.平面上的点集
S
中有有限个不全共线的点,它们被染成红和蓝两
种颜色。证明:存在一条直
线使得它过
S
中至少两个点,而且
S
中在
这条直线上的所有点都是同一种颜色。
精品文档
1.试求n项的没有两个或以上连续的0的0,1序列的个数。
精品文档
2.m,n是正整数.证明:每个由mn+1个不同实数组成的
数列一定有一个(m+1)项递增子序列或
者一个(n+1)项递减子序列。
3.正整数n的一个分拆是指把n分成若干个正整数(不计次序)之和.证明对于任意正整数n,n
的分成每部分都是奇数的分拆个数等于n的分成每部分互不相同的分拆个数。
精品文档
4.n是给定正整数.将n个黑子和n个
白子任意放在一个圆周上.从某个白子起,按顺时针方向依
次将全体白子标上1,2,…,n,再从某个
黑子起,按逆时针方向依次将全体黑子标上1,2,…,n.
证明:在圆周上必可以找到连续n个棋子,
使得它们标号所成的集合恰好为{1,2,…,n}。
精品文档
精品文档
5.设n和k是正整数,且(k - n
)是非负偶数.有2n盏灯依次编号为1,2,…,2n,每一盏灯
可以开和关.开始时所有的灯都是关
的, 现在要对这些灯进行k次操作,每次操作改变且只改变一盏
灯的开关状态.用N表示满足“k次操
作以后灯1,2,…,n是开的,其它灯都是关的”的不同操作
序列总数,用M表示满足“k次操作以后
灯1,2,…,n是开的,其它灯都是关的而且从来没有被开
过”的不同操作序列总数.试求比值。
精品文档
精品文档
6.给定n,k是正整数,.假设F是{1,2,…,n}
的子集族,如果F中的每个集合
都有k个元素,而且F中任何两个集合都相交非空,那么∣F∣的最大
可能值是多少?
精品文档
7.有12个人,其中任何9人中都有5人两两认识.证明:这12人中必有6人两两认识。
精品文档
【知识储备】
精品文档
精品文档
【例题精讲】
精品文档
1.p≥1是实数,n是正整数.证明闵可夫斯基不等式:任给
实数a
1
,a
2
....,b
1
,b
2
,
....,b
n
,必有:
精品文档
2.如果函数f:Z→R满足
:存在正数M使得对于任意正数a和正整数d,
(这里
精品文档
I=
[a-d,a+d],表示f在I上的平均值),那么就称f
是BMO的,M则称为f的一个BMO模长
.证明存在正的常数C,使得对于任何BMO的函数f,只要M
是f的一个BMO模长,就有对任何正数
a和正整数d,
精品文档
3.设n是
给定的正整数.S={1,2,…,n}.求|A△S|+|B△S|+|C△S|的最小值.这里A,B是非空
有限
实数集合,C=A+B={x+y|x∈A,y∈B}.X△Y表示由恰好属于X,Y中一个的元素
组成的集合.
精品文档
精品文档
4.证明存在正的常数C,使得平面直角坐标系中的
任意有限个(边平行于坐标轴的)正方形中
必能挑出一些正方形两两内部无公共点,而且他们覆盖的总面
积不小于全体正方形覆盖总面积的C
倍.
5.设A是一个有限实数集.A1
,A
2
,…,A
n
是A的非空子集,且满足:(
(i
i)对任意x
i
∈A
i
(i=1,2,…,n),都成立
i)A中所有元素之和为0;
.证明:
精品文档
存在1≤i
1
2
<…k
≤n使得
精品文档
精品文档
6.设m和n是给定的正整数,4
A
2
…A
2n+1
是一个正(2n+1)边形,P={A1
, A
2
,…,A
2n+1
}.
求顶点属于P且恰
有两个内角是锐角的凸m边形个数.
精品文档
精品文档
7.将全体正整数用红或蓝进行二染色.证明:存在一列无穷个递增正整数a
1
,a
2
,a
3
,…使得
全都是同色的正整数.
精品文档
精品文档
8.如果平面上的有限(≥1)个非零向量形成的集
合R满足下列三个条件就称R为一个根系:(i)
任两个向量a,b∈R,
b∈R,∈R;(<
br>们或者相等或者和为0.试求平面上所有可能的根系.
是整数;(ii)任两个向量a,
iii)如果R中两个向量共线,那么他
精品文档
精品文档
精品文档
精品文档
精品文档
高中数学必修二空间几何体-清江中学高中数学名师
教师资格证高中数学面试视频教程-高中数学概率的考点
高中数学定义域有哪些技巧-高中数学圆的有关试题及答案
高中数学平面数乘向量教案-高中数学化学一号通
南雅高中数学组-人教版高中数学旧教材目录
高中数学2-2微积分的例题-高中数学例奇函数的特征
高中数学老师面试试讲内容-高中数学对数函数与指数函数
高中数学能听懂不会做题怎么办-高中数学学科本核心素养试题
-
上一篇:高中数学联赛基本知识集锦
下一篇:全国高中数学联赛(上海)赛区竞赛试卷