答 案
见解析
解析
解：
名选手用
个顶点，
，
，
，
表示，
其中代表那名男选手．两人握过手就在他们相应的顶点之间连一条边，得图
．
在
中，
，
，，，
，
．
并且当
时，
．
所以除顶点外，其他顶点的度分别为，，，
，
．
不妨设
，
，，，
，
．
对顶点
来说，它只和顶点
不相邻，
故
和
是搭档．
在
中去掉顶点
，
及与它们相邻的边，
得图
．
在
中除外，各顶点的度仍然不同，且都减小．
同样道理，
和
是搭档．
依次可得
和
，
和
，
，
和
是搭档，
于是
和是搭档，
所以那名男选手的女搭档握了
次手．
答 案
见解析
解析
证明：用节点
，
，
，
表示这个选手．
如果两个选手互相认识，那么就在相应的两个节点之间连一条边，这样就得到一个简单图
．
图
中的顶点满足：任意两个不相邻的顶点都恰好有两个共同相邻的顶点．
要证明的是相邻的两个节点
与
满足条件
．
从
中任取节点
．
由条件，
，
得
．
从而
中有节点，与之间有边相连．
易见，
中不同的对应于
中不同的．
模块
模块1：
1
1
例题1
48
48
v
v
0
v
1
⋯
v
46
v
G
G
d v
⩽
( i)
46
i = 0
1
2
⋯
46
i=j
/
d v
=
d v
( i) /
( j)
v
0
1
2
⋯
46
d v
=
( i)
i
i = 0
1
2
⋯
46
v
46
v
0
v
46
v
0
G
v
0
v
46
G1
G1
v
1
v
45
v
1
v
44
v
2
v
43
v
3
⋯
v
24
v
22
v
23
v
23
例题2
A1
A2
⋯
An
n
G
G
A1
A2
N A
=
∣
(
1)∣
N A
∣
(
2)∣
N A
(
1)
x =
A
(/
2)
N A
∩
(
1)
N A
=
(
2)
∅
x, A
∈
(
2) / E G
( )
N A
(
2)
y
x
N A
(
1)
x
N A
(
2)
y
这就建立起了从
到
之间元素的一一对应，
所以
．
答 案
见解析
解析
解：显然
．记个人为个点
，
，
，
．
若
，
之间通电话，则连
，
因此这个点中必有边相连，不妨设为
．
倘若
与
之间无边，分别考虑
个点
，
，
，
，
；
，
，
，
，
及
，
，
，
，
．
由题意知，
，
，
分别与
，
，
，
．之间所连边的总数相等，记为．
将
加入到
，
，
，
，
中，
则这
个点之间边的总数
．
从这
个点中任意去掉一点，剩下的
个点所连边数都是
，
故每个点都与其余
个点连
条边，
从而
．
同理，考虑
加入
，
，
，
，
中所得的
个点的情况，
可知边的总数为
．
因为
，
得
，
即
，矛盾．
所以
与
之间有边．
同理，
，
之间也有边，进而
，
与所有
之间有边．
对于
，
，
因为
与
之间有边，可知
与
之间有边，
因此这个点构成一个完全图．
所以
，
．
答 案
见解析
解析
解：设对任意两人，与他们都握过手的有人．
考虑某个，与握过手的全体记为
，
与没有握过手的全体记为
．
由题设
，
．
1
1
N A
(
1)
N A
(
2)
N A
=
∣
(
1)∣
N A
∣
(
2)∣
例题3
n ⩾5
n
n
A
1
A
2
⋯
A
n
Ai
Aj
A , A
(
i
j)
n
A , A
(
1
2)
A1
A3
n −2
A
1
A
4
A
6
⋯
A
n
A
2
A
4
A
5
⋯
A
n
A3
A4
A5
⋯
An
A1
A2
A3
A4
A5
⋯
An
k
A2
A1
A4
A6
⋯
An
n −1
S = 3
+
m
k + 1
n −1
n −2
3m
n −2
k + 1
S =
n −1
k + 1
2
1 (
) (
)
A3
A1
A4
A6
⋯
An
n −1
t = 3
+
m
k =
n −1 k
2
1 (
)
S = t + 1
n −1
k + 1 =
2
1 (
) (
)
n −1 k +
2
1 (
)
1
n = 3
A1
A2
A2
A3
A1
A2
A
i = 3, 4, ⋯, n
i (
)
Ai
A
i=
j
j ( / )
Ai
A1
Ai
Aj
n
3
=
m
n −2
n −3
2
1 (
) (
)
n = 5
例题4
n
a
a
A
a
B
A =
∣∣
3k + 6
B =
∣
∣
9k −7
再考虑
，与，都握过手的个人都在
中，
因此，与
中个人握手，与
中
人握手．
考虑
，与，都握过手的人都在
中．
于是
与
之间握手总数为
，
．
从而
．
显然
，
所以
．
由于
除以余，
所以
，
，
．
经检验只有
产生整数解
，
．
下面构造一个由
点组成的图，图中每点引出
条边，且对每一对点与它们相连的点均为个．
自然地，我们可用个完全图
．把
个点分成六组，同组的六人编号，排成一个
方阵
对方阵中的每个点，它与同行、同列、同编号的
个点相连，与其余点不相连．
易见，与任意两位代表都握过手的恰好有人．
答 案
见解析
解析
解：先把问题翻译成图论语言．把该团体的成员视为顶点，其顶点全体记做
．
对于任意两个顶点，所代表的成员，当且仅当彼此认识，
则在，之间连一条边．得到一个含
个顶点的简单图
．
已知条件是，图
中任意四个顶点中都至少有一顶点和其他三个顶点相邻．
要求图
中度为
的顶点个数的最小值
．
当图
是完全图时，每个顶点的度都是
，
所以有
个度为
的顶点．
当图
是非完全图时，图
中必有两个不相邻的顶点和．
显然
，
．
因此图
中度为
的点的个数
．
如果
中除和外另有两个顶点，不相邻，
则，，和中不存在和其他三个顶点都相邻的顶点，与题意矛盾(与图
的性质矛盾)．
因此
中除，外任意两个顶点相邻．
这说明对
中除，外的任意点，均有
．
如果
中除、外的任何都和，相邻，
则
．
此时
中度为
的顶点个数为
．
设
中除、外有个顶点和、不都相邻，
1
b ∈A
a
b
n
A
b
A
n
B
3k + 5 −n
c ∈B
a
c
n
A
A
B
3k + 6
3k + 5 −n =
(
) (
)
9k −7 n
(
)
n =
12k −1
3k + 6
3k + 5
(
) (
)
16n =
12k −1
12k −1 + 25
12k −1 + 21
(
) (
)
3, 12k −1 =
(
)
1
12k −1
25 × 7
(
) ∣
12k −1
4
3
12k −1 = 7
5 × 7
5 ×
2
7
12k −1 = 5 × 7
k = 3
n = 6
36
15
6
6
K
6
36
6 × 6
1
6
5
4
3
2
2
1
6
5
4
3
3
2
1
6
5
4
4
3
2
1
6
5
5
4
3
2
1
6
6
5
4
3
2
1
15
6
例题5
V
u
v
u
v
100
G
G
G
99
m
G
99
100
99
G
G
u
v
d u ⩽
( )
98
d v ⩽
( )
98
G
99
l ⩽98
G
u
v
x
y
u
v
x
y
G
G
u
v
G
u
v
x
d x ⩾
( )
97
G
u
v
x
u
v
d x =
( )
99
G
99
98
G
u
v
x
u
v
则有
的性质知，
中除，，外的任意顶点和、、都相邻．
因此
，
．
所以
中度为
的顶点个数为
．
这表明含
个顶点的简单图
中，如果任意四个顶点中必有一个顶点和其他三个顶点都相邻，那
么
中至少有
个度为
的顶点．
回到原问题，即得：该团体中认识其他所有人的成员最少是
个．
答 案
见解析
解析
证明：阶完全图中有
条边，
故图中仅有两对点没有连边，分为两种情形．
(i)若没有连的两边有公共点(如图
)，
则4点组
，
，
，
组成阶完全图．
(ii)若没有连的两边无公共点(图
)，
则点组
，
，
，
组成阶完全图．
答 案
见解析
解析
证明：给出的图如图
．
1
2
G
G
u
v
x
y
u
v
x
d u ⩽
( )
98
d v ⩽
( )
98
G
99
97
100
G
G
97
99
97
例题6
6
C
=
6
2
15
1
( )
A
2
A
4
A
5
A
6
4
2
( )
4
A1
A3
A5
A6
4
3
( )
答 案
见解析
解析
证明：同
情况(i)有个点组：
，
，
，
；
，
，
，
；
，
，
，
；
，
，
，
；
，
，
，
；
，
，
，
，组成阶完全图，情况(ii)中有
个点组：
，
，
，
；
，
，
，
；
，
，
，
；
，
，
，
，组成阶完全图．
答 案
见解析
解析
解：根据已知，每个人都有朋友．
如果有
个人彼此是朋友，那么根据已知他们有一个公共的朋友．我们得到
个人彼
此是朋友．
依此类推(或者用归纳法)，导出有
个人
，
，
，
彼此是朋友．
如果
是这
个人以外的人，并且
至少与
，
，
，
中两个人是朋友．
设
与
，
是朋友，则
，
，
，
，
这
个人有两个公共的朋友
，
．与已
知矛盾．
因此，
，
，
，
之外的人
至多与
，
，
，
中一个人是朋友．
设
与
，
，
，
一都不是朋友，则
，
，
，
，
的公共朋友
不是
，
，当然也不是
，
，
，
．
由于
，
与
，
，
，
中
个人是朋友．但上面已证
至多与
，
，
中一个人是朋友，矛盾．
于是，车厢中只有
，
，
，
这
个人，每个人的朋友为
个(恰好是完全图
)．
下面是图论的一个应用．
答 案
见解析
解析
解：将委员会
除去成员
、
、
后余下的成员组成集合
，
则
．
设在集合
中，与成员
、
、
均为朋友的人数分别为
．
则
．
由于成员
、
、
均与集合
中至少
人为朋友，
3
1
1
1
( )
6
4
A
1
A
4
A
5
A
6
A
2
A
4
A
5
A
6
A
3
A
4
A
5
A
6
A1
A3
A4
A5
A1
A3
A4
A6
A1
A3
A5
A6
4
4
4
A1
A3
A5
A6
A1
A4
A5
A6
A2
A3
A5
A6
A2
A4
A5
A6
4
例题7
k k ⩽m
(
)
k + 1
m + 1
A
1
A
2
⋯
A
m+1
B
m + 1
B
A
1
A
2
⋯
A
m+1
B
A
1
A
2
B
A
3
A
4
⋯
A
m+1
m
A
1
A
2
A1
A2
⋯
Am+1
B
A
1
A
2
⋯
A
m+1
B
A
2
A
3
⋯
A
m+1
B
A
1
A
2
⋯
A
m+1
C
A
m
Am+1
A1
A2
⋯
Am+1
m ⩾3
C
A
1
A
2
⋯
A
m+1
m −1 ⩾2
C
A
1
⋯
Am+1
A1
A2
⋯
Am+1
m + 1
m
k
m+1
例题8
P
A
B
C
T
T =
∣∣
n −3
T
A
B
C
a
i = 0, 1, 2, 3
i (
)
a
+
0
a
+
1
a
+
2
a
=
3
n −3
①
A
B
C
T
k −1 k =
(
[2
n])
则
．
故
．
．
由式
、
得
．
由式
、
得
．
故朋友圈的个数为
．
为了证明最小值可为，考虑极端情况．
在集合
中，
人与
、
均为朋友，
而另
人仅与
为朋友，
故朋友圈的个数为．
．
由式
、
得
．
由式
、
得
．
故朋友圈的个数为
．
为证明最小值为
，可考虑极端情况．
在集合
中，人与
、
、
中的两人交朋友，
而另外
人仅与
、
、
中的另一人交朋友，
故朋友圈的个数为
．
对于
，由完全图
可形成
个三角形，
即个朋友圈．
综上，当为奇数时，朋友圈的个数最少为
；
当偶数
时，朋友圈的个数最少为
；
当
时，朋友圈的个数最少为．
答 案
见解析
解析
解：用图论来重新描述原问题：
将
个顶点的完全图的每条边染为五种颜色之一，
求“同色角”的个数的最小值答案：
(百万里拉)．
假设个顶点的完全图的每条边染种颜色之一，
对于每个顶点引出的颜色是
的边的数目
，
．
于是，以为顶点的同色角的个数为
1
a
+
1
2a
+
2
3a
⩾
3
3 k −1
(
)
a
+
0
2a
+
2
3a
⩾
3
3 k −1
(
)
②
1 n =
( )
2k + 1
③
①
③
a
+
0
a
+
1
a
+
2
a
=
3
2k −2
④
②
④
a
+
2
2a
⩾
3
k −1
1 + a
+
2
3a
⩾
3
1 + a
+
2
2a
⩾
3
k
k
T
k −1
A
B
k −1
C
k
2 n =
( )
2k k ⩾3
(
)
⑤
①
⑤
a
+
0
a
+
1
a
+
2
a
=
3
2k −3
⑥
②
⑥
a
+
2
2a
⩾
3
k
1 + a
+
2
3a
⩾
3
1 + a
+
2
2a
⩾
3
k + 1
k + 1
T
k
A
B
C
k −3
A
B
C
k + 1
n = 4
K
4
C
=
4
3
4
4
n
2
n −1
n ⩾6
+
2
n
1
n = 4
4
例题9
36
6C
=
36
2
3780
n
r
i i = 1, 2, ⋯, r
(
)
f v, i
(
)
f v, i =
i=1
∑
r
(
)
n −1
v
C
=
i=1
∑
r
j v,i
(
)
2
f
v, i −
f v, i
2
1 (
i=1
∑
r
2 (
)
i=1
∑
r
(
))
，
此处用到了柯西不等式
对式
中所有的个顶点求和，得所有同色角的个数至少为
．
特别地，
，
时，同色角的个数为
．
下面给出恰有
个同色角的例子．
设有六个顶点
，
，
，
的完全图为
，其组成一个正六边形的顶点
正六边形的六条边，相间地染为颜色、；
将对角线
、
、
染为颜色
，
其中，下标在模意义下．
在图
的每个顶点处放置一个图
的“复制品”来代替原来的点，
从而，得到一个
个顶点的新的图．
若图
的两个顶点之间所连的边的颜色为，
对于分别放置在顶点
、
处的复制品图
、
，
将所有
、
之间所连的边也染为颜色．
下面计算同色角
的个数，其中，为固定的顶点
不失一般性，设
若
，则对于每个
，
存在唯一的一个复制品图
，
中的每个点与所连边的颜色，
与边
的颜色相同．
因此，这样的同色角有
个．
若、
，则对于任意一个不同于图
的复制品图
，
每一对顶点、
，均有边
和边
同色，
这样的同色角有
个．
综上，所有同色角的个数为
．
答 案
见解析
解析
解：最小的正整数为
．
由星程航空公司开通的单向航线可得一个有
个顶点的有向图
，且每个顶点的出度为．
先证明这
座城市至少分成
组．
假设图
中有一个长度为
的有向圈．
则对于该圈中的任意两座城市一定有一座城市最多用
次飞行到达另一座城市．故该圈中不存在两
座城市属于同一组．
因此，至少要分成
组．
再证明能分成
组就足够了．
考虑任意一个辅助的有向图
，其顶点是梦境国的城市，
1
⩾
f v, i
−n −1
2
1
⎣
⎡
r
1 (
i=1
∑
r
(
))
2
(
)
⎦
⎤
=
−n −1
2
1 [
r
n −1
(
)2
(
)]
①
①
n
−n −1
n =
2
1 [
r
n −1
(
)2
(
)]
−1
C
(
r
n −1
)
n
2
n = 36
r = 5
6C
36
2
6C36
2
A1
A2
⋯
A6
G0
1
( )
1
2
2
( )
A A
i
i3
A
A
i+1
i−1
A
A
i+2
i−2
i i = 3, 4, 5
(
)
6
G0
G0
36
G0
t
Ai
Aj
G0
′
G0
′′
a a ∈G
(
0
′ )
b b ∈G
(
0
′′)
t
a, b, c
(
)
b
b ∈G
0
′
a ∈G
0
′
a ∈G
0
′
G0
′′
G0
′′
c
b
a, b
(
)
5 × 6
a
c ∈ / G
0
′
G
0
′
G
0
′′
a
c ∈G
0
′′
a, b
(
)
b, c
(
)
5C6
2
36 5 × 6 + 5C
=
(
6
2)
6C
26
2
例题10
k
57
2016
G
1
2016
57
G
57
28
57
57
H
且若城市能用不超过
次飞行到达城市，
则从城市到城市有一个箭头．
从而，每座城市的入度最多为
．
要证明可以将图
中的所有城市分成
组，使得每组中的两座城市之间没有箭头．
只要证下面一个更强的结论．
引理：假设有个顶点的有向图满足每个顶点的入度最多为
．
则个顶点能被分成
组，使得每组中均没有两个顶点用一个箭头连接．
证明：数学归纳法．
时，结论显然成立．
对于
，假设
时结论成立．
对于个顶点的有向图
，由于每个顶点的入度最多为
，
则存在一个顶点的出度最多为
．
不妨记顶点的出度最多为
，
将点从图
中移出，得到一个有
个顶点的图
仍满足条件．
由归纳假设，可将这
个顶点分成
组，每组中均没有两个顶点用一个箭头连接．
因为点的入度和出度均最多为
，
所以，在有向图
中最多有
个顶点与相邻．
将点放到在
组中无顶点与相邻的那一组中去．
由此，完成了数学归纳法的证明．
答 案
见解析
解析
证明：对警察的每次巡逻，按照如下方式构造阶图：
对每名警察而言，若他移动了，就用有向线段将这两点连起来；
若他没有移动，则在该点放一颗珠子，
当然，可能在某个点会有不止一颗珠子．
若某个顶点的珠子数不少于，
则称该顶点为“好点”，反之称为“坏点”．
首先证明一个引理
引理：若从某个好点出发的有向线段不少于一条，则存在三个点
、
、
满足：
、
为坏点，且除了点
、
、
，没有从
或
出发的有向线段；
点
的度和珠子数之和至少为(度包括入度和出度)；
除了点
，没有其他好点连向
或
．
证明：令为珠子数，
为好点数，
是从好点出发的有向线段集合．
设
．
若
，用
代表这个好点，
出发有一条有向线段．
若
，
因为至少有两条有向线段，
所以，图中顶点的度和珠子数之和超过，
这表明，存在一个顶点
，其度数和珠子数之和不少于．
于是，不妨设
为好点且存在一条由点
出发的有向线段，
．令
是出度为的坏点的集
合．
由于坏点的出度和为
，
则
1
v
28
u
u
v
28
H
57
n
28
n
57
n = 1
n ⩾2
n −1
n
H
28
28
v
28
H
n −1
H′
n −1
57
v
28
H
56
v
v
57
v
例题11
n
1
A
B
C
1 A
( )
B
A
B
C
A
B
2
( )
C
2
3
( )
C
A
B
x
y y ⩽x
(
)
V
V
=
∣
∣
z
z ⩾1
C
C
z = 0
n
C
2
C
C
z ⩾1
U
0
n −1 −x −z
U ⩾
∣
∣
n −y −
(
)
n −1 −x −z
(
)
．
再设从点
出发的有向线段的集合为
．
则
，
即可以选出两个顶点
、
，使得不存在有向线段
指向点
或
．
从而，点
、
、
满足引理中的条件．
引理得证．
对于互异的点
，
，
，
，
，
，
若小偷可以在警察次巡逻后仍旧没在桥上被抓，
则称集合
为“ —集”．
显然，只要说明—集的存在性即可．
对进行归纳．
当
时，显然成立．
假设
时，存在一集，考虑
次巡逻．
若存在一条有向线段且该有向线段从一个坏点出发，
则
也是一个
一集．
若不然，由引理知可以选择点
．
下面证明：
为
一集，
其中，
；
、
之一属于
．
不妨设
．
若
(
类似)，注意到，
，
于是，可以选择一个顶点同时在集合
、
中． 若
，
则
、
之一属于集合
．
因此，集合
、
有公共的桥且以
、
之一作为终
点．
据引理中的条件
，小偷可以留在桥
上．
若存在至多一条有向线段从
到
、
，
则小偷可以停留在桥
或桥
上．
令
为
集合中均指向
、
的
构成的集合，
．
当
时，结论显然成立．
假设
，任取
，
则
与
中的点连成的有向线段条数加上
中的珠子数总和不会超过
，
而此和小于
．
从而，存在某个坏点
，使得
与
间无有向线段．
因此，由引理中的条件
，知这个小偷可以从
到
或
．
命题得证．
= 1 + z + x −y ⩾
(
)
1 + z
C
V ′
V \V
⩽
∣
′∣
z −1
A
B ∈U
e ∈V \V ′
A
B
A
B
C
A1
A2
B
1
B
2
⋯
B
n−3
k
A
, A
, B
, ⋯, B
⟨
1
2
1
n−3⟩
=
A
A
, A
B
, ⋯, A
B
, A
B
, ⋯, A
B
{
1
2
1
1
1
n−3
2
1
2
n−3}
k
k
k
k = 0
k ⩾0
k
k + 1
A
, A
, B
, ⋯, B
⟨
1
2
1
n−3⟩
k + 1
A
, A
, B
, ⋯, B
⟨
1
2
1
n−3⟩
A, B, C
, ⋯, C
⟨
1
n−3⟩
k + 1
C ∈ /
C
, ⋯, C
{
1
n−3}
A
1
A
2
A, B, C
, ⋯, C
⟨
1
n−3⟩
A
∈
1
A, B, C
, ⋯, C
⟨
1
n−3⟩
A
=
1
A A
=
1
B
n −2 ⩾2
A
, B
, ⋯, B
⟨
2
1
n−3⟩
B, C
, ⋯, C
⟨
1
n−3⟩
A
=
1
C
1 ⩽i ⩽n −3
i (
)
A
B
A
, B
, ⋯, B
⟨
2
1
n−3⟩
A
, B
, ⋯, B
⟨
2
1
n−3⟩
A
, A
, B
, ⋯, B
⟨
1
2
1
n−3⟩
A
B
1
( )
AB
C
i
A
B
AC
i
BC
i
W
W
= r
1 (∣
1∣
)
C
, C
, ⋯, C
⟨
1
2
n−3⟩
A
B
C
i
W
=
2
C
, C
, ⋯, C
\W
{
1
2
n−3}
1
r = 0
r ⩾1
C
∈
i
W
1
C
i
W
2
W
2
n −1 −2 −2r = n −3 −2r
W
=
∣
2∣
n −3 −r
C
∈
i
W
2
C
i
C
j
3
( )
C
C
j
i
C
A
i
C
B
i
