重点高中数学联赛组合专题

重点高中数学联赛组合专题

———————————————————————————————— 作者：
———————————————————————————————— 日期：




2

课程简介：全国高中数学联赛是中国高中数学学科的最高等级的 数学竞赛，其地位远高于各省自行
组织的数学竞赛。在这项竞赛中取得优异成绩的全国约90名学生有资 格参加由中国数学会主办的
“中国数学奥林匹克（CMO）暨全国中学生数学冬令营”。优胜者可以自动 获得各重点大学的保送资
格。各省赛区一等奖前6名可参加中国数学奥林匹克，获得进入国家集训队的机 会。中小学教育网
重磅推出“全国高中数学联赛”辅导课程，无论是有意向参加竞赛的初学者，还是已入 围二试的竞
赛选手，都有适合的课程提供。本套课程由中国数学奥林匹克高级教练熊斌、人大附中数学教 师李
秋生等名师主讲，轻松突破你的数学极限！
课程招生简章：http:
选课中心地址：
http:?courseeduid=170037#_170037_

第二章 组合专题


一、重要的概念与定理
1、完全图：每两个顶点之间均有边相连的简单图称为完全图,有
个顶点的完全图
（阶完全图） 记为
3

.
2、顶点的度：图中与顶点
相关联的边数（环按2条边计算）称为顶点
4

的度（或次数）,记为
.与
分别表示图
5

的顶点的最小度与最大度.度为奇数的顶点称为奇顶
点,度为偶数的顶点称为偶顶点.
3、树：没有圈的连通图称为树,用表示,其中度
6

为1的顶点称为树叶（或悬挂点）.阶树常表示为
.
4、部图：若图
7

的顶点集
可以分解为
个两两不相交的非空子集的并,即
8

并且同一子集

内
任何两个顶点没有边相连,则称这样的图为部图,记
9

作. 2部图又叫做偶图,记为
.
5、完全部图：在一个
10

部图
中,
11

,若对任意均有边连接
和,
则称图为完全
12

部图,记为
.
6、欧拉迹：包含图中所有边的迹称为欧拉迹.起点与终点重合的欧拉迹称为闭欧拉迹.
欧拉图：包含欧拉迹的图为欧拉图. 欧拉图必是连通图.
哈密顿链（圈）：经过图上各顶点一次 并且仅仅一次的链（圈）称为哈密顿链（圈）.包含哈密
顿圈的图称为哈密顿图.
13

7、平面图：若一个图可画在平面上,即可作一个
与同构的图
,使
14

的顶点与边在同一平面内,且任意两边仅在端点相交,则图
称为平面图.
一个平 面图的顶点和边把一个平面分成若干个互相隔开的区域,称为平面图的一个面,在所有边
的外面的面称为 外部面,其余的称为内部面.
8、竞赛图：有向完全简单图称为竞赛图.有个顶
15

点的竞赛图记作.
9、有向路：在有向图中,一个由不同的弧组成的
序列,其中
16

的起点为
,终点为
,称这个序列为从
17

到
的有向路（简称路）,为这个路的
长,为路的起
18

点,为路的终点.若
,则称这个路为回路.

19

20

定理1 设是
阶图,则
中
21

个顶点的度之和为边数的2倍.
定理2 对于任意图,奇顶点的个数一定是偶数.
定理3（Turan定理） 有个顶点且不含三角形的
22

图的最大边数为
.
定理4 图为偶图,当且仅当
23

中不含长度为奇数的圈.
定理5 若树的顶点数
,则
24

中至少有两个树叶.
定理6 若数有
个顶点,则
25

的边数
.
定理7 设是有
26

个顶点、
条边的图,则下列命题等价:
⑴ 图是树; ⑵ 图
27

无圈,且
; ⑶ 图
连通,且
28

.
定理8 阶连通图中以树的边数最少,且
阶连通图必有一个子图是树.
29

定理9（一笔画定理） 有限图是一条链或圈（可
以一笔画成）的充要条件是是连通的,且奇顶点的个
数为0或2. 当且仅当奇顶点个数为0时,连通图是
30

一个圈.
定理10 在偶图中,若
,则
31

一定无哈密顿圈.若与
的差大于1,则
一定无哈密顿链.
32

定理11 设是
阶简单图,且对每一对顶点
有,
33

则图有哈密顿链.
定理12 设是
阶简单图,且对每一对不相邻的顶点
34

有,
则图有哈密顿圈.
定理13 设是
35

阶简单图,若每个顶点的度
,则图
有哈密顿圈.
36

定理14 若图有哈密顿圈,从
中去掉若干个点
及与它们关联的边得到图
37

,则图
的连通分支不超过
个.
38

定理15（欧拉公式） 若一个连通的平面图有
个顶点、
条边、
39

个面,则
.
定理16 一个连通的平面简单图有个顶点、
40

条边,则
,对于连通的偶图,则有
.
41

定理17 一个图是平面图当且仅当它不包含同胚于
或
的子图.
定理18 设阶竞赛图
42

的顶点为
,则,
且.
43

定理19 竞赛图中出度最大的点称为“优点”,“优点”到其余各点都有长度不超过2的链.
定理20 竞赛图中存在一条长为
的哈密顿路.
44

定理21 竞赛图中有一个回路是三角形的充要
条件是有两个顶点 满足
.
45

定理22（Ramsey定理） 任意2色完全图
在同色三角形.
中必存


46

二、例题选讲
例1 、某天晚上21个人之间 通了电话,有人发现这21人共通话102次,且每两人至多通话一次.
他还发现,存在个人,第1个人 与第2个人通了话,第
2个人与第3个人通了话,……, 第个人与第
47

个人通了话,第
个人又与第1个人通了话,他不肯透露
的具体值,只说
48

