答 案
见解析
解析
解：我们来观察包括首都在内的航线图中的连通成分，构成一个连通图，
只要证明在这个连通图中也包括
市．
假设不真．于是由这个图的一个顶点(首都)连出了
条边，而从其他每个顶点都连出
条边．
这意味着这个图中恰有一个度数为奇数的顶点，此为不可能！
答 案
见解析
解析
证明：
，
代表居民，无向图
，
认识用边相连，
，
对应长度为的
．
固定
，恰好有
个
过
．
定义：
．
，
，取
一个
连通．
，
．
是单射．两边元素个数相等，
所以是双射．
如果存在
，则
，对于
，只能找到一个
．
所以没有
，
圈．
连通图没有
，
圈，只可能是树或者至少
圈．
但是所有点都最多长度为的
连通，
树的情形只可能是
，矛盾．
如果至少
圈，有两点
大于．
所以只可能是
．
模块
模块1：
1
1
1
例题1
A
21
20
例题2
k = 5
v
i
G
a
=
i
deg v
i
v
, v
, v
( i
j
l)
2
walks
v
j
a
j
2
walks
v
j
f
v
, v
, i=
j
→
{( i
j)
/ }
walksinE G
( )
f v
, v
=
( i
j)
v
, v
, v
( i
l
j)
v
v
∈
i
j / E G
( )
v
l
f v
, v
=
( i
j)
v
, v
, v
( i
j
i)
v
v
∈
i
j
E G
( )
f
v
l
v
v
∈
i
j / G
v
v
∈
i
j / G
v
l
C
3
C
4
C
3
C
4
C
5
2
path
star
C
6
path
2
C
5
例题3
答 案
见解析
解析
证明：我们关于用数学归纳法来证明，
可将
个城市划归为两个主权国家
和
，使得两国城市数分别是和
．
当
时命题显然成立．
设命题对
时成立，
即
个城市可划分为两个主权国家
和
，其中
和
内分别有和
个国家，
于是
时，命题能否成立的关键是能否从B国中拨一个城市给
国．
首先，从
中任取一个与
国某城有道路相通的城市
(依题意，这样的城市必存在)．
若将
拨给
后，
国内部的交通网仍然是连通的(即从任何一个城市只经过国内的道路可抵达任
何另一城市)，
则问题就解决了；
若不然，则
国在
被拨走之后，其余城市将被分成一些非空子集
，
，
，
，
其中
，使每个子集内的城市之间是连通的，
属于任何两个不同子集的两城市之道都不能仅通过
国内部的道路来通行．
换句话说，这
个子集之间的连通只有经过
才行，
我们称
为从属于
对
国的分划．
这时将
留在
国，并从子集
中取一个与
国有道路相通的城市
，
如果将
拨给
国后，
国的交通网仍是连通的，那么问题就解决了．
否则，又得到一个从属于
的
国的分划
，
因为
，
，
，
之间可通过
连通，
所以它们的并集属于某一个
(含
的子集)，不妨设
，
于是
，
，
，
都是
的子集，
即
的真子集(这是因为
，
，
，
之间可通过
连通且
)．
如此继续下去，可得一串城市
，
，
和相应于它们的分划中的子集
， 使得到某个
时拨给
国后满足要求，或者一直下去直到某个
仅
有一个城市
为止，
这时只要把
拨给
国就可以了，
即当
时命题也成立，于是原命题得证．
答 案
见解析
解析
证明：用反证法．假设结论不成立，即对每一道题
，去掉后，
必存在一对学生
和
做对的题目相同(若有好几对这样的学生，则任取其中一对)．
将学生用点表示，并在上述学生
与
之间连一条边，边的标号为，这样得到一个图
有
个
点，
条边，各边的标号为，，，
，
．
图
由若干连通分支组成(若
本身是连通的，那么只有个连通分支，即
本身)．
由于
的顶点数
边数，
故必有一连通分支
的顶点数
边数，
于是
必有圈．
设
，
，
，
是一个圈，那么沿着这个圈前进时，
每通过一条边就相当于做对的题目增加或减少一道，
即假设一开始
做对的题目构成的集合为
，
1
n
100
A
B
n
100 −n
n = 1
n = k
100
A
B
A
B
k
n −k
n = k + 1
A
B
A
a
1
a1
A
B
B
a
1
B
11
B
12
⋯
B
1m
1
m
⩾
1
2
B
m1
a1
B
, B
, ⋯, B
{
11
12
1m
1}
a
1
B
a1
B
B
11
A
a
2
a2
A
B
a2
B
B
, B
, ⋯, B
{
21
22
2m
2}
B
11
B
12
⋯
B
1m
1
a
1
B
2i
a
1
i = m
2
B
21
B
22
⋯
B
2m
−1
2
B
−
11
a
{
2}
B
11
B
21
B
22
⋯
B
2m
−1
2
a
2
a
∈
2
B
11
a1
a2
⋯
B
⫌
11
B
⫌
21
B
⫌
31
⋯
a
i
A
B
j1
aj+1
aj+1
A
n = k + 1
例题4
h 1 ⩽h ⩽10
(
)
h
v
i
v
j
v
i
v
j
h
G
10
10
1
2
3
⋯
10
G
G
1
G
G
⩽
G
⩽
G
v
1
v
2
⋯
v
k
v
i
M v
i = 1, 2, ⋯, k
( i) (
)
则
中要增加或减少一道题(题目的编号为边
上的标号)才与
相同(
，，
，，其中
)，
并且由于各边上的标号互不相同，
故每次增加或减少的题目互不相同．
于是
做对的题目集合
通过增加和减少一些互不相同的题，
最后得到的集合
仍与
原来做对的题目集合完全相同，矛盾．
这就证明了原命题的结论成立．
答 案
见解析
解析
解：如图，
时，国王的打算可以实现，
线段上的数表示该线段两端代表的两个城市之间的距离．
答 案
见解析
解析
解：我们先求出符合要求的道路网络存在时，必须满足的必要条件．
用点表示城市，用线段表示连接城市的道路，得到一个图
．
依题意，
是一个阶连通图，又其边数恰为
，
故
是阶树，
因而
的任意两点之间只存在唯一的路．任取一点
，称
为“好点”，
而对其他任意一点，若它沿唯一路到达
的距离是偶数，则称该点为“好点”，
否则称该点为“坏点”(即这点沿唯一路到达
的距离是奇数)．
设
中“好点”的数目为，则坏点的数目为
，
由一个“好点”和一个“坏点”组成的点对有
个．
容易知道：两点之间的距离为奇数，
当且仅当两个点一“好”一“坏”又在，，，
，
中，
当
为偶数时，其中的奇数有
个；
1
2
M v
( i)
v
v
i
i+1
M v
( i+1)
i = 1
2
⋯
k
v
=
k+1
v
1
v
1
M v
( 1)
M v
=
( k+1)
M v
( 1)
v
1
例题5
n = 6
n
G
G
n
n −1
G
n
G
A
A
A
A
G
x
y = n −x
xy
1
2
3
⋯
n n −1
2
1
(
)
n n −1
2
1
(
)
n n −1
4
1
(
)
当
为奇数时，其中的奇数的个数为
个．
于是，如果国王的打算可以实现，那么必须有
或
．
结合
可得
或
，
即国王的打算可以实现的必要条件是或
为完全平方数，
但
以及
都不是完全平方数，
故
时，国王的打算不可能实现．
答 案
见解析
解析
解：
．
首先证明：
．
若
，不妨设有两座城市
、
间至少经过
次到达．设城市
到
的一个最短连接
线路为
．
因为每一座城市至少和七座城市有直航连接，所以城市
、
与除
以外至少六座城市
有直航连接，
与除
以外至少五座城市有直航连接．
设
，分别与城市
、
、
、
、
、
、
、
、
、
有直航连接，且不属于城市
的所有城市组成的集合为
．易知，
，
，
．
又
，否则，城市
、
之间有更短连接路线．
故
，矛盾．
所以，
．
其次证明：
．
对
，取
座城市
，
，
，
与城市集合
．当
, 时，
；当
，，
，时，
，且对
，
，
中
不包括城市
，
，
，
．对
，城市
、
、
与集合
中的所有
城市有直航连接；城市
、
集合与
中所有城市有直航连接；城市
、
与集合
中所
有城市有直航连接；集合
中任意一座城市除与上述的城市
有直航连接，与且仅
与集合
中其余城市有直航连接；城市
与
有直航连接
．
这样，城市
至少与七座城市有直航连接，集合
中任意一座城市均只与七座城市有直航
连接，且城市
至少经过
次直航来连接．因此，
．
1
n n −1
2
1
(
)
n n −1 + 1
=
2
1 [2
1
(
)
]
n n −1 + 2
4
1 [ (
)
]
xy =
n n −1
4
1
(
)
xy =
n n −1 + 2
4
1 [ (
)
]
x + y = n
n = x −y
(
)2
n = x −y
+
(
)2
2
n
n −2
2004
2004 −2 = 2002
n = 2004
例题6
k = 27
k ⩽27
k ⩾28
A
1
A
29
28
A
1
A
29
A
→
1
A
→
2
⋯→A
29
A1
A29
A
∼
2
A
28
A
∼
2
A
28
A
∼
1
A
29
A =
A
, A
, ⋯, A
{
1
2
29}
A
1
A
4
A
7
A
10
A
13
A
16
A
19
A
22
A
25
A29
A
X
i = 0, 1, ⋯, 9
i (
)
X
⩾
∣
0∣
6
X
⩾
∣
9∣
6
X
⩾
∣
i∣
5 i = 1, 2, ⋯, 8
(
)
X
∩
i
X
=
j
∅i=
j
( / )
A
1
A
29
A ∪X
∪X
∪⋯∪X
⩾
∣
(
0
1
9)∣
29 + 6 × 2 + 5 × 8 = 81 > 80
k ⩽27
k = 27
k = 27
28
A
1
A
2
⋯
A
28
X
i = 0, 1, ⋯, 9
i (
)
i = 0 9
X
=
∣
i∣
6
i = 1
2
⋯
8
2 + 2 = 4
0 ⩽i < j ⩽9
X
∩
i
X
=
j
∅
X
i
A1
A2
⋯
A28
1 ⩽k ⩽8
A
3k
A
3k+1
A
3k+2
X
k
A1
A2
X
0
A
27
A
28
X
9
X
0 ⩽i ⩽9
i (
)
A
s
X
i
A
i
A
i+1
i = 1, 2, ⋯, 27
(
)
A
∼
1
A
28
X
i
A
∼
1
A
28
27
k = 27
答 案
见解析
解析
解：问题等价于求在由六个点和若干条边构成的图中，满足任意两点均连通的所有连接方式种数．
为此，用
表示个点中的任意两点均连通的所有连接方式的种数，则
，
．
对于三个点的情形，要么任意两点之间均有连线，要么在三条连线中任选两条均可对任意两点连
通，因此，
．
接下来推导
的一般表达式．
由于个点可有
条边，故总共有
种不同连接方式(任意两点之间要么有连线，要么没有连
线)．
选定个点中的一个点，考虑包含点在内的
个点构成的集合，可从除去点之外的
个点中任取
个点，与连通构成这个个点的集合，故有
种选取方式．
又由
的定义，知对于选取的
个点和点，共有
种方式使任意两点均连通，而对于余
下的
个点，又有
种不同连接方式．
因此，
由该递推关系及
，
，
，得
，
，
故所求数值为
，这是因为
种方式中，有
种方式关闭了若干段铁路，而种没有
关闭任何一段铁路．
答 案
见解析
解析
解：先构造一个有向图，其顶点是各座城市，边就是各条道路．
若某条道路实施单向行车规则，则在该条道路上用箭头标注行车方向；对于双向行车的道路则不标
注箭头．
再证明：在事情进程的任意时刻，均可以有办法给任何一条还没有标注箭头的道路上标上箭头，使
得图的连通性不受破坏．由此即可推知，在正确的策略下，两名部长均会善始善终，即均可以保住
自己的职位．
假设连接顶点、的边
上还没有标注箭头．容易看出，若在这两个顶点之间存在着其他的路
(不失一般性，假定沿着这条路可以从顶点走到)，而无须经过边
，则可以在边
上标
注由顶点指向的箭头．此时，对于任何一条途经边
时按
方向行车的路，可以让其
沿着由顶点到的另一条路行驶，图的连通性未受破坏．
因此，只须考虑顶点到与之间不存在不经过边
的路的情形．
将由顶点无须经过边
可以到达的所有城市的集合记作
(包括本身)．因为图是连通的，所
以，对于集合
中的每一个顶点，均存在由其到达顶点的路．
然而，在假定之下，这些路均需要经过边
．这表明，由集合
中的每一个顶点均有路到达顶
点，而无须经过边
，即由集合
中的每一个顶点均有路到达该集合中的任何一个其他的顶
1
1
例题7
f n
( )
n
f 1 =
( )
1
f 2 =
( )
1
f 3 =
( )
4
f n
( )
n
Cn
2
2Cn
2
n
v
v
i 1 ⩽i ⩽n
(
)
v
n −1
i −1
v
i
C
n−1
i−1
f i( )
i −1
v
f i( )
n −i
2C
n−1
2
2
=
C
n
2
C
f i 2
i=1
∑
n
n−1
i−1
( )
C
n−i
2
f 1 =
( )
1
f 2 =
( )
1
f 3 =
( )
4
f 4 =
( )
38
f 5 =
( )
728
f 6 =
( )
26704
26703
26704
26703
1
例题8
u
v
u, v
(
)
u
v
u, v
(
)
u, v
(
)
v
u
u, v
(
)
u →v
u
v
u
v
u, v
(
)
u
u, v
(
)
U
u
U
v
u, v
(
)
U
u
u, v
(
)
U
点，而无须经过边
．
类似地，对于由顶点无须经过边
所能到达的所有城市的集合
而言，其中的每一个顶点也
均有路到达该集合中的任何一个其他的顶点，而无须经过边
．
既然图是连通的，于是，每座城市均恰属于集合
与
之一．而根据题意，在没有标注任何箭头之
前，任意去掉图中的一条边，图均仍然保持连通．这表明，在集合
与
之间，除了边
之
外，还存在另外一条边．假设沿着这条边可以由
走到
(可能在进程中的这一时刻，
该条边上已经标注了箭头，也可能没有标注箭头，但是任何时候，至少有一个方向，例如由顶点
到
是可以沿着它通行的)．由此可以由顶点
到
，再由
到，而无须经过边
．此与前
面的假设相矛盾．这一矛盾表明断言成立．
答 案
见解析
解析
解：首先，一棵条边的树有
个顶点．
对于给定的一棵条边的树
，用，，
，
给所有与
同构的树的顶点标号，且满足对于
其中任意两棵树
、
，
的标号、
的顶点间连有边当且仅
当
的标号、的顶点间连有边．
根据同构的定义，条件
是可以做到的．
注意到，在分割立方体时，立方体的一个顶点会作为不同的多个树的顶点，在不同的树中可能会有
不同的标号．
下面对归纳证明一个更强的命题．
命题：设
是一棵有条边的树，则维立方体可以被分割为与
同构的树，同时，存在一种满足条
件
的标号方法，使得维立方体的任何一个顶点
，对于它所拥有的任意
标号
，恰在一棵树中用标记．
证明：当
, 时，命题显然成立．
假设命题对成立．
接下来考虑
维立方体．
维立方体(这里指以其顶点为顶点，以其棱为边的图)可按下面的方法得到：
作两个维立方体，在这两个立方体各自顶点分别组成的集合间建立任意的双射关系，并将对应顶
点连线，即得到一个
维立方体．
在维立方体的基础上，还原出一个
维立方体．
由树的定义，知对任意
条边的树
，一定存在度数是不是的顶点，将
去掉一个度数是的顶
点和与其相邻的边，即得到一棵条边的树
．
取两个维立方体，在顶点集之间建立双射(注意，这里的映射关系与条件
并不相同，下面还原出
维立方体的过程并不依据这里的映射)．
根据归纳假设，维立方体可以分割为与
同构的树，且任意顶点在所属不同的树中具有互不相同
的标号，并满足条件
．
按照上述方法对两个立方体进行完全相同的分割，即一个顶点在一棵树中具有某个标号当且仅当它
对应的顶点在对应的树中具有相同的标号(用，，
，
标号)，在集合
中任取一个．
由归纳假设，知在两个维立方体中各恰有
个用标记过的顶点，也就各恰有
个没有用标
记过的顶点．
将所有没有用标记过的点标上
，并与另一个维立方体中一个用标记过的顶点相连，并保证
每个顶点恰与另一个立方体中的一个顶点连有边(注意到，用标记过的顶点与未被标记过的顶点一
样多，这样的操作一定是可以实现的)．
1
u, v
(
)
v
u, v
(
)
V
u, v
(
)
U
V
U
V
u, v
(
)
u
∈
1
U
v
∈
1
V
u1
v
1
u
1
v
1
v
1
v
u, v
(
)
例题9
k
k + 1
k
T
1
2
⋯
k + 1
T
A
B
A
i
j i, j ∈1, 2, ⋯, k + 1 , i=
j
(
{
}
/ )
B
i
j
①
①
k
T
k
k
T
①
k
A
i = 1, 2, ⋯, 2
i (
k)
j j = 1, 2, ⋯, k + 1
(
)
j
k = 1 2
k
k + 1
k + 1
k
k + 1
k
k + 1
②
k + 1
T
T
1
k
T
0
k
②
k + 1
k
T
0
①
1
2
⋯
k + 1
1, 2, ⋯, k + 1
{
}
i
k
2k−1
i
2k−1
i
i
k + 2
k
i
i
i
于是，就还原出了一个
维立方体，其中，每棵与
同构的树并上与其顶点相连的顶点
和连接它们的边，就得到一个
条边的树
，
的顶点已经用，，
，
标号，
若一个顶点在一棵树中标号为
，则这棵树的另外
个顶点原来一定不与顶点
在一
个维立方体中，因为每个立方体恰属于一棵这样的树，它的另外
个顶点最初同在另一个维
立方体中，所以，所得
维立方体的任意顶点至多在一棵树中用
标记过．
结合归纳假设，如
维立方体的任何一个顶点
，对于它所拥有的任
意标号
，恰在一棵树中用标记．
于是，完全归纳，命题得证．
k + 1
T
0
i
k + 2
k + 1
T
T
1
2
⋯
k + 2
k + 2
k + 1
k + 2
k
k + 1
k
k + 1
k + 2
k + 1
A
i = 1, 2, ⋯, 2
i (
k+1)
j j = 1, 2, ⋯, k + 2
(
)
j