是奇数.求证: 21个人中必存在3人,他们两两通了
话.

例2、45个校友聚会,在这些人中,任意两个熟人数目相同的校友互不认识.问在参加 校友聚会的
所有人中,熟人最多的人的数目最多是多少?
49

50

1.平面上的
n
（
≥
4）个点中，任何4个点都是凸四边形的顶点。证明这
n< br>个点是一个凸
n
边
形的顶点。
51

2.平面上有两条线段
AB
和
C D
使得
ABDC
是平行四边形。我想把
AB
在平面上（连续地）移动 直
到
A
与
C
重合，
B
与
D
重合。 证明：不管这两条线段多长，也不管它们相距多远，我总可以使得在
平移的过程中
AB
扫过的总面积小于1。

3.证明:平面上任意
n
（正整数）个点能 被满足下列条件的有限个圆盘（圆盘包含边界）覆盖:
它们直径之和小于
n
，而且任何 两个圆盘之间的距离（指这两个圆盘上各取一点的最小距离）都大
于1。
52

4.在平面直角坐标系中，求所有满足下列条件的过原点的直线
l
:对于任意实数
a，b
以及
d >
0,
都存在 整数
m，n
和
l
上的点
P
使得（
a
+
m，b
+
n
）和
P
的距离小于
d
。


53

5.证明:任给正整数
n< br>，总存在正整数
K
使得下面的结论成立:如果平面上
K
个点中没有三点 共
线，那么这些点中必定存在
n
个点是一个凸
n
边形的顶点。
54

6.一个矩形
R
被切成了若干 个（内部不相交的而且拼起来恰好是整个
R
的）小矩形，这些小矩
形的边都与
R
的边平行或垂直，而且每个小矩形至少有一条边长为整数。证明：
R
也至少有一条边
长为整数。
55

7.平面上的点集
S
中有有限个不全共线 的点，它们被染成红和蓝两种颜色。证明:存在一条直
线使得它过
S
中至少两个点，而 且
S
中在这条直线上的所有点都是同一种颜色。


56

1.试求n项的没有两个或以上连续的0的0，1序列的个数。

57

2.m，n是正整数.证明:每个由mn+1个不同实数组成的数列一定 有一个（m+1）项递增子序列或
者一个（n+1）项递减子序列。


3.正整数n的一个分拆是指把n分成若干个正整数（不计次序）之和.证明对于任意正整数n,n
的分 成每部分都是奇数的分拆个数等于n的分成每部分互不相同的分拆个数。
58

4.n是给定正整数.将n个黑子和n个白子任意 放在一个圆周上.从某个白子起,按顺时针方向依
次将全体白子标上1，2，…，n,再从某个黑子起, 按逆时针方向依次将全体黑子标上1，2，…，n.
证明:在圆周上必可以找到连续n个棋子,使得它们 标号所成的集合恰好为｛1，2，…，n｝。
59

60

5.设n和k是正整数,且（k － n）是非负偶数.有2 n盏灯依次编号为1，2，…，2n,每一盏灯
可以开和关.开始时所有的灯都是关的, 现在要对这些 灯进行k次操作,每次操作改变且只改变一盏
灯的开关状态.用N表示满足“k次操作以后灯1，2，… ，n是开的,其它灯都是关的”的不同操作
序列总数,用M表示满足“k次操作以后灯1，2，…，n是 开的,其它灯都是关的而且从来没有被开
过”的不同操作序列总数.试求比值。
61

62

6.给定n，k是正整数,.假设F是｛1，2，…，n｝
的子 集族,如果F中的每个集合都有k个元素,而且F中任何两个集合都相交非空,那么∣F∣的最大
可能值 是多少?

63

7.有12个人,其中任何9人中都有5人两两认识.证明:这12人中必有6人两两认识。

64

【知识储备】

65

66

【例题精讲】
67

1.p≥1是实数，n是正整数.证明闵可夫斯基不等式：任给实数a< br>1
,a
2
....,b
1
,b
2
,.... ,b
n
,必有：




68

2.如果函数f：Z→R满足：存在正数M使得对于任意正数a和正整数d，
（这里
69

I=[a-d,a+d],表示f在I上的平均值），那么就称f
是 BMO的，M则称为f的一个BMO模长.证明存在正的常数C，使得对于任何BMO的函数f，只要M
是f的一个BMO模长，就有对任何正数a和正整数d,
70

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中一个的元素组成的集合.
71

72

4.证明存在正的常数C，使得平面直角坐标系中的任意有限 个（边平行于坐标轴的）正方形中
必能挑出一些正方形两两内部无公共点，而且他们覆盖的总面积不小于 全体正方形覆盖总面积的C
倍.


5.设A是一个有限实数集.A< br>1
,A
2
,…,A
n
是A的非空子集，且满足：（i）A中所 有元素之和为0；
（ii）对任意x
i
∈A
i
（i=1,2，…,n ）,都成立.证明:
73

存在1≤i
1
2
<…k
≤n使得




74

75

6.设m和n是给定的正整数，41
A< br>2
…A
2n+1
是一个正（2n+1）边形，P={A
1
， A
2
，…，A
2n+1
}.
求顶点属于P且恰有两个内角是锐角的 凸m边形个数.




76

77

7.将全体正整数用红或蓝进行二染色.证明：存在一列无穷 个递增正整数a
1
,a
2
,a
3
,…使得
全都是同 色的正整数.


78

79

8.如果平面上的有限（≥1）个非零向量形成的集合R满足 下列三个条件就称R为一个根系：（i）
任两个向量a，b∈R，是整数；（ii）任两个向量a，b∈R,∈R；（iii）如果R中两个向量共线，那么他
们或者相等或者和为0.试求平面上所有 可能的根系.
80

81

82

83

84

85